Alasan untuk pernyataan kembali dalam panggilan fungsi rekursif

Saya hanya memiliki keraguan dalam pikiran saya. Subrutin berikut (untuk mencari elemen, dalam daftar, misalnya) memiliki pernyataan kembali di akhir:

list *search_list(list *l, item_type x) {
  if (l == NULL) return(NULL);
  if (l->item == x)
    return(l);
  else
    return( search_list(l->next, x) );
}

Saya tidak bisa mendapatkan signifikansi pernyataan pengembalian di akhir (yaitu mengembalikan search_list (l-> selanjutnya, x)). Akan sangat membantu jika ada yang bisa menjelaskan konsep ini, menggunakan model stack.

Pernyataan kembali meneruskan nilai kembali ke penelepon langsung dari kerangka panggilan fungsi saat ini. Dalam kasus rekursi, penelepon langsung ini bisa menjadi doa lain dari fungsi yang sama.

Dalam sebagian besar bahasa, jika Anda tidak menggunakan nilai balik dari fungsi yang Anda panggil (secara rekursif atau tidak), nilai pengembalian itu akan dibuang atau itu adalah kesalahan yang dapat didiagnosis. Ada beberapa bahasa di mana nilai kembali dari panggilan fungsi terakhir secara otomatis digunakan kembali sebagai nilai balik dari pemanggilan fungsi saat ini, tetapi mereka tidak membedakan antara panggilan fungsi normal dan rekursif.

Dengan asumsi nilai pengembalian yang tidak digunakan akan dibuang secara diam-diam, jika Anda telah menulis kode seperti ini:

list *search_list(list *l, item_type x) {
  if (l == NULL) return(NULL);
  if (l->item == x)
    return(l);
  else
    search_list(l->next, x); // no return!
}

maka search_listhanya akan mengembalikan nilai yang ditentukan untuk daftar kosong (NULL) atau jika item pertama cocok dengan nilai yang Anda cari. Segera setelah fungsi masuk ke panggilan rekursif, Anda tidak tahu apa hasilnya nanti, karena hasil panggilan rekursif akan dibuang.

Selain itu, Anda berjanji untuk mengembalikan nilai dari fungsi Anda, tetapi Anda memiliki jalur (yang rekursif) di mana Anda tidak menentukan nilai apa yang akan dikembalikan. Bergantung pada bahasa yang Anda gunakan, ini biasanya menghasilkan diagnostik wajib atau perilaku tidak terdefinisi (yang merupakan singkatan: apa pun bisa terjadi dan yang dapat berubah sewaktu-waktu tanpa pemberitahuan. Jangan pegang orang lain kecuali diri Anda yang bertanggung jawab jika itu mengacaukan presentasi Anda yang paling penting). Ada beberapa situasi di mana nilai pengembalian yang hilang mungkin tampak berfungsi, tetapi itu mungkin berubah saat Anda menjalankan program berikutnya (dengan atau tanpa kompilasi ulang).

Dua hal; Mengembalikan seluruh daftar jika Anda menemukan "x" yang Anda cari tidak selalu menjamin menggunakan rekursi, tetapi selain itu, pertimbangkan hal berikut:

Misalkan Anda mencari nilai X = "Desember", dan daftar Anda adalah nilai numerik dari bulan dalam setahun, sebuah penunjuk ke bulan berikutnya, dan item l-> dalam daftar adalah nama ejaan dari bulan. (Januari, Februari, ..., Desember). Anda membutuhkan tiga pengembalian untuk hasil yang mungkin. Yang pertama, return (NULL) diperlukan jika daftar tidak mengandung X yang Anda cari. Yang kedua, (kembali (l)) mengembalikan daftar, dalam hal ini, memberi tahu Anda bahwa Anda menemukan "x" Anda. Yang terakhir adalah di mana model tumpukan berperan. Panggilan beruntun ke fungsi akan memperbarui variabel lokal (khususnya, l-> item) seperti ini:

1: l->item = January
   returns search_list(l->next, x)
2: l->item = February
   returns search_list(l->next, x)
3-11: March, April, May, June, July, August, September, October, November
   all return search_list(l->next, x)
12: l->item = December
  This matches the second if() and returns your list, letting you know you found your search item.