[코드트리] 재귀함수를 이용한 피보나치 수 /재귀함수

 

 

https://www.codetree.ai/missions/5/problems/fibonacci-using-recursive-function?&utm_source=clipboard&utm_medium=text

재귀함수를 이용한 피보나치 수

---

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

피보나치 수열이란 이전 두 항의 합이 그 다음 항이 되는 수열을 의미합니다.

예를 들어 첫 번째 원소를 1, 두 번째 원소도 1이라 하면 그 다음 항은 2, 3, 5, 8 .. 이 됩니다.

N번째 피보나치 수를 구하는 프로그램을 작성해보세요. 단, 재귀함수를 이용하여 문제를 해결해주세요

 

입력 형식

첫째 줄에는 N이 주어집니다.

• 1 ≤ N ≤ 20

출력 형식

N번째 피보나치 수를 출력합니다.

 

입출력 예제

예제1

입력:

3

출력:

2

 

 

 

 내가 짠 코드

 

---

n = int(input())

def f(n):
    if n ==1:
        return 1
    if n==2:
        return 1
    
    return f(n-1) + f(n-2)

print(f(n))

기본적인 재귀함수 문제이다. 

 

피보나치 수란, 

피보나치 수열이란 이전 두 항의 합이 그 다음 항이 되는 수열을 의미한다.

1, 1, 2, 3, 5, 8, .. 과 같은 수열을 말한다.

 

 

n 을 입력받은후 피보나치 수를 출력해야한다.

이때 베이스 케이스에 주의해야하는데 n==1 이거나 n==2 일 때는 n-1 혹은 n-2 가 0이나 음수가 나와 정의할 수 없기 때문에 따로 정의해야한다. 1,2 일때는 1을 리턴하도록 하고 그게 아닌경우는 n-1 과 n-2 번째 수를 합하도록한다.