一个函数怎么可能调用自己
How is it possible that a function can call itself
我知道递归，但我不知道它是如何实现的。我将使用下面的示例来进一步解释我的问题。
(def (pow (x, y))
(cond ((y = 0) 1))
(x * (pow (x , y-1))))
上面的程序是Lisp语言的。我不确定语法是否正确，因为我在脑海中想出了它，但它会的。在程序中，我定义了函数 pow，在 pow 中它调用了自己。我不明白它是如何做到这一点的。据我所知，计算机必须在定义功能之前对其进行完整分析。如果是这样的话，那么我用pow的时候电脑应该会给出一个undefined的信息，因为我在定义之前就用过了。我描述的原理是当您在 x = x + 1 中使用 x 时起作用的原理，而 x 之前未定义。
编译器比你想象的要聪明得多。
编译器可以在这个定义中转递归调用：
(defun pow (x y)
(cond ((zerop y) 1)
(t (* x (pow x (1- y))))))
进入 goto 指令以从头开始重新启动函数：
Disassembly of function POW
(CONST 0) = 1
2 required arguments
0 optional arguments
No rest parameter
No keyword parameters
12 byte-code instructions:
0 L0
0 (LOAD&PUSH 1)
1 (CALLS2&JMPIF 172 L15) ; ZEROP
4 (LOAD&PUSH 2)
5 (LOAD&PUSH 3)
6 (LOAD&DEC&PUSH 3)
8 (JSR&PUSH L0)
10 (CALLSR 2 57) ; *
13 (SKIP&RET 3)
15 L15
15 (CONST 0) ; 1
16 (SKIP&RET 3)
如果这是编译器无法展开到循环中的更复杂的递归函数，它只会再次调用该函数。
From what I know the computer has to completely analyze a function before it can be defined.
当编译器看到定义了一个函数POW，然后它告诉自己：现在我们正在定义函数POW。如果它随后在定义中看到对 POW 的调用，那么编译器会对自己说：哦，这似乎是对我当前正在编译的函数的调用，然后它可以创建代码来进行递归调用。
一个函数就是一段代码。它的名称只是帮助，因此您不必计算它将最终到达的确切地址。编程语言会将名称转换为程序要执行的位置。
一个函数调用另一个函数的方式是将本函数中下一条命令的地址存入栈中，或者在栈中添加参数，然后跳转到函数的地址位置。该函数本身跳转到它找到的 return 地址，以便控制返回给被调用者。语言实现了几种调用约定，在哪一边做什么。 CPU 并没有真正的函数支持，所以就像在 CPU 中没有所谓的 while 循环一样，函数被模拟了。
就像函数有名字一样，参数也有名字，但它们只是指针，就像 return 地址一样。当调用自身时，它只是将一个新的 return 地址和参数添加到堆栈上并跳转到自身。堆栈的顶部将不同，因此相同的变量名称是调用的唯一地址，因此上一次调用中的 x 和 y 不同于当前的 x 和 y。事实上，与调用其他任何东西相比，调用自身不需要特殊处理。
从历史上看，第一个高级语言 Fortran 不支持递归。它会调用自己，但是当它 returned 时，它 returned 到原始被调用者，而没有在自我调用后执行其余功能。如果没有递归，Fortran 本身就不可能编写，因此虽然它自己使用递归，但它并没有将它提供给使用它的程序员。这种局限性是 John McCarthy 发现 Lisp 的原因。
我想看看这是如何工作的通常，特别是在递归调用不能的情况下循环，值得考虑通用编译语言如何工作，因为问题没有什么不同。
让我们想象一下编译器如何将此函数转换为机器代码：
(defun foo (x)
(+ x (bar x)))
并且假设它在编译时对 bar 一无所知。好吧，它有两个选项。
- 它可以编译
foo 的方式使得对 bar 的调用被翻译成一组指令，即 'look up the function definition stored under the name bar, whatever it currently is, and arrange to call that function with the right arguments'.
- 它可以编译
foo 以这样的方式存在对函数的机器级函数调用，但该函数的地址保留为某种占位符。然后它可以将一些元数据附加到 foo 上，上面写着：'在调用此函数之前，您需要找到名为 bar 的函数，找到它的地址，将其拼接到正确位置的代码中，并删除此元数据。
这两种机制都允许在知道 bar 是什么之前定义 foo。请注意，我可以写 foo 而不是 bar：这些机制也处理递归调用。然而，它们与此不同。
- 第一种机制意味着，每次调用
foo 时都需要对 bar 进行某种动态查找，这将涉及一些开销（但这种开销可能非常小）：
- 因此，第一个机制将比它可能的速度稍慢；
- 但是，也因此，如果
bar 被重新定义，那么新定义将被采用，这对于交互式语言来说是非常可取的事情，而 Lisp 实现通常是这样。
- 第二种机制意味着，在
foo 将其对其他函数的所有引用 link 编辑到其中之后，调用发生在机器级别：
- 这意味着他们会很快；
- 但是重新定义充其量会更加复杂，或者在最坏的情况下根本不可能。
第二个实现与传统编译器编译代码的方式很接近：它们编译代码时留下一堆占位符和相关的元数据，说明这些占位符对应的名称。 linker（有时称为 link-loader 或 loader）然后遍历编译器生成的所有文件以及其他库代码并解析所有这些引用，导致一些代码实际上可以是 运行.
一个头脑简单的 Lisp 系统可能完全通过第一种机制工作（例如，我很确定 Python 就是这样工作的）。更高级的编译器可能会通过第一种和第二种机制的某种组合来工作。例如，CL 允许编译器假设函数中明显的自调用实际上是 是 自调用，因此编译器可以将它们编译为直接调用（本质上它将编译该函数，然后 link 即时编译它）。但是一般编译代码的时候，可能会调用函数的'through the name'。
事情也有一些或多或少的英雄策略：例如在函数的第一次调用时 link 它，在运行中，对它所指的所有事物，并注意在 他们的 定义中，如果他们改变了，那么这件事也需要取消 link，这样一切都会再次发生。这些技巧曾经看起来难以置信，但像 JavaScript 这样的语言的编译器现在至少一直在做这样的事情。
请注意，现代系统的编译器和 linker 实际上做的事情比我描述的要复杂，因为共享库 &c：我描述的或多或少是共享库之前发生的事情.
我知道递归，但我不知道它是如何实现的。我将使用下面的示例来进一步解释我的问题。
(def (pow (x, y))
(cond ((y = 0) 1))
(x * (pow (x , y-1))))
上面的程序是Lisp语言的。我不确定语法是否正确，因为我在脑海中想出了它，但它会的。在程序中，我定义了函数 pow，在 pow 中它调用了自己。我不明白它是如何做到这一点的。据我所知，计算机必须在定义功能之前对其进行完整分析。如果是这样的话，那么我用pow的时候电脑应该会给出一个undefined的信息，因为我在定义之前就用过了。我描述的原理是当您在 x = x + 1 中使用 x 时起作用的原理，而 x 之前未定义。
编译器比你想象的要聪明得多。 编译器可以在这个定义中转递归调用：
(defun pow (x y)
(cond ((zerop y) 1)
(t (* x (pow x (1- y))))))
进入 goto 指令以从头开始重新启动函数：
Disassembly of function POW
(CONST 0) = 1
2 required arguments
0 optional arguments
No rest parameter
No keyword parameters
12 byte-code instructions:
0 L0
0 (LOAD&PUSH 1)
1 (CALLS2&JMPIF 172 L15) ; ZEROP
4 (LOAD&PUSH 2)
5 (LOAD&PUSH 3)
6 (LOAD&DEC&PUSH 3)
8 (JSR&PUSH L0)
10 (CALLSR 2 57) ; *
13 (SKIP&RET 3)
15 L15
15 (CONST 0) ; 1
16 (SKIP&RET 3)
如果这是编译器无法展开到循环中的更复杂的递归函数，它只会再次调用该函数。
From what I know the computer has to completely analyze a function before it can be defined.
当编译器看到定义了一个函数POW，然后它告诉自己：现在我们正在定义函数POW。如果它随后在定义中看到对 POW 的调用，那么编译器会对自己说：哦，这似乎是对我当前正在编译的函数的调用，然后它可以创建代码来进行递归调用。
一个函数就是一段代码。它的名称只是帮助，因此您不必计算它将最终到达的确切地址。编程语言会将名称转换为程序要执行的位置。
一个函数调用另一个函数的方式是将本函数中下一条命令的地址存入栈中，或者在栈中添加参数，然后跳转到函数的地址位置。该函数本身跳转到它找到的 return 地址，以便控制返回给被调用者。语言实现了几种调用约定，在哪一边做什么。 CPU 并没有真正的函数支持，所以就像在 CPU 中没有所谓的 while 循环一样，函数被模拟了。
就像函数有名字一样，参数也有名字，但它们只是指针，就像 return 地址一样。当调用自身时，它只是将一个新的 return 地址和参数添加到堆栈上并跳转到自身。堆栈的顶部将不同，因此相同的变量名称是调用的唯一地址，因此上一次调用中的 x 和 y 不同于当前的 x 和 y。事实上，与调用其他任何东西相比，调用自身不需要特殊处理。
从历史上看，第一个高级语言 Fortran 不支持递归。它会调用自己，但是当它 returned 时，它 returned 到原始被调用者，而没有在自我调用后执行其余功能。如果没有递归，Fortran 本身就不可能编写，因此虽然它自己使用递归，但它并没有将它提供给使用它的程序员。这种局限性是 John McCarthy 发现 Lisp 的原因。
我想看看这是如何工作的通常，特别是在递归调用不能的情况下循环，值得考虑通用编译语言如何工作，因为问题没有什么不同。
让我们想象一下编译器如何将此函数转换为机器代码：
(defun foo (x)
(+ x (bar x)))
并且假设它在编译时对 bar 一无所知。好吧，它有两个选项。
- 它可以编译
foo的方式使得对bar的调用被翻译成一组指令，即 'look up the function definition stored under the namebar, whatever it currently is, and arrange to call that function with the right arguments'. - 它可以编译
foo以这样的方式存在对函数的机器级函数调用，但该函数的地址保留为某种占位符。然后它可以将一些元数据附加到foo上，上面写着：'在调用此函数之前，您需要找到名为bar的函数，找到它的地址，将其拼接到正确位置的代码中，并删除此元数据。
这两种机制都允许在知道 bar 是什么之前定义 foo。请注意，我可以写 foo 而不是 bar：这些机制也处理递归调用。然而，它们与此不同。
- 第一种机制意味着，每次调用
foo时都需要对bar进行某种动态查找，这将涉及一些开销（但这种开销可能非常小）：- 因此，第一个机制将比它可能的速度稍慢；
- 但是，也因此，如果
bar被重新定义，那么新定义将被采用，这对于交互式语言来说是非常可取的事情，而 Lisp 实现通常是这样。
- 第二种机制意味着，在
foo将其对其他函数的所有引用 link 编辑到其中之后，调用发生在机器级别：- 这意味着他们会很快；
- 但是重新定义充其量会更加复杂，或者在最坏的情况下根本不可能。
第二个实现与传统编译器编译代码的方式很接近：它们编译代码时留下一堆占位符和相关的元数据，说明这些占位符对应的名称。 linker（有时称为 link-loader 或 loader）然后遍历编译器生成的所有文件以及其他库代码并解析所有这些引用，导致一些代码实际上可以是 运行.
一个头脑简单的 Lisp 系统可能完全通过第一种机制工作（例如，我很确定 Python 就是这样工作的）。更高级的编译器可能会通过第一种和第二种机制的某种组合来工作。例如，CL 允许编译器假设函数中明显的自调用实际上是 是 自调用，因此编译器可以将它们编译为直接调用（本质上它将编译该函数，然后 link 即时编译它）。但是一般编译代码的时候，可能会调用函数的'through the name'。
事情也有一些或多或少的英雄策略：例如在函数的第一次调用时 link 它，在运行中，对它所指的所有事物，并注意在 他们的 定义中，如果他们改变了，那么这件事也需要取消 link，这样一切都会再次发生。这些技巧曾经看起来难以置信，但像 JavaScript 这样的语言的编译器现在至少一直在做这样的事情。
请注意，现代系统的编译器和 linker 实际上做的事情比我描述的要复杂，因为共享库 &c：我描述的或多或少是共享库之前发生的事情.