재귀 - 피보나치

피보나치 수열
앞에 있는 숫자와 그 앞에 숫자를 더한 것을 나열하는 수열

1. 재귀함수로 피보나치수열을 구현

public static int fibo(int data) {
	if(data <= 1) {
    	return 1;
    }
    //앞에 있는 숫자와, 그 앞에 있는 숫자를 재귀함수를 사용하여 더함
    return fibo(data - 1) + fibo(data - 2);
}

중복 호출이 발생한다.

2. 메모이제이션을 이용한 피보나치수열

메모이제이션(memoization)?
컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술로, 동적 계획법의 핵심이 되는 기술이다.

public static int memoFibo(int data) {
	if(data <= 1) {
    	table[data] = 1;
        return 1;
    }
    //0으로 초기화된 테이블의 값이 0이상인 경우 -> 값을 기억한 경우
    if(table[data] > 0) {
    //값이 저장된 경우에는 계산을 하지 않음
    	return table[data];
    }
    //값이 저장되지 않은 경우, 계산 후 저장
    table[data] = memoFibo(data-1) + memoFibo(data-2);
    
    return table[data];
}

예제

링크텍스트