Không gian phụ với hàm đệ quy trong C

Phân tích không gian phụ (auxiliary space) của hàm đệ quy so với hàm thường.

Ví dụ hàm giai thừa đệ quy:

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

Gọi fact(5) -> stack: fact(5) -> fact(4) -> fact(3) -> fact(2) -> fact(1).

Mỗi lời gọi đệ quy đẩy địa chỉ vào stack -> O(n) không gian phụ.

Hàm thường gọi n lần: địa chỉ push/pop luân phiên -> O(1) không gian phụ.