Python哪些可以代替递归的算法？

回复内容： 所有的递归调用，都可以做CPS变换改写成尾递归形式，然后尾递归可以改写成循环：

  def   fact  (  n  ): 
     if   n   ==   0  : 
         return   1 
     else  : 
         return   n   *   fact  (  n   -   1  ) 


 id   =   lambda   x  :   x 


 def   factCPS  (  n  ): 
     def   f  (  n  ,   k  ): 
         if   n   ==   0  : 
             return   k  (  1  ) 
         else  : 
             return   f  (  n   -   1  ,   lambda   x  :   k  (  n   *   x  )) 

     return   f  (  n  ,   id  ) 


 def   factNoRec  (  n  ): 
     def   factory  (  n  ,   k  ): 
         return   lambda   x  :   k  (  n   *   x  ) 

     k   =   id 
     while   True  : 
         if   n   ==   0  : 
             return   k  (  1  ) 
         else  : 
             k   =   factory  (  n  ,   k  ) 
             n   -=   1 


 def   factHolyCrap  (  n  ): 
     k   =   () 
     while   True  : 
         if   n   ==   0  : 
             x   =   1 
             while   k  : 
                 x   =   k  [  0  ]   *   x 
                 k   =   k  [  1  ] 
             return   id  (  x  ) 
         else  : 
             k   =   (  n  ,   k  ) 
             n   -=   1 

 if   __name__   ==   '__main__'  : 
     print  ([  f  (  5  )   for   f   in   [  fact  ,   factCPS  ,   factNoRec  ,   factHolyCrap  ]]) 
  

递归过程中需要维护一个调用栈

如果不想递归，硬是要循环，那么可以自己手动来维护这个调用栈

这样唯一的好处或许就是解除了最大递归深度的限制吧。。。 给邵大神补一个java sample

  public   class   RecursionEliminationSample   { 
     int   factorRec  (  int   n  )   { 
         if   (  n   ==   0  ) 
             return   1  ; 
         else 
             return   n   *   factorRec  (  n  -  1  ); 
     } 

     int   factor  (  int   n  )   { 
         Function    Integer  ,   Integer  >   k   =   (  x  )   ->   x  ; 
         while  (  true  )   { 
             if   (  n   ==   0  ) 
                 return   k  .  apply  (  1  ); 
             else   { 
                 final   Function    Integer  ,   Integer  >   k0   =   k  ; 
                 final   int   n0   =   n  ; 

                 k   =   (  x  )   ->   k0  .  apply  (  n0   *   x  ); 
                 n   -=   1  ; 
             } 
         } 
     } 
 } 
  

用循环实现？ 可以自己建个栈来保存状态。你只需要搞明白在递归的时候程序往栈上面放了些什么，然后用自己的栈模拟即可。
技巧上倒是可以参照从fortran时代积累的递归转迭代的技术。 不是完全没有解决方案：
Does Python optimize tail recursion? 时代积累的递归转迭代的技术。 然后用自己的栈模拟即可。 ，话j

查看更多关于Python哪些可以代替递归的算法？的详细内容...