Menggunakan ruang tambahan untuk fungsi rekursif dalam program C?

王林
Lepaskan: 2023-09-05 10:01:06
ke hadapan
1087 orang telah melayarinya

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);
}
Salin selepas log masuk

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)
Salin selepas log masuk

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!

Label berkaitan:
sumber:tutorialspoint.com
Kenyataan Laman Web ini
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn
Tutorial Popular
Lagi>
Muat turun terkini
Lagi>
kesan web
Kod sumber laman web
Bahan laman web
Templat hujung hadapan