lisp 中的递归跟踪...可以使用一些建议

Question

有人能抽出一点时间来帮助我理解为什么在 Lisp 中的这个小函数中它一直评估为 true 吗？

(defun fob (n)
   (if (= n 10)
      'true
      (fob (+ n 1))))

继续评估追踪到：

  0: (FOB 5)                                                                                                                                                                                  

    1: (FOB 6)                                                                                                                                                                                

      2: (FOB 7)                                                                                                                                                                              

        3: (FOB 8)                                                                                                                                                                            

          4: (FOB 9)                                                                                                                                                                          

            5: (FOB 10)                                                                                                                                                                       

            5: FOB returned TRUE                                                                                                                                                              

          4: FOB returned TRUE                                                                                                                                                                

        3: FOB returned TRUE                                                                                                                                                                  

      2: FOB returned TRUE                                                                                                                                                                    

    1: FOB returned TRUE                                                                                                                                                                      

  0: FOB returned TRUE 

我不明白为什么它返回 'true'，尽管显然 6 不等于 10。我只是读错了轨迹吗？任何帮助，将不胜感激。 :)

Answer 1

正如评论中所讨论的，递归有两个组成部分：一个基本情况（没有进行递归调用的条件）和一个递归情况。基本情况被跳过的递归函数可以 return 通过递归情况的值。

在您的示例中，每次调用向 n 加 1 将达到 n = 10 的基本情况（假设 n 开始于 <= 10——如果它开始out > 10 你将有无限递归，因为基本情况是不可到达的）。当调用确实到达 n = 10 时，基本情况将 return 为真，它一直传递到调用堆栈。对于您的函数，只有两种可能的结果：无限递归或 returning true.

这解释了为什么您的所有函数 return 对于 n = 5 都是正确的；虽然他们的基本情况直到 n = 10 才成立，但子调用的结果是。