C语言程序中具有递归函数的辅助空间?
在这里,我们将看到递归函数调用如何需要辅助空间。它与正常的函数调用有何不同?
假设我们有一个像下面的功能-
long fact(int n){ if(n == 0 || n == 1) return 1; return n * fact(n-1); }
此函数是递归函数。当我们像事实(5)那样调用它时,它将在堆栈内存储地址,如下所示:
fact(5) ---> fact(4) ---> fact(3) ---> fact(2) ---> fact(1)
随着递归函数一次又一次地调用自身,地址被添加到堆栈中。因此,如果函数被递归调用n次,它将占用O(n)个辅助空间。但这并不意味着如果一个正常函数被调用n次,则空间复杂度将为O(n)。对于正常功能,当其被调用时,地址被压入堆栈。之后,当它完成时,它将从堆栈中弹出地址并进入调用程序函数。然后再次致电。因此它将是O(1)。