어떠한 재귀 문제(Recursive Problem)도 해결할 수 있는 5가지 단계(Steps)

  해외 사이트에서 재귀 문제나 다이나믹 프로그래밍 문제를 공부할 때 좋은 교육용 자료를 찾아서 공유한다.

 

  ▶ 어떠한 재귀 문제도 해결할 수 있는 5가지 단계: https://www.youtube.com/watch?v=ngCos392W4w 

 

  ▶ 예시 문제: 피보나치(Fibonacci) 수열

 

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

 

[1단계] What's the simplest possible input? (가장 간단한, 가능한 입력은 무엇인가?)

 

  가장 간단한 형태의 입력을 선택하면 된다. f(0) = 0, f(1) = 1로 볼 수 있다.

 

[2단계] Play around with examples and visualize! (다양한 예제를 그려보며 놀기!)

 

  규칙을 찾기 위해서 다양한 예제를 그려보며 노는 것이 중요하다.

 

[3단계] Relate hard cases to simpler cases (어려운 문제와 쉬운 문제를 연결 짓기)

 

  재귀 문제의 가장 큰 특징은, 하나의 어려운 문제를 해결하기 위해 쉬운 문제를 조합해야 한다는 것이다. 예를 들어 피보나치 수열은 f(x) = f(x - 1) + f(x - 2)가 성립한다. 다시 말해 하나의 어려운 문제 입장에서는 자기보다 쉬운 2개의 문제를 해결하면, 자기 자신을 해결할 수 있다는 것을 의미한다.

 

[4단계] Generalize the pattern (패턴을 일반화하기)

 

  f(x) = f(x - 1) + f(x - 2)가 정당하다는 것을 확인하고, f(x) = f(x - 1) + f(x - 2) 형태로 일반항을 정의한다. 이때 초기 항은 f(0) = 0, f(1) = 1이다.

 

[5단계] Write code by combining recursive patterns with the base case (코드로 옮기기)

 

  이후에 해당 점화식을 다음과 같이 코드로 옮기면 된다.

 

def fibo(x):
    if x == 0 or x == 1:
        return x
    else:
        return fibo(x - 1) + fibo(x - 2)

print(fibo(10))