recursion
-
[Python]피보나치수열 구현 및 방법 비교: 재귀 함수,동적 프로그래밍 활용(Fibonacci numbers, recursion and dynamic programming)프로그래밍/알고리즘 2022. 9. 20. 16:16
이번 글에서는 파이썬 언어로 피보나치수열을 구현합니다. 이때, 재귀함수 및 동적 프로그래밍 방법을 모두 구현하여 실행시간을 비교합니다. 1. 재귀 함수로 구현(Recursion) def Fibo_recursion(n): if n == 0: return 0 elif n == 1: return 1 else: return Fibo_recursion(n-1) + Fibo_recursion(n-2) 2. 동적 프로그래밍으로 구현(Dynamic programming) def Fibo_dynamic(n): arr = [0]*(n+1) arr[1] = 1 for i in range(2,n+1): arr[i] = arr[i-1] + arr[i-2] return arr[n] 3. 실행시간 비교 # 재귀함수 실행 start..