前言
    说白了递归就象我们讲的那个故事：山上有座庙，庙里有个老和尚，老和尚在讲故事，它讲的故事是：山上有座庙，庙里有个老和尚，老和尚在讲故事，它讲的故事是：……也就是直接或间接地调用了其自身。
    就象上面的故事那样，故事中包含了故事本身。因为对自身进行调用，所以需对程序段进行包装，也就出现了函数。
    函数的利用是对数学上函数定义的推广，函数的正确运用有利于简化程序，也能使某些问题得到迅速实现。对于代码中功能性较强的、重复执行的或经常要用到的部分，将其功能加以集成，通过一个名称和相应的参数来完成，这就是函数或子程序，使用时只需对其名字进行简单调用就能来完成特定功能。
    例如我们把上面的讲故事的过程包装成一个函数，就会得到：
void Story()
{
    puts("从前有座山，山里有座庙，庙里有个老和尚，老和尚在讲故事，它讲的故事是：");
    getchar();//按任意键听下一个故事的内容
    Story(); //老和尚讲的故事，实际上就是上面那个故事
}
    函数的功能是输出这个故事的内容，等用户按任意键后，重复的输出这段内容。我们发现由于每个故事都是相同的，所以出现导致死循环的迂回逻辑，故事将不停的讲下去。出现死循环的程序是一个不健全的程序，我们希望程序在满足某种条件以后能够停下来，正如我们听了几遍相同的故事后会大叫：“够了！”。于是我们可以得到下面的程序：
#include<stdio.h>

const int MAX = 3;

void Story(int n);//讲故事

int main(void)
{
    Story(0);
   
      getchar();
    return 0;
}

void Story(int n)
{
    if (n < MAX)
    {
        puts("从前有座山，山里有座庙，庙里有个老和尚，老和尚对小和尚说了一个故事：");
        getchar();
        Story(n+1);
    }
    else
    {
        printf("都讲%d遍了！你烦不烦哪？\n", n);
        return ;
    }
}
    上面的Story函数设计了一个参数n，用来表示函数被重复的次数，当重复次数达到人们忍受的极限（MAX次）时，便停下来。
基本递归
    数学归纳法表明，如果我们知道某个论点对最小的情形成立，并且可以证明一个情形暗示着另一个情形，那么我们就知道该论点对所有情形都成立。
    数学有时是按递归方式定义的。
例1：假设S（n）是前n个整数的和，那么S（1）= 1编程递归函数，并且我们可以将S（n）写成S（n）= S（n-1）+ n。
    根据递归公式，我们可以得到对应的递归函数：
int S(int n)    //求前n个整数的和
{
    if (n == 1)
        return 1;
    else
        return S(n-1) + n;
}
    函数由递归公式得到，应该是好理解的，要想求出S（n），得先求出S(n-1)，递归终止的条件（递归出口）是(n == 1)。
    再举一个典型的例子：斐波那契(Fibonacci)数列。
例2：斐波那契数列为：1、1、2、3、5、8、13、21、…，即 fib(1)=1; fib(2)=1;  fib(n)=fib(n-1)+fib(n-2) (当n>2时)。
    我们曾经用迭代法解决了这个问题，实际上数列公式本身是一个递归公式，如果用递归算法来解将更自然。根据递归公式，很容易递归函数：
int Fib(int n)
{
    if (n < 1)//预防错误
        return 0;
if (n == 1 || n == 2)// 递归出口
        return 1;
       
    return Fib(n-1) + Fib(n-2);
}


实际在上例中，当n = 40时，程序将变得缓慢，当n再大一些，内存就不够了。
    不用说,这种特例不能说明递归调用是最佳的调用，因为问题如此简单，不用递归也能解决。大多数恰当使用递归的地方不会耗尽计算机内存，只是比非递归耗费稍多时间。但是，递归一般可以得到更紧凑的代码。
    在实际编程中，有许多定义或者问题本身就具有递归性质。所以我们顺其自然就想到用递归来解决，这样不仅代码少,而且结构清晰。但是问题是我们应该怎样设计递归呢？这确
实一个问题。由于许多问题并不是很明显的表现出递归的关系，所有很大一部分需要我们进行推导，从而得出递归关系，有了递归关系，编写代码就相对的比较简单了。
    首先,我们了解递归算法的特点，所谓的递归，就是把一个不能或不好直接求解的“大问题”转化成一个或几个与原问题相似的“小问题”来解决，再把这些“小问题”进一步分解成更小的“小问题”来解决，如此分解，直至每个“小问题”都可以直接解决（此时分解到递归出口）。在逐步求解“小问题”后，再返回得到“大问题”的解。
因此，递归的执行过程由分解和求值两部分构成。首先是逐步把“大问题”分解成形式相同但规模减小的“小问题”，直至分解到递归出口。一旦遇到递归出口，分解过程结束，开始求值过程，所以分解过程是“量变”过程，即原来的“”大问题”在慢慢变小，但尚未解决。遇到递归出口后，便发生了“质变”，即原递归问题转换成直接问题。
    由于递归只需要少量的步骤就可描述解题过程中所需要的多次重复计算，所以大大的减少了代码量。递归算法设计的关键在于，出递归方程和递归终止条件(又叫边界条件或递归出口)。递归关系就是使问题向边界条件转化的过程，所以递归关系必须能使问题越来越简单，规模越小。一定要知道，没有设定边界的递归是只能‘递’不能‘归’的，即死循环。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。