[파이썬 기초] 알고리즘의 개념 / 코딩 연습 - 예제4(재귀함수 연습 - 피보나치 수열)

# 재귀 함수(recursive function)  : 자기 자신을 호출하는 함수(반복문은 없음)

   (improvemyself.tistory.com/82?category=849184)

[파이썬 기초] 알고리즘의 개념 / 코딩 연습 - 재귀함수의 개념(카운트다운 함수, 팩토리얼 함수)

# 피보나치 수열 : 첫 번째 항과 두 번째 항이 1이고, 세 번째 항부터는 바로 앞의 두 항의 합으로 정의된 수열       
   → 1, 1, 2, 3, 5, 8, 13 21, 34, 55,,, 

 

코드잇 예제풀이(재귀함수 문제) : 파라미터로 1 이상의 자연수 n을 받고, n번째 피보나치 수를 리턴하는 재귀 함수 fib를 작성(조건 : 반복문 사용하지 말것)

 

Hint 1 : 재귀함수의 recursive case와 base case를 구분 : 여기서 base case는 인풋 n의 값이 2 이하(또는 3 미만)(1,2)일 때임(리턴 값 = 1) 그 외는 recursive case

 

Hint 2 : n항까지의 수열을 출력한다고 하면 출력 범위는 fib(1)부터 fib(n)

 

==========================================================

 

# n번째 피보나치 수를 리턴

def fib(n) :

    # base case

    if n<=2 :

       return 1

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

 

# 테스트 : fib(1)부터 fib(10)까지 출력

for i in range(1,11)

    print(fib(i))

 

1

1

2

3

5

8

13

21

34

55