PROSAGA码农传奇-lisp-什么是尾递归？

0# 一只特立独行的猪 | 2019-08-31 10-32

1# 哈哈哈哈 | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”>
  
    摘自本书
    
      Lua编程
    
     节目
    <a href="http://www.lua.org/pil/6.3.html" rel="noreferrer">
      如何进行正确的尾递归
    </A>
     （在Lua中，但也应该适用于Lisp）以及为什么它更好。
  
  <BLOCKQUOTE>
    
      一个
      
        尾巴电话
      
       [tail recursion]是一种goto打扮
  作为电话。当a时发生尾调用
  函数将另一个调用为最后一个
  行动，所以它没有别的办法。
  例如，在以下代码中，
  打电话给
       <code>
 g
 </code>
       是一个尾调：
    
     <pre class="lang-lua prettyprint-override">
 <code>
 function f (x)
 return g(x)
end

</code>
 </pre>
    
      后
       <code>
 f
 </code>
       电话
       <code>
 g
 </code>
      ，它没有别的
  去做。在这种情况下，该计划
  不需要返回调用
  函数调用时的函数
  结束。因此，尾调用后，
  该计划不需要保留任何
  有关呼叫功能的信息
  在堆栈中。 ...
    
    
      因为正确的尾调用不会
  堆栈空间，没有限制
  “嵌套”尾部调用的数量a
  程序可以做。例如，我们可以
  用any调用以下函数
  数字作为参数;永远不会
  溢出堆栈：
    
     <pre class="lang-lua prettyprint-override">
 <code>
 function foo (n)
 if n > 0 then return foo(n - 1) end
end

</code>
 </pre>
    
      ......正如我之前所说，尾部呼叫是一个
  转发。因此，一个非常有用
  应用适当的尾调用
  Lua用于编程状态机。
  这样的应用可以代表每个
  以功能陈述;改变国家
  是去（或打电话）具体的
  功能。举个例子，让我们来吧
  考虑一个简单的迷宫游戏。迷宫
  有几个房间，每个房间最多
  四扇门：北，南，东，和
  西方。在每一步，用户输入一个
  运动方向。如果有门
  在那个方向，用户去
  相应的房间;否则，
  程序打印警告。目标是
  从最初的房间到决赛
  房间。
    
    
      这个游戏是一个典型的状态机，
  当前房间是哪个州。
  我们可以用一个这样的迷宫来实现
  每个房间的功能。我们用尾巴
  打电话从一个房间搬到
  另一个。一个有四个房间的小迷宫
  可能看起来像这样：
    
     <pre class="lang-lua prettyprint-override">
 <code>
 function room1 ()
 local move = io.read()
 if move == "south" then return room3()
 elseif move == "east" then return room2()
 else print("invalid move")
 return room1() -- stay in the same room
 end
end

function room2 ()
  local move = io.read()
  if move == "south" then return room4()
  elseif move == "west" then return room1()
  else print("invalid move")
       return room2()
  end
end

function room3 ()
  local move = io.read()
  if move == "north" then return room1()
  elseif move == "east" then return room4()
  else print("invalid move")
       return room3()
  end
end

function room4 ()
  print("congratulations!")
end

</code>
 </pre>
  </BLOCKQUOTE>
  
    所以你看，当你做一个递归调用时：
  
   <pre class="lang-lua prettyprint-override">
 <code>
 function x(n)
 if n==0 then return 0
 n= n-2
 return x(n) + 1
end

</code>
 </pre>
  
    这不是尾递归，因为在进行递归调用之后，您仍然可以在该函数中执行操作（添加1）。如果输入一个非常高的数字，可能会导致堆栈溢出。
  
</DIV>

2# Moso31 | 2019-08-31 10-32

3# 我头上有犄角 | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”>
  
    递归函数是一个函数
    的
      自己打电话
    </强>
  
  
    它允许程序员使用a编写高效的程序
    的
      最少量的代码
    </强>
    。
  
  
    缺点是他们可以
    的
      导致无限循环
    </强>
     和其他意外的结果如果
    的
      写得不好
    </强>
    。
  
  
    我会解释两者
    的
      简单的递归函数和尾递归函数
    </强>
  
  
    为了写一个
    的
      简单的递归函数
    </强>
  
  <OL>
    <LI>
      的
        要考虑的第一点是你什么时候决定出来
循环的结果是if循环
      </强>
    </LI>
    <LI>
      的
        第二个是如果我们是自己的功能，那么要做什么
      </强>
    </LI>
  </醇>
  
    从给定的例子：
  
   <pre>
 <code>
 public static int fact(int n){
 if(n <=1)
 return 1;
 else 
 return n * fact(n-1);
}

</code>
 </pre>
  
    从上面的例子
  
   <pre>
 <code>
 if(n <=1)
 return 1;

</code>
 </pre>
  
    是退出循环的决定性因素
  
   <pre>
 <code>
 else 
 return n * fact(n-1);

</code>
 </pre>
  
    是否要进行实际处理
  
  
    让我逐一打破任务，以便于理解。
  
  
    如果我跑，让我们看看内部会发生什么
     <code>
 fact(4)
 </code>
  
  <OL>
    <LI>
      的
        代入n = 4
      </强>
    </LI>
  </醇>
   <pre>
 <code>
 public static int fact(4){
 if(4 <=1)
 return 1;
 else 
 return 4 * fact(4-1);
}

</code>
 </pre>
  
     <code>
 If
 </code>
     循环失败，所以它去了
     <code>
 else
 </code>
     环
所以它返回
     <code>
 4 * fact(3)
 </code>
  
  <ol start =“2”>
    <LI>
      
        在堆栈内存中，我们有
         <code>
 4 * fact(3)
 </code>
      
      
        的
          代入n = 3
        </强>
      
    </LI>
  </醇>
   <pre>
 <code>
 public static int fact(3){
 if(3 <=1)
 return 1;
 else 
 return 3 * fact(3-1);
}

</code>
 </pre>
  
     <code>
 If
 </code>
     循环失败，所以它去了
     <code>
 else
 </code>
     环
  
  
    所以它返回
     <code>
 3 * fact(2)
 </code>
  
  
    记得我们称之为```4 * fact（3）``
  
  
    输出为
     <code>
 fact(3) = 3 * fact(2)
 </code>
  
  
    到目前为止堆栈已经存在
     <code>
 4 * fact(3) = 4 * 3 * fact(2)
 </code>
  
  <ol start =“3”>
    <LI>
      
        在堆栈内存中，我们有
         <code>
 4 * 3 * fact(2)
 </code>
      
      
        的
          代入n = 2
        </强>
      
    </LI>
  </醇>
   <pre>
 <code>
 public static int fact(2){
 if(2 <=1)
 return 1;
 else 
 return 2 * fact(2-1);
}

</code>
 </pre>
  
     <code>
 If
 </code>
     循环失败，所以它去了
     <code>
 else
 </code>
     环
  
  
    所以它返回
     <code>
 2 * fact(1)
 </code>
  
  
    记得我们叫了
     <code>
 4 * 3 * fact(2)
 </code>
  
  
    输出为
     <code>
 fact(2) = 2 * fact(1)
 </code>
  
  
    到目前为止堆栈已经存在
     <code>
 4 * 3 * fact(2) = 4 * 3 * 2 * fact(1)
 </code>
  
  <ol start =“3”>
    <LI>
      
        在堆栈内存中，我们有
         <code>
 4 * 3 * 2 * fact(1)
 </code>
      
      
        的
          代入n = 1
        </强>
      
    </LI>
  </醇>
   <pre>
 <code>
 public static int fact(1){
 if(1 <=1)
 return 1;
 else 
 return 1 * fact(1-1);
}

</code>
 </pre>
  
     <code>
 If
 </code>
     循环是真的
  
  
    所以它返回
     <code>
 1
 </code>
  
  
    记得我们叫了
     <code>
 4 * 3 * 2 * fact(1)
 </code>
  
  
    输出为
     <code>
 fact(1) = 1
 </code>
  
  
    到目前为止堆栈已经存在
     <code>
 4 * 3 * 2 * fact(1) = 4 * 3 * 2 * 1
 </code>
  
  
    最后，结果
    的
      事实（4）= 4 * 3 * 2 * 1 = 24
    </强>
  
  
    <a href="https://i.stack.imgur.com/ELSwN.jpg" rel="nofollow noreferrer">
      <img src =“https://i.stack.imgur.com/ELSwN.jpg”alt =“在此处输入图片说明”/>
    </A>
  
  
    该
    的
      尾递归
    </强>
     将会
  
   <pre>
 <code>
 public static int fact(x, running_total=1) {
 if (x==1) {
 return running_total;
 } else {
 return fact(x-1, running_total*x);
 }
}

</code>
 </pre>
  <OL>
    <LI>
      的
        代入n = 4
      </强>
    </LI>
  </醇>
   <pre>
 <code>
 public static int fact(4, running_total=1) {
 if (x==1) {
 return running_total;
 } else {
 return fact(4-1, running_total*4);
 }
}

</code>
 </pre>
  
     <code>
 If
 </code>
     循环失败，所以它去了
     <code>
 else
 </code>
     环
所以它返回
     <code>
 fact(3, 4)
 </code>
  
  <ol start =“2”>
    <LI>
      
        在堆栈内存中，我们有
         <code>
 fact(3, 4)
 </code>
      
      
        的
          代入n = 3
        </强>
      
    </LI>
  </醇>
   <pre>
 <code>
 public static int fact(3, running_total=4) {
 if (x==1) {
 return running_total;
 } else {
 return fact(3-1, 4*3);
 }
}

</code>
 </pre>
  
     <code>
 If
 </code>
     循环失败，所以它去了
     <code>
 else
 </code>
     环
  
  
    所以它返回
     <code>
 fact(2, 12)
 </code>
  
  <ol start =“2”>
    <LI>
      
        在堆栈内存中，我们有
         <code>
 fact(2, 12)
 </code>
      
      
        的
          代入n = 2
        </强>
      
    </LI>
  </醇>
   <pre>
 <code>
 public static int fact(2, running_total=12) {
 if (x==1) {
 return running_total;
 } else {
 return fact(2-1, 12*2);
 }
}

</code>
 </pre>
  
     <code>
 If
 </code>
     循环失败，所以它去了
     <code>
 else
 </code>
     环
  
  
    所以它返回
     <code>
 fact(1, 24)
 </code>
  
  <ol start =“3”>
    <LI>
      
        在堆栈内存中，我们有
         <code>
 fact(1, 24)
 </code>
      
      
        的
          代入n = 1
        </强>
      
    </LI>
  </醇>
   <pre>
 <code>
 public static int fact(1, running_total=24) {
 if (x==1) {
 return running_total;
 } else {
 return fact(1-1, 24*1);
 }
}

</code>
 </pre>
  
     <code>
 If
 </code>循环是真的
  
  
    所以它返回
     <code>
 running_total
 </code>
  
  
    输出为
     <code>
 running_total = 24
 </code>
  
  
    最后，结果
    的
      事实（4,1）= 24
    </强>
  
  
    <a href="https://i.stack.imgur.com/FkcU1.jpg" rel="nofollow noreferrer">
      <img src =“https://i.stack.imgur.com/FkcU1.jpg”alt =“在此处输入图片说明”/>
    </A>
  
</DIV>

4# 筱梨 | 2019-08-31 10-32

5# 听风～ | 2019-08-31 10-32

6# v-star*위위 | 2019-08-31 10-32

7# 敢嫁就敢娶 | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”>
  
    递归意味着一个函数调用自身。例如：
  
   <pre class="lang-lisp prettyprint-override">
 <code>
 (define (un-ended name)
 (un-ended 'me)
 (print "How can I get here?"))

</code>
 </pre>
  
    Tail-Recursion表示结束函数的递归：
  
   <pre class="lang-lisp prettyprint-override">
 <code>
 (define (un-ended name)
 (print "hello")
 (un-ended 'me))

</code>
 </pre>
  
    看，最后一个未结束的函数（过程，在方案术语中）做的是调用自身。另一个（更有用）的例子是：
  
   <pre class="lang-lisp prettyprint-override">
 <code>
 (define (map lst op)
 (define (helper done left)
 (if (nil? left)
 done
 (helper (cons (op (car left))
 done)
 (cdr left))))
 (reverse (helper '() lst)))

</code>
 </pre>
  
    在辅助程序中，如果左边不是nil，它会做的最后一件事就是调用自己（在有些事情和cdr之后）。这基本上是您映射列表的方式。
  
  
    尾递归具有很大的优势，解释器（或编译器，依赖于语言和供应商）可以优化它，并将其转换为等同于while循环的东西。事实上，在Scheme传统中，大多数“for”和“while”循环是以尾递归方式完成的（据我所知，没有for和while）。
  
</DIV>

8# 無口君 | 2019-08-31 10-32

9# 机器设备维修 | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”>
  
    考虑一个添加前N个整数的简单函数。 （例如。
     <code>
 sum(5) = 1 + 2 + 3 + 4 + 5 = 15
 </code>
    ）。
  
  
    这是一个使用递归的简单JavaScript实现：
  
   <pre class="lang-js prettyprint-override">
 <code>
 function recsum(x) {
 if (x===1) {
 return x;
 } else {
 return x + recsum(x-1);
 }
}

</code>
 </pre>
  
    如果你打电话
     <code>
 recsum(5)
 </code>
    ，这是JavaScript解释器评估的内容：
  
   <pre class="lang-js prettyprint-override">
 <code>
 recsum(5)
5 + recsum(4)
5 + (4 + recsum(3))
5 + (4 + (3 + recsum(2)))
5 + (4 + (3 + (2 + recsum(1))))
5 + (4 + (3 + (2 + 1)))
15

</code>
 </pre>
  
    请注意每个递归调用必须在JavaScript解释器开始实际执行计算总和之前完成。
  
  
    这是同一函数的尾递归版本：
  
   <pre class="lang-js prettyprint-override">
 <code>
 function tailrecsum(x, running_total=0) {
 if (x===0) {
 return running_total;
 } else {
 return tailrecsum(x-1, running_total+x);
 }
}

</code>
 </pre>
  
    这是您调用时将发生的事件序列
     <code>
 tailrecsum(5)
 </code>
    ，（这实际上是
     <code>
 tailrecsum(5, 0)
 </code>
    ，因为默认的第二个参数）。
  
   <pre class="lang-js prettyprint-override">
 <code>
 tailrecsum(5, 0)
tailrecsum(4, 5)
tailrecsum(3, 9)
tailrecsum(2, 12)
tailrecsum(1, 14)
tailrecsum(0, 15)
15

</code>
 </pre>
  
    在尾递归的情况下，对每个递归调用的评估，
     <code>
 running_total
 </code>
     已更新。
  
  
    
      注意：原始答案使用了Python中的示例。由于现代JavaScript解释器支持，因此已将其更改为JavaScript
      <a href="https://stackoverflow.com/questions/310974/what-is-tail-call-optimization">
        尾调用优化
      </A>
       但Python解释器却没有。
    
  
</DIV>