재귀함수 사용시 시간을 단축시키는 방법

💡 재귀함수
재귀함수란 자기 자신을 호출하는 함수를 말합니다.
ex) 피보나치 수열

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

하지만 재귀함수를 사용하다보면 시간복잡도가 너무 높아질때가 있습니다.
위의 예시에 나온 피보나치 수열의 시간복잡도는 O(2^n)입니다.

메모이제이션을 사용하면 위와 같은 경우에 시간복잡도를 줄일 수 있습니다.

💡 메모이제이션
메모이제이션은 한 번 계산된 결과를 저장해 두고, 같은 입력이 다시 주어졌을 때는 저장된 값을 반환하도록 하여 불필요한 중복 계산을 방지합니다.

• 동적 계획법(DP)의 한 기법으로, 중복된 계산을 피하는 방식입니다.

피보나치 수열을 메모이제이션을 이용하여 다시 구현해보겠습니다.

public int fibonacci(int n, int[] memo) {
    if (n <= 1) {
        return n;
    }
    
    if (memo[n] != -1) {
        return memo[n]; // 이미 계산된 값 반환
    }
    
    memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo); // 값 계산 후 저장
    return memo[n];
}

위의 코드는 각 피보나치 수를 한 번만 계산하고, 계산된 값을 배열에 저장해 중복 계산을 피합니다. 결과적으로, 시간 복잡도는 O(n)으로 줄어듭니다.