[파이썬] 재귀함수를 통한 피보나치 수의 구현

피보나치 수

- 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열

※ 편의상 0번째 항을 0으로 두기도 함.

 

예시)

 

 

1) 반복문을 통한 팩토리얼의 구현

 

# 반복문을 통한 피보나치 수 구현

# 입력부
n = int(input())

# 0번째, 1번째 피보나치 수를 포함하는 배열 생성
answer_arr = [0, 1]

# 반복문을 통해 n을 입력받았을 때, 기존 배열에 n번째 피보나치 수까지 추가 
for i in range(n-1):
    
    answer_arr.append(answer_arr[1+i] + answer_arr[i])


# 입력받은 n번째 피보나치 수 출력
print(answer_arr[n])

n = 4인 경우의 출력결과 (4번째 피보나치 수)

 

 

반응형

2) 재귀함수를 통한 팩토리얼의 구현

 

# 재귀함수를 통한 피보나치 수 구현

def Fibonacci(n):
    
# 0번째 피보나치 수는 0임을 밝힘과 동시에 재귀함수 탈출의 기능
    if n == 0:
        return 0
    
# 1번째 피보나치 수는 1임을 밝힘과 동시에 재귀함수 탈출의 기능
    elif n == 1:
        return 1
    
    else:
        value = Fibonacci(n-1) + Fibonacci(n-2)
        return value

# 입력부
n = int(input())

# 입력받은 n번째 피보나치 수 출력
answer = Fibonacci(n)
print('{0}번째 피보나치 수는 {1} 입니다.'.format(n, answer))

n = 4인 경우의 출력결과 (4번째 피보나치 수)

 

 

n = 4인 경우의 재귀함수 모식도

 

 

 

 

 피보나치 수 구현의 경우, 반복문을 사용함으로써 구현 가능하지만,

재귀함수로 피보나치 수를 구현해봄으로써, 재귀함수의 작동에 대해서 공부할 수 있습니다.

 

 재귀함수의 경우에 자연과학 연구, 특정  문제의 모든 경우의 수를 효율적으로 확인하는 백트래킹 메서드(back tracking method), 코딩 테스트 등, 다방면에서 사용되니 작동방법을 명확히 아는 것이 중요하겠습니다.