编译器如何理解递归？

Question

在使用c和python进行编程时,我已经使用递归进行了验证,并且我猜它也用于许多其他语言,但编译器如何实际解释递归函数？它如何在它自己的定义中使用该函数？

Answer 1

但编译器如何实际解释递归函数？它如何在它自己的定义中使用该函数？

要理解这一点,您只需了解编译器如何解释函数.对于C,该函数只是一个符号,或指向内存中入口地址的指针.直观但不严格,函数调用将编译为这样的汇编指令:

CALL address_of_function

看到？编译器不需要知道函数是否是递归的.它只是让CPU跳转到函数入口的地址并继续执行指令.

这就是为什么我们可以使用该功能,即使它的定义没有完成.编译器只需知道起始地址或符号,然后它就会知道跳转的位置.稍后可以生成函数体.

但是,您可能想知道Tail Recursion,这是函数式编程语言中常见的特殊情况."尾递归"表示递归函数调用是函数定义中的最后一个语句.正如@ paulsm4所提到的,在调用函数时,编译器需要将上下文和参数推送到堆栈中,然后恢复上下文并从中获取返回值.因此,如果你的函数调用自身然后调用它自己......,那么在内存耗尽之前,堆栈会太深.但是如果函数调用是函数定义中的最后一个语句,那么就没有必要在堆栈中保存上下文,我们只能覆盖它.因此,即使函数无限地调用自身,堆栈也不会溢出.