피보나치 수열
이번 연습 문제에서는 자연에서 흔히 볼 수 있는 피보나치 수열을 구현해 보겠습니다. 수열은 "0, 1, 1, 2, 3, 5, 8…"처럼 진행돼요. 이 수열을 생성하는 알고리즘을 재귀로 구현할 것입니다.
처음 두 수는 0과 1이며, 그다음 수들은 바로 앞의 두 수를 더한 값입니다.
이 수열은 재귀적으로 다음과 같이 정의할 수 있습니다: \(fib(n)=fib(n-1)+fib(n-2)\), 단 \(fib(0)=0\), $fib(1)=1$이고, 여기서 $n$은 수열의 $n$번째 위치를 뜻합니다.
첫 단계에서는 재귀를 사용해 피보나치를 코딩합니다. 두 번째 단계에서는 동적 계획법을 사용해 개선하고, 하위 문제의 해를 cache 변수에 저장하세요.
이 연습은 강의의 일부입니다
Python으로 배우는 자료구조와 알고리즘
실습형 인터랙티브 연습
이 예제를 이 샘플 코드를 완성하여 풀어보세요.
def fibonacci(n):
# Define the base case
if ____ <= ____:
return n
else:
# Call recursively to fibonacci
____
print(fibonacci(6))