📌 구해야 하는 정답

N번째 피보나치 수를 구하는 문제입니다.

📌 풀이 하기

1️⃣ N번째 피보나치 수를 어떻게 구할 수 있을까?

N번째 피보나치 수를 어떻게 구할 수 있을까요?

1. 재귀 함수를 이용해 탐색하기

재귀 함수로 피보나치수를 구하는 방법은 아주 간단합니다.

return f(n) = f(n-1) + f(n-2)

이 식 하나면 해결됩니다.

하지만 이렇게 계산한다면 N이 커질 수록 N번째 피보나치수를 구하기 위해 호출해야 하는 함수의 회수는 기하급수적으로 증가합니다.

3번째 피보나치 구하기

f(3)
|- f(2)
|  |- f(1)
|  |- f(0)
|- f(1)

# 총 5번 호출

4번째 피보나치 구하기

f(4)
|- f(3)
|  |- f(2)
|  |  |- f(1)
|  |  |- f(0)
|  |- f(1)
|- f(2)
|  |- f(1)
|  |- f(0)

# 총 9번

5번째 피보나치 구하기

f(5)
|- f(4)
|  |- f(3)
|  |  |- f(2)
|  |  |  |- f(1)
|  |  |  |- f(0)
|  |  |- f(1)
|  |- f(2)
|  |  |- f(1)
|  |  |- f(0)
|- f(3)
|  |- f(2)
|  |  |- f(1)
|  |  |- f(0)
|  |- f(1)

# 총 15번

이런식으로 N이 커질 수록 점점 호출해야 하는 함수의 횟수가 증가합니다.