재귀, 자기호출 (recursion)

재귀는 '내 안의 나를 찾는것' -> 성격은 같고 크기만 작은 나를 찾아 큰 나와 작은 나가 연결된 관계를 드러내는 것 즉, 자기 자신을 호출하는 방법

 

예시) 팩토리얼 계산

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

	public static void main(String[] args) {
    	int number = 5;
        int result = factorial(number);
        System.out.prntln(result);
    }
}

 

예시) 피보나치 수열

public class FibonacciRecursion {
	public static int fibonacci(int n) {
    	if (n ==1 || n==2) {
        	return 1;
        } else {
        	return fibonacci(n-1) + fibonacci(n-2);
        }
    }

 

예시) 하노이 탑

 

move( n, a, b, c):
	if (n > 0 )
    	move(n-1, a,c,b)
        a 에 있는 원반을 b로 옮긴다
        move(n-1, c, b, a)

move(n, a, b, c) 를 수행하는 과정에서 move(0, ...)이 총 2^n번이나 호출된다. 왜..? 설명해주실 분?