Recursion

Recursion 

 - 자기 자신을 호출하는 함수

 

void func(...)
{
	func(...);
}

 

 

위 함수를 실행코드로 짜보자

 

public class Recursive1 {
    public static void main(String[] args) {
        func();
    }

    public static void func(int k) {
        System.out.println("Hello");
        func();    
    }
}

 

 

위와 같은 코드를 실행하게 되면 return문이 없기 때문에 무한 반복으로 Hello를 출력하면서 에러가 발생하게 된다.

 

그럼 Recursion은 항상 무한루프에 빠질까?

 

그건 아니다.

 

또 하나의 코드를 보자

public class Code02 {
    public static void main(String[] args) {
        int k = 4;
        func(k);
    }

    public static void func(int k) {
        if (k<=0)  // Base case : 적어도 하나의 recursion에 빠지지 않는 경우가 존재해야 한다.
            return;
        else {
            System.out.println("Hello...");
            func(k-1); // Recursive case : recursion을 반복하다보면 결국 base case로 수렴해야 한다.
        }
            
    }
}

 

해당 코드는 func() 함수에 k의 값을 1을 빼면서 재귀를 하기 때문에 k <= 0일때 return을 통해서 코드를 빠져나오게 된다.

 

순환함수와 수학적 귀납법

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

증명:
1. n=0인 경우: 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까지의 합을 올바로 계산하여 반환한다.

0! = 1
n! = n X (n-1)!    n>0