[Algorithm] 재귀함수(피보나치 수열, 팩토리)

재귀함수란?

정의 단계에서 자신을 재참조하는 함수를 뜻한다.

 

예제

public Main{

	public static void func(int count) {
        if (count == 3) {  
            return;
        }
        func(count + 1);
        System.out.println("count : " + count);
    }
    
    public static void main(String[] args) {
    	 func(0);
    }
}

결과값이 어떨까요?

결과는

count : 2
count : 1
count : 0

이렇게 나오는데 그 이유는 재귀 호출을 한 후에 count가 출력하도록 되어있기 때문에 콜스택에 차근 차근 쌓이며

func(0) 호출 -> func(1) 호출 -> func(2) 호출 -> func(3) 에서 조건에 의해 중단, 콜스택 맨마지막 기준으로 2, 1, 0 순으로 출력이 됩니다.

 

이제 재귀함수로 피보나치 수열을 만드는 법을 보겠습니다.

 

피보나치 수열

피보나치 수열은 0 1 1 2 3 5 8 13.... 앞에 있는 두 수를 더하여 그 다음의 수를 얻을 수 있습니다.

첫번째 수와 두번째 수는 0과 1이고 

그 다음 n번째 피보나치 수는 (n-1번째 피보나치 수) + (n-2번째 피보나치 수)입니다.

 

자바에선 동적계획법과 메모이제이션 방법으로 구할 수 있습니다.

 

예제

//동적계획법
public class FibonacciExample {

    public static int fibonacci(int n) {
    //종료조건
        if (n <= 1) {
            return n;
        }

        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        
		//n이 2이상일 경우
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        return dp[n];
    }

    public static void main(String[] args) {
        // 피보나치 수열의 첫 10개 항을 출력
        for (int i = 0; i < 10; i++) {
            System.out.println(fibonacci(i));
        }
    }
}


//메모이제이션
public class FibonacciExample {

    public static int fibonacci(int n) {
    //종료조건
        if (n <= 1) {
            return n;
        }

      int a = 0, b = 1, temp;
        for(int i = 2;i<=n;i++){
        	temp = b;
            b = a + b;
            a = temp;
        }
        return b;
    }

    public static void main(String[] args) {
        // 피보나치 수열의 첫 10개 항을 출력
        for (int i = 0; i < 10; i++) {
            System.out.println(fibonacci(i));
        }
    }
}