实现尾递归优化的一点思路

3P主义

不精确的概括，所谓尾递归，就是在函数里最后一条里调用自身；如果没有尾递归优化的话，在栈上要保存无数个函数的返回地址；在很多函数式语言里，有所谓的尾递归优化；在 Perl 里如何达到尾递归的效果？可以考虑借助 goto ：

1. 
   
2. #!/bin/env perl
   
3. 
   
4. use strict;
   
5. use warnings;
   
6. 
   
7. print func(100);
   
8. 
   
9. sub func {
   
10.     my ($n, $sum) = @_;
    
11.     $sum = 1 if (not defined $sum);
    
12. 
    
13.     if ($n <= 1) {
    
14.         return $sum;
    
15.     }
    
16.     else {
    
17.         $sum *= $n;
    
18.         @_ = ($n - 1, $sum);
    
19.         goto(&func);
    
20.     }
    
21. }
    
22. 
    
23. sub func2 {
    
24.     my ($n, $sum) = @_;
    
25.     $sum = 1 if (not defined $sum);
    
26. 
    
27.     if ($n <= 1) {
    
28.         return $sum;
    
29.     }
    
30.     else {
    
31.         $sum *= $n;
    
32.         return func2($n - 1, $sum);
    
33.     }
    
34. }
    

复制代码

bikong0411

3p主义莫莫牛x

sjdy521

这个和goto有什么关系呢，尾递归无非是把每次递归的结果传递给自身。

perl -e 'use strict;sub r{if(@_ == 1){return ($_[0]== 0)?(1)&r($_[0],1))} elsif(@_==2){return ($_[0]==1)?($_[1])&r($_[0]-1,$_[1]*$_[0]))}   };  print &r(10)'

按照普通语言的写法不就可以了？

sjdy521

回复 1# 3P主义


   普通的递归调用没办法较少堆栈的消耗，你说的优化很可能是编译器自身针对尾递归进行的内部的一种优化方法吧。。。希望能发个其他语言的尾递归来看看

royalzhang

关于Tail Call，《Modern Perl》第77页，有个二分查找的例子。