Recursion 순환
•
보통의 경우, recursion 은 무한루프를 돈다.
package practice.algorithm;public class Main { public static void main(String[] args) { func(); } public static void func() { System.out.println("Hello ..."); func(); }}/*resultHello ...Hello ...Hello ...Hello ......*/
Java
복사
하지만, recursion 이 항상 무한루프에 빠지는 것은 아니다.
두 가지의 조건을 충족한다면, recursion 은 무한루프에 빠지지 않는다.
•
base case : 적어도 하나의 recursion에 빠지지 않는 경우가 존재해야한다.
•
recursive case : recursion 을 반복하다보면 결국 base case 로 수렴해야한다.
package practice.algorithm;public class Main { public static void main(String[] args) { int a = 4; func(a); } public static void func(int a) { if (a <= 0) { //base case return; } System.out.println("Hello ..."); func(a-1); //recursive case : 결국 0으로 수렴한다. }}/*resultHello ...Hello ...Hello ...Hello ...Process finished with exit code 0*/
Java
복사
recursion 을 이용하여 1부터 N까지의 합을 구하기
package practice.algorithm;public class Main { public static void main(String[] args) { int result = sum(4); System.out.println("result = " + result); } public static int sum(int n) { if (n == 0) { return 0; } return n + sum(n-1); }}//result = 10
Java
복사
수학적 귀납법으로 위의 코드를 증명하기
•
정리 : func(int n)은 음이 아닌 정수 n에 대해서 0에서 n까지의 합을 올바로 계산한다.
•
증명
1.
n=0인 경우, 0을 반환한다. → 올바르다.
2.
임의의 양수 k에 대하여 n<k 라고 할 때, 0에서 n까지의 합을 올바르게 계산하여 반환한다고 가정을 해보자.
3.
n=k인 경우를 고려해보자. func 는 먼저 func(k-1) 호출하는데 2번의 가정에 의해서 0부터 k-1까지의 합을 올바르게 계산하여 반환한다. 매서드 func 는 그 값에다가 n을 더하여 반환한다. 따라서 매서드 func 는 0에서 k까지의 합을 올바로 계산하여 반환한다.
Factorial : n!
•
0! = 1
•
n! = n*(n-1)! (if n>0)
package practice.algorithm;public class Main { public static void main(String[] args) { int result = factorial(5); System.out.println("result = " + result); } public static int factorial(int n) { if (n == 0) { return 1; } return n * factorial(n-1); }}//result = 120
Java
복사
수학적 귀납법으로 위의 코드 증명하기
•
정리 : factorial(int n)은 음이 아닌 정수 n에 대하여 n!을 올바로 계산한다.
•
증명
1.
먼저, n=0인 경우, 1을 반환한다. 올바르다.
2.
임의의 양의 정수인 k에 대해서 n < k인 경우, n! 를 올바르게 계산한다고 가정해보자.
3.
만약 n=k인 경우, factorial 은 먼저 factorial(k-1)를 호출하는데 2번의 가정에 의해서 (k-1)!이 올바로 계산되어 반환된다. 매서드 factorial 은 여기에 k 를 곱하여 반환하므로k*(k-1)! = k! 를 올바로 반환한다고 할 수 있다.
x^n 도 같은 방식으로 적용될 수 있다.
package practice.algorithm;public class Main { public static void main(String[] args) { int result = power(5, 3); System.out.println("result = " + result); } public static int power(int x, int n) { if (n == 0) { return 1; } return x * power(x, n-1); }}//result = 125
Java
복사
Fibonacci Number
package practice.algorithm;public class Main { public static void main(String[] args) { int result = fibonacci(5); System.out.println("result = " + result); } public static int fibonacci(int n) { if (n < 2) { return n; } return fibonacci(n-1) + fibonacci(n-2); }}//result = 5
Java
복사
최대공약수 : Euclid Method
package practice.algorithm;public class Main { public static void main(String[] args) { int result = gcd(90, 120); System.out.println("result = " + result); } public static int gcd(int m, int n) { if (m < n) { int temp = 0; temp = m; m = n; n = temp; } if (m%n == 0) { return n; } return gcd(n, m%n); }}
Java
복사
•
m≥n 인 두 양의 정수 m과 n에 대해서 m이 n의 배수이면, gcd(m, n) = n이고
•
그렇지 않으면 gcd(m, n) = gcd(n, m%n)이다.