นี่คือการดูว่าพื้นที่ช่วยเหลือ (auxiliary space) สำหรับการเรียกฟังก์ชันเรียกซ้ำต้องการเท่าไร และแตกต่างจากการเรียกฟังก์ชันปกติอย่างไร
สมมติมีฟังก์ชันดังนี้:
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) สำหรับฟังก์ชันปกติ เมื่อถูกเรียก ที่อยู่จะถูก push เข้าสแต็ก หลังเสร็จจะ pop ออกและกลับไปยังฟังก์ชันเรียก แล้วเรียกใหม่ ดังนั้นเป็น O(1)
