더북(TheBook)

6.7 재귀, 하나 더(2)

factorial 다음으로 재귀적으로 정의된 수학 함수로 가장 흔한 예제는 fibonacci가 있으며, fibonacci는 다음과 같이 정의된다(자세한 내용은 https://ko.wikipedia.org/wiki/피보나치_수를 참조하자).

fibonacci(0) = 0

fibonacci(1) = 1

fibonacci(n) = fibonacci(n - 1) + fibonacci(n - 2)

파이썬으로 바꾸면 이런 모습이 된다.

def fibonacci (n):

if n == 0:

return 0

elif n == 1:

return 1

else:

return fibonacci(n-1) + fibonacci(n-2)

여기서 실행 흐름을 따라가 보려고 한다면 아무리 작은 n값이라도 머리가 터져버릴 것이다. 여기서는 믿음의 도약에 따라 두 개의 재귀 호출이 올바르게 동작한다고 가정하고, 두 재귀 호출을 더하면 올바를 결과를 얻을 수 있다고 이해하자.

신간 소식 구독하기
뉴스레터에 가입하시고 이메일로 신간 소식을 받아 보세요.