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 merupakan bagian dari kursus
Struktur Data dan Algoritma di Python
Latihan interaktif langsung praktik
Cobalah latihan ini dengan melengkapi kode contoh ini.
def fibonacci(n):
# Define the base case
if ____ <= ____:
return n
else:
# Call recursively to fibonacci
____
print(fibonacci(6))