Simulic
Bahasa Indonesia

Rekursi – tumpukan panggilan dan pohon panggilan

InformatikaAlgoritma dan pemecahan masalahUsia 17–18

Memuat…

Gunakan di kelas saya ✨ Sesuaikan dengan AI Laporkan masalah

Jalankan langkah demi langkah fungsi rekursif – faktorial, Fibonacci, jumlah isi list, pencarian biner, teka-teki menara cakram, dan merge sort – lalu lihat tumpukan panggilan bertambah dan berkurang sementara pohon panggilan mencatat setiap panggilan, kasus dasar, dan nilai kembalian. Bandingkan Fibonacci rekursif biasa dengan memoisasi dan dengan perulangan, hapus kasus dasar untuk memicu stack overflow, dan baca kodenya dalam Python atau pseudokode.

Pelajaran: Rekursi: kasus dasar, tumpukan panggilan, divide and conquer, memoisasi, rekursi dibandingkan iterasi

Yang ditunjukkan

Fungsi rekursif menyelesaikan masalah dengan memanggil dirinya sendiri pada versi masalah yang lebih kecil. Setiap panggilan menaruh bingkai baru di tumpukan panggilan; kasus dasar mengembalikan nilai tanpa memanggil lagi, lalu bingkai-bingkai diambil kembali sambil nilai dikirim ke atas. Pohon panggilan menampilkan semua panggilan: faktorial dan jumlah list membentuk satu rantai, sedangkan Fibonacci, merge sort, dan menara bercabang. Fibonacci biasa mengulang panggilan yang sama sehingga jumlahnya tumbuh eksponensial; memoisasi menyimpan hasilnya. Tanpa kasus dasar, tumpukan meluap.

Cara menggunakan

Pilih Fungsi dan atur n (atau Target untuk pencarian biner). Tekan Langkah untuk menjalankan satu panggilan atau pengembalian, Mundur untuk membatalkan satu langkah, atau Jalankan untuk memutar pada Kecepatan yang dipilih. Amati kode, tumpukan, dan pohon; ketuk sebuah simpul untuk detailnya. Centang Memo untuk Fibonacci atau hapus centang Dengan kasus dasar untuk melihat stack overflow.

Parameter yang dapat diubah

  • Fungsi rekursif Faktorial n!, Bilangan Fibonacci, Jumlah isi list, Pencarian biner, Menara cakram (teka-teki), Merge sort
  • n (ukuran masalah) 0–8
  • Nilai yang dicari (pencarian biner) 0–100
  • Memoisasi (Fibonacci)
  • Sertakan kasus dasar
  • Bahasa Python, Pseudokode
  • Kecepatan 0,5–10 langkah/s

Pertanyaan untuk dijelajahi

  1. Berapa kali fib(2) dipanggil saat menghitung fib(6) tanpa memoisasi, dan berapa kali dengan memoisasi?
  2. Berapa kedalaman tumpukan maksimum untuk factorial(5), dan berapa tumpukan yang dibutuhkan versi perulangan?
  3. Mengapa menghapus kasus dasar menyebabkan stack overflow, bukan jawaban yang salah?

Simulasi terkait