纠结了2天的递归函数，记录一下

<php>
function sum($n,$m){
    if($m<=$n){
        return $n;
    }
    return sum($n,$m-1)+$m;
}
echo sum(1,3);  // => 6
</php>


推算一下运算过程

sum(1,3) = sum(1,2) + 3 , sum(1,2) = sum(1,1) + 2 , sum(1,1) =1  

得到了sum(1,1) =1  后，再进行倒推

sum(1,1) =1  , sum(1,2) = 1 + 2 = 3  , sum(1,3) = 3+3=6

递归函数
        

            
[ firedy 发表于 2007-1-20 12:54:00 ]
            
        

            
学C数据结构时在讲栈的章节里重点提到递归函数的思想，现在我在看java时同样遇到递归的思想，所以就想整理整理一下自己的“笔记”，理一下自己的思路。
            
递归的定义：递归是指在定义自身的同时又出现了对自身的调用。 如果一个函数在其定义体内直接调用自己，则称其为直接递归函数； 如果一个函数经过一系列的中间调用语句，通过其它函数间接调用自己，则称其为间接递归函数。  见名思意，递归实际上是递推与回归的结合。
            
下面见一个例子，这个例子很有意思，因为在我考数据结构时且好出了这道题，我刚好在考试前复习时见道同样的题，然后我并且在考试前运行过此题目的程序。题目是：求函数F＝1+1/2+1/3+……+1/n的递归出口和递归体。
            
在这里先提一下递归模型：
            
递归模型：
    由递归体与递归出口组成
{
      if(递归出口)
             (简单操作);
     else
             (递归体);
}
            
根据题目写的c程序如下：
            
/*****************************************
求函数F＝1+1/2+1/3+……+1/n
运行环境：Turbo 2.0&&Turbo C for Windows
Firedy
2007-1-8
******************************************/
            
float fun(int n)    /*递归函数*/
{
            /*float k=1.0/n;*/
       if(n==1)         /*递归出口*/
             return 1;    
       else
             return fun(n-1)+1.0/n;/*k+=fun(n-1);*/  /*递归体*/
} 
            
main()
{
      int n;
      float F;
      printf("F=1+1/2+1/3+...+1/n=?/n");
      printf("/ninput n(n!=0):");
      scanf("%d",&n);
      F=fun(n);
      printf("/nF=%.3f",F);
}
            
运行结果：
            
 
            
从中可以看出递归的优点，接着说下教材里（我使用的c数据结构教材是西电科大出版的耿国华等编著的《数据结构－－C语言描述》）提到的递归算法到递归算法的转换：
            
递归算法有两个特性：（1）递归算法是一种分而治之、把复杂问题分解为简单问题的求解问题方法，对求解某些复杂问题，递归算法的分析方法是有效的。  （2）递归算法的时间效率底。（计算机编程很讲究算法的效率问题，也许所以就有了需要消除递归的原因，对这方面的理解，我没有怎么去思考，毕竟目前我们为了完成题目，首先是找思维直观，容易想到的方法，而对于效率的或效益的问题，更多的是企业或更进一步的研究学习是应该很重视的一个问题，可能这也可以说是我们学校的教育与社会之间的差距吧。）
            
其实，一个问题的思考，可以延伸到很多领域，研究研究是永无止境的

            
        
 

Python 递归函数
如果一个函数体直接或者间接调用自己，那么这个函数就称为递归函数．也就是说，递归函数体的执行过程中可能会返回去再次调用该函数．在ｐｙｔｈｏｎ里，递归函数不需要任何特殊的语法，但是它需要付出一定的努力去理解和创建．
我们会以一个简单的例子开始：写一个函数求一个自然数中所有数字的和．在设计递归函数的时候，我们会寻找能把问题分解成简单的问题的方法．在这道题中，运算符%和//可以用来把一个数分成两部分：最低位和不包含最低位数字两部分．
１８１１７的数字和为：１＋８＋１＋１＋７＝１８．这样我们就可以分割这个数．把这个数分割成最低位７和不包含最低位数字的和１＋８＋１＋１＝１１．这种分割方法给我们提供了一个算法：通过最低位ｎ％１０与ｎ//１０的数字之和相加来计算数ｎ的数字之和．这种方法存在特殊情况：如果一个数只有一位，那么它的数字之和就是它本身．这个算法可以用递归函数实现．
def sum_digit(n):
"""return the sum of the digit of positive integer n."""
if n < 10:
return n
else:
last = n % 10
all_but_last = n // 10
return sum_digit(all_but_last) + last
函数ｓｕｍ_digit的定义是完整和正确的，即使ｓｕｍ_digit函数在自身的函数体里被调用．
这样求一个数的数字之和的问题就被分解成了两部分：求除去最低位部分数字之和，然后加上最低位．这两个步骤全都比原问题要简单．这个函数是递归的，因为第一步的问题和原问题是相同类型的．也就是说,sum_digit的确实是我们需要去实现自然数数字求和的函数．
我们可以理解这个递归函数是怎样使用计算环境模型成功应用的．它　不需要任何新的规范．
感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！
您可能感兴趣的文章:浅谈Python中的可迭代对象、迭代器、For循环工作机制、生成器Python进阶之递归函数的用法及其示例Python递归函数定义与用法示例浅析python递归函数和河内塔问题讲解Python中的递归函数python实现斐波那契递归函数的方法提升Python效率之使用循环机制代替递归函数

                    
递归函数（一）：开篇
递归函数（二）：编写递归函数的思路和技巧
递归函数（三）：归纳原理
递归函数（四）：全函数与计算的可终止性
递归函数（五）：递归集与递归可枚举集
递归函数（六）：最多有多少个程序
递归函数（七）：不动点算子
递归函数（八）：偏序结构
递归函数（九）：最小不动点定理
-

递归，是一个熟悉而陌生的概念，说它熟悉，是因为人们经常提起它，
而说它陌生，指的是人们在实际编程中几乎不会主动使用它。
给定一个问题，如果本质上它能看做一个调用自身的规模较小的一个子问题来求解，
那么给出一个递归的算法解，就是很自然的。
然而，即使是这样，编制一个递归函数也是一件令人头疼的事情。
本系列文章的目的，可能并不局限于指出如何编写一个递归函数，
而是期望想从递归函数开始，了解它相关的科学知识，以达到对不同领域触类旁通的效果。
从一个简单的例子开始
首先，我们来重温一下递归的概念，
维基百科上是这样描述的，
递归（recursion），在数学与计算机科学中，是指在函数的定义中使用函数自身的方法。
我们来看一个简单的例子吧。（Haskell代码
fact :: Int -> Int
fact 1 = 1
fact n = n * fact (n-1)
在这个例子中，
第一行fact :: Int -> Int表示了fact函数的类型，
第二行和第三行定义了函数fact，
我们看到第三行，在对fact函数定义的时候，等式右边又出现了fact，
这样定义的函数fact是递归的。
我们调用一下fact，来看看结果，
fact 10
3628800
嗯嗯，fact就是阶乘函数。
写递归函数的步骤
那么，给定一个问题，我们编写一个递归函数，要如何开始呢？
（1）递推式
首先，我们要找到“递推式”。
例如，在数学上阶乘的定义是，\(f(n)=n!\)，这样的表述形式，不具有递推性。
我们先要想办法把\(f(n)\)用\(f(n-1)\)表示出来。
经过思考之后，我们可以证明，\(f(n)=n*f(n-1)\)，
于是，我们就走出了关键的第一步，得到了“递推式”。
（2）找出终止条件
有了“递推式”还不行，我们还需要确定递推在什么时候终止。
我们知道\(f(1)=1\)，\(f(2)=2f(1)\)，\(f(3)=3f(2)\)，等等，
因此，我们只需要指定\(f(1)=1\)，那么递推就会在\(f(n)\)，当\(n=1\)的时候终止了。
终止，就是不再调用规模更小的问题了。
这时，终止条件是\(f(1)=1\)。
（3）用数学归纳法证明解的正确性
这一步是很重要的，有很多人都缺少证明递推式正确性的环节，
但是，考虑到介绍数学归纳法及其扩展会占用不少篇幅，
这里先略去，下一篇我们再回来讨论它。
这里，我们先假定，根据“递推式”和“终止条件”，使用数学归纳法，
我们已经证明了这样定义的\(f(n)\)就是\(n!\)。
（4）根据递推式和终止条件，编写程序
有了“递推式”和“终止条件”，再编写程序就水到渠成了。
很多人一上来就开始编码，就会感觉毫无头绪。
我们再来看下那段程序，
fact :: Int -> Int
fact 1 = 1
fact n = n * fact (n-1)
这不就是“递推式”和“终止条件”的忠实表示吗？
我们用fact 1 = 1表示了\(f(1)=1\)，
用fact n = n * fact (n-1)表示了\(f(n)=n*f(n-1)\)。
小技巧
我们再看个复杂一点的例子。
在实际项目中，我们可能会遇到循环n次的场景，
在循环过程中，我们会根据索引进行运算，然后将某些符合条件的运算放到最终的结果中。
例如，我们选择10以内的所有偶数，
[x|x <- [0..9], x `mod` 2 == 0]
[0,2,4,6,8]
使用以上列表解析（list comprehension）的方法，我们可以快速得到结果。
但是这里，我们想要拿它来举例，介绍一个编写递归函数常用的小技巧。
为了通用性，我们考虑循环n次，将索引传入函数fn，根据fn的返回值，将结果放入一个列表中。
（1）困境
根据前文介绍的编写步骤，我们需要先找到“递推式”和“终止条件”。
“终止条件”怎么写呢？
假如我们定义的递归函数称为myLoop，那么\(myLoop(0,fn)\)就是终止条件，它应该返回一个列表。
但是这个列表在参数中没有，它随着递归调用的过程“积累”得到的。
好吧，那我们看“递推式”。
\(myLoop(n,fn)\)要用\(myLoop(n-1,fn)\)的结果计算出来，
我们需要先用索引调用fn，然后再根据fn的返回值，放入结果列表，再继续调用\(myLoop(n-1,fn)\)。
可是，索引从哪来呢？（n不是索引，因为索引从0开始，而n是逐渐变小的。
这是两个典型的困难，
其一，我们在递归的过程中“积累”了某些东西，
其二，我们需要传递和递归过程相关的“索引”。
（2）解法
这时候，我们的小技巧就有用武之地了。
我们可以编写一个辅助的递归函数，通过增加参数的办法，提高灵活性。
例如，我们可以编写一个辅助函数myLoop'，然后用myLoop'来实现myLoop。
myLoop :: Int -> (Int -> Maybe a) -> [a]
myLoop n fn = myLoop' n 0 fn []

myLoop' :: Int -> Int -> (Int -> Maybe a) -> [a] -> [a]
myLoop' 0 i fn lst = lst
myLoop' n i fn lst = case fn i of
  Just x -> myLoop' (n-1) (i+1) fn (lst++[x])
  Nothing -> myLoop' (n-1) (i+1) fn lst
以上，我们为myLoop'增加了参数i和lst，分别表示“索引”和“积累”的列表。
然后，myLoop就可以用myLoop'来实现了。
别忘了测试一下最终的结果，
myLoop 10 (\x -> if x `mod` 2 == 0 then Just x else Nothing)
[0,2,4,6,8]
（3）其他考虑
合理的利用递归函数的返回值，会减少附加参数的数量，例如，
myLoop :: Int -> (Int -> Maybe a) -> [a]
myLoop n fn = myLoop' n 0 fn

myLoop' :: Int -> Int -> (Int -> Maybe a) -> [a]
myLoop' 0 i fn = []
myLoop' n i fn = case fn i of
  Just x -> x:(myLoop' (n-1) (i+1) fn)
  Nothing -> myLoop' (n-1) (i+1) fn
但最终得到的递归函数就不是尾递归了，
关于尾递归，我们将在后续文章中讨论它。
参考
维基百科 - 递归
维基百科 - 递推关系式