[Recursive Function] 피보나치 수열

코드잇 강의를 통해 알고리즘에 대해 공부하며 배운 내용들을 기록한 글입니다.

---

문제 설명

피보나치 수열이란 첫 번째 항과 두 번째 항이 1이고, 세 번째 항부터는 바로 앞의 두 항의 합으로 정의된 수열이다.
예를 들어서 세 번째 항은 첫 번째 항($1$)과 두 번째 항($1$)을 더한 $2$이며, 네 번째 항은 두 번째 항($1$)과 세 번째 항($2$)를 더한 $3$이 될 것이다.
이러한 방식으로 피보나치 수열의 첫 $10$개 항은 $1$,$1$,$2$,$3$,$5$,$8$,$13$,$21$,$34$,$55$이다.
파라미터로 $1$ 이상의 자연수 n을 받고, $n$번째 피보나치 수를 리턴하는 재귀 함수 fib를 써라.
단, 반복문은 쓰면 안된다!

# n번째 피보나치 수를 리턴
def fib(n):
    # 여기에 코드를 작성하세요

# 테스트 코드: fib(1)부터 fib(10)까지 출력
for i in range(1, 11):
    print(fib(i))

1
1
2
3
5
8
13
21
34
55

---

나의 풀이

# n번째 피보나치 수를 리턴
def fib(n):
    if n == 1 or n == 2:
        return 1
    else:
        return (fib(n-1) + fib(n-2))
    
# 테스트 코드: fib(1)부터 fib(10)까지 출력
for i in range(1, 11):
    print(fib(i))

나는 우선 피보나치 수열의 첫 번째 항과 두 번째 항은 항상 1이기 때문에, 조건문을 사용해서 n이 1일 때와 2일 때는 1을 리턴하도록 하였다.

def fib(n):
    if n == 1 or n == 2:
        return 1

예를 들어, 5번째 항은 4번째 항과 3번째 항의 합이다.
즉, n이 5면, fib(4)와 fib(3)을 더해주면 되는데, 이것을 일반화하면 fib(n - 1)과 fib(n - 2)를 더하는 것이다.

따라서 n이 1이나 2가 아닐 경우,
fib(n - 1)과 fib(n - 2)를 더한 결과를 리턴해주면 된다.