Không gian bổ trợ với các hàm đệ quy trong chương trình C?

Ở đây chúng ta sẽ xem không gian phụ được yêu cầu như thế nào đối với lệnh gọi hàm đệ quy. Và nó khác với lệnh gọi hàm thông thường như thế nào?

Giả sử chúng ta có một chức năng như bên dưới -

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

Hàm này là hàm đệ quy. Khi chúng ta gọi nó như fact (5), thì nó sẽ lưu trữ các địa chỉ bên trong ngăn xếp như bên dưới -

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

Khi các hàm đệ quy đang gọi đi gọi lại chính nó, các địa chỉ được thêm vào ngăn xếp. Vì vậy, nếu hàm được gọi n lần một cách đệ quy, nó sẽ chiếm O (n) không gian phụ. Nhưng điều đó không có nghĩa là nếu một hàm bình thường được gọi n lần, thì độ phức tạp không gian sẽ là O (n). Đối với hàm bình thường khi nó được gọi, địa chỉ được đẩy vào ngăn xếp. Sau đó, khi nó hoàn thành, nó sẽ bật địa chỉ từ ngăn xếp và đi vào chức năng invoker. Sau đó gọi lại. Vì vậy, nó sẽ là O (1).