Deret Fibonacci
Pada latihan ini, Anda akan mengimplementasikan deret Fibonacci, yang banyak dijumpai di alam. Deretnya terlihat seperti ini: "0, 1, 1, 2, 3, 5, 8…". Anda akan membuat implementasi rekursif dari algoritma yang menghasilkan deret tersebut.
Dua angka pertama adalah 0 dan 1, dan sisanya merupakan penjumlahan dari dua angka sebelumnya.
Kita dapat mendefinisikan deret ini secara rekursif sebagai: \(fib(n)=fib(n-1)+fib(n-2)\), dengan \(fib(0)=0\) dan \(fib(1)=1\), di mana \(n\) adalah posisi ke-\(n\) dalam deret.
Pada langkah pertama, Anda akan menulis kode Fibonacci menggunakan rekursi. Pada langkah kedua, Anda akan meningkatkannya dengan menggunakan pemrograman dinamis, menyimpan solusi submasalah dalam variabel cache.
Latihan ini adalah bagian dari kursus
Struktur Data dan Algoritma di Python
Latihan interaktif praktis
Cobalah latihan ini dengan menyelesaikan kode contoh berikut.
def fibonacci(n):
# Define the base case
if ____ <= ____:
return n
else:
# Call recursively to fibonacci
____
print(fibonacci(6))