순환이란

자기 자신을 호출하는 함수, 매서드

재귀함수라고도 함

public class Code01 {
	public static void main(String [] args) {
		func(); // 여기서 함수를 호출하고 함수가 무한으로 호출됨
	}
	public static void func() {
		System.out.println("hello");
		func(); 
	}
}

• 이때 무한 루프에 빠지지 않는 상황

이렇게 되면 func(4)부터 func(1)까지 실행되어 Hello…를 4번 출력하고 마지막 k가 0이 되었을 때 그 전 실행문인 func(0)이 실행되고 이어서 다시 코드가 실행되게 된다. 이때 else 문 내에 func()문 이후에 다른 코드가 없어 아무런 반응이 나오지 않게 된다.

재귀함수에서 무한 루프에 빠지지 않기 위한 조건

• Base case : 적어도 하나의 recursion에 빠지지 않는 경우가 존재해야 한다.
  • 위 코드에서의 Base case는 if (k≤0) return; 이다.
• Recursion case : recursion을 반복하다보면 결국 base case로 수렴해야 한다.
  • 위 코드에서의 Recursion case는 func(k-1); 이다.

public class Code01 {
	public static void main(String [] args) {
		func(4);
		System.out.println(result);
	}
	public static void func(int n) {
		if (n<=0){
			return 0;
		}
		else{
				System.out.println("hello");
				return n+func(n-1); 
		}
	}
}
// 해당 계산 결과가 나와 10이 된다

해당 Recursion의 해석

	public static int func(int n) {
		if (n==0){
			return 0; // n=0이라면 합은 0이다.
		}
		else{
				return n+func(n-1); // n이 0보다 크다면 0에서 n까지의 합은 0에서 n-1까지의 합에 n을 더한 것이다.
		}
	}
	// 이 함수는 0~n까지의 합을 구하는 것

순환 함수와 수학적 귀납법

정리 : func(int n)은 음이 아닌 정수 n에 대해서 0에서 n까지의 합을 올바로 계산한다.

증명

1. n=0인 경우 : n=0인 경우 0을 반환한다. ( O )
2. 임의의 양의 정수 k에 대해서 n<k인 경우 0에서 n까지의 합을 올바르게 계산하여 반환한다고 가정.
3. n=k인 경우 : func은 먼저 func(k-1)을 호출하는데 2번의 가정에 의해서 0에서 k-1까지의 합이 올바르게 계산되어 반환된다. 메서드 func은 그 값에 n을 더해서 반환한다. 따라서 메서드 func은 0에서 k까지의 합을 올바로 계산하여 반환한다.

재귀함수의 대표적인 예

1. Factorial : n!

0에서 n까지의 합

Factorial의 정의
0! = 1
n! = n x (n - 1)! n > 0

	public static int factorial(int n) {
		if (n==0){
			return 1;
		}
		else{
				return n*factorial(n-1); 
		}
	}

순환 함수와 수학적 귀납법

정리 : factorial(int n)은 음이 아닌 정수 n에 대해서 n! 을 올바로 계산한다.

증명

1. n=0인 경우 : n=0인 경우 1을 반환한다. ( O )
2. 임의의 양의 정수 k에 대해서 n<k인 경우 n! 을 올바르게 계산하여 반환한다고 가정.
3. n=k인 경우 : factorial은 먼저 factorial(k-1)을 호출하는데 2번의 가정에 의해서 (k-1)! 이 올바르게 계산되어 반환된다. 따라서 메서드 factorial은 k*(k-1)! = k! 을 반환한다.

2. x^n

x^0 = 1
x^n = x*x^n-1 if n > 0

public static double power(double x, int n){
	if (n==0)
		return 1;
	else
		return x*power(x, n-1);
}

3. Fibonacci number

f0 = 0
f1 = 1
fn = fn-1 + fn-2 if n>1

public int fibonacci(int n){
	if(n<2)
		return n;
	else
		return fibonacci(n-1) + fibonacci(n-2);
}

4. 최대공약수 : Euclid method

public static int gcd(int m,int n){
	if(m<n){
		// swap m and n
		int tmp = m;
		m = n;
		n = tmp;
	}
	if (m%n==0)
		return n;
	else
		return gcd(n, m%n)
}

m≥n인 두 양의 정수 m과 n에 대해서 m이 n의 배수이면 gcd(m,n)=n이고, 그렇지 않으면gcd(m,n)=gcd(n,m%n)이다.

해당 정리를 조금 단순화 하게 되면

public static int gcd(int p,int q){
	if (q==0)
		return p;
	else
		return gcd(q, p%q)
}