ที่นี่เราจะมาดูกันว่าจำเป็นต้องใช้พื้นที่เสริมสำหรับการเรียกใช้ฟังก์ชันแบบเรียกซ้ำอย่างไร และต่างจากการเรียกใช้ฟังก์ชันปกติอย่างไร
สมมติว่าเรามีฟังก์ชันหนึ่งดังนี้ -
long fact(int n){
if(n == 0 || n == 1)
return 1;
return n * fact(n-1);
} ฟังก์ชันนี้เป็นฟังก์ชันแบบเรียกซ้ำ เมื่อเราเรียกมันว่า fact(5) มันจะเก็บที่อยู่ในสแต็กด้านล่าง -
fact(5) ---> fact(4) ---> fact(3) ---> fact(2) ---> fact(1)
เนื่องจากฟังก์ชันเรียกซ้ำเรียกตัวเองซ้ำแล้วซ้ำอีก ที่อยู่จะถูกเพิ่มลงในสแต็ก ดังนั้นหากฟังก์ชันถูกเรียกซ้ำ n ครั้ง มันจะใช้ช่องว่างเสริม O(n) แต่นั่นไม่ได้หมายความว่าถ้าฟังก์ชันปกติหนึ่งฟังก์ชันถูกเรียก n ครั้ง ความซับซ้อนของสเปซจะเป็น O(n) สำหรับฟังก์ชันปกติเมื่อมีการเรียก ที่อยู่จะถูกผลักเข้าไปในสแต็ก เสร็จแล้วจะเด้ง address จาก stack มาที่ invoker function แล้วโทรใหม่ ดังนั้นมันจะเป็น O(1).
