Menggunakan ruang tambahan untuk fungsi rekursif dalam program C?

Di sini kita akan melihat bagaimana panggilan fungsi rekursif memerlukan ruang tambahan. Bagaimanakah ia berbeza daripada panggilan fungsi biasa?

Andaikan kita mempunyai fungsi seperti yang ditunjukkan di bawah -

long fact(int n){
   if(n == 0 || n == 1)
      return 1;
   return n * fact(n-1);
}

Fungsi ini adalah fungsi rekursif. Apabila kita memanggilnya seperti fakta(5), ia akan menyimpan alamat di dalam tindanan seperti yang ditunjukkan di bawah -

fact(5) --->
fact(4) --->
fact(3) --->
fact(2) --->
fact(1)

Apabila fungsi rekursif memanggil dirinya berulang kali, alamat itu ditambahkan pada tindanan. Oleh itu, jika fungsi dipanggil secara rekursif n kali, ia akan menduduki ruang tambahan O(n). Tetapi ini tidak bermakna jika fungsi normal dipanggil n kali, kerumitan ruang akan menjadi O(n). Untuk fungsi biasa, alamat ditolak ke tindanan apabila dipanggil. Setelah selesai, alamat akan muncul dari timbunan dan dimasukkan ke dalam fungsi pemanggil. Kemudian telefon semula. Jadi kerumitannya ialah O(1).

Atas ialah kandungan terperinci Menggunakan ruang tambahan untuk fungsi rekursif dalam program C?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!