재귀 알고리즘 상향식/하향식 분석 방법(with 피보나치수열)

목차

---

1. 재귀 함수 분석 방법

2. 피보나치 수열 문제를 통한 예시

2-1. 하향식 분석

2-2. 상향식 분석

---

 

 1.  재귀 함수 분석 방법

재귀 함수의 분석 방법에는 1. 하향식 분석과 2. 상향식 분석 두 가지가 있다.

하향식 분석은 마지막에 종료되는 부분에서 반대로 이동하는 분석법이다.(콜스택의 가장 아랫부분)

상향식 분석은 가장 먼저 종료되는 부분에서 반대로 이동하는 분석법이고(콜스택의 가장 윗부분)

 

자세한 것은 아래 예시를 통해 설명한다.

---

 2.  피보나치수열 문제를 통한 예시

private static int fibonacci(int n){
    // 0, 1, 1, 2, 3, 5
    if(n >= 2){
        int result = fibonacci(n-1) + fibonacci(n-2);
        return result;
    } else{
        return n;
    }
}

 

 

우선 위의 예시는 자바 코드를 통해 피보나치 수열을 재귀적으로 구현한 것이며, 최초 fibonacci(5)을 실행하였다.

 

2-1. 하향식 분석

 

빨간 숫자는 실제 해당 함수의 리턴 값

 

설명

1. 위에서 아래로 호출 순서를 표현하며, 왼쪽 아래에서부터 리턴 되며 위로 올라가는 구조이다.
2. fibonacci(n-1) 이 먼저 호출되므로 왼쪽 부분이 n-1 오른쪽 부분이 n-2로 표현된다.

 

주관적인 장단점

1. 직접 하향식 트리를 그려보니 디버깅을 할 필요없이 콜 스택의 구조와 호출 순서, 종료 순서가 한눈에 파악 됐다.
2. 알고리즘 코드가 완성된 후에야 어떤식으로 진행이 되는지 한눈에 볼 수 있어 좋지만 만드는 과정에서는 무슨 소용인가 싶었다.

 

 

 

2-2. 상향식 분석

f(0) = 0
f(1) = 1
f(2) = f(1) + f(0) = 1
f(3) = f(2) + f(1) = 1 + 1 = 2
f(4) = f(3) + f(2) = 2 + 1 = 3
f(5) = f(4) + f(3) = 3 + 2 = 5

 

설명

1. 실행 순서의 맨 마지막(콜 스택의 최상단)에서 위로 가는 과정을 분석하는 방법
2. 위부터 리턴되어 아래로 가기 때문에 아래에서 호출한 함수의 리턴 값은 바로 위의 값이 된다. 

 

 

주관적인 장단점

1 .위에서부터 종료가 되기 때문에 아래에서 사용된 함수의 리턴 값이 자연스럽게 대입이 되어 결과 도출이 편함.
2. 하향식과 달리 함수의 실행 과정은 유추하기 어렵다.
3. 문제의 재귀 조건과 종료 조건을 대략 도출하였다면 해당 분석을 통해 빠르게 검증 할 수 있기 때문에
    알고리즘 문제를 푸는 과정에서는 하향식보다 상향식이 나은 것 같다.

 

---

 글을 마치며

 

상향식/하향식 분석을 직접 해보니 재귀 알고리즘에 대한 이해도가 올라가긴 했지만,

막상 문제를 풀 때 재귀 조건과 종료 조건을 구하는 것에는 도움이 되지 못하는 거 같다..

 

어떻게 해야 재귀 알고리즘을 짤 때 재귀 조건과 종료 조건을 잘 구할 수 있을까 고민이다.
당연히 많은 문제를 풀다 보면 도움이 되겠지만. 아직까지는 항상 재귀 조건과 종료 조건이 유추되지 않아 답답하다😢