递归函数

编写递归程序要点：

1. 找到正确的递归算法，这是编写递归程序的基础；
2. 确定递归算法的结束条件，这是决定递归程序能否正常结束 的关键。

数值类问题

数值问题，可以表达为数学公式， 从数学公式推导出问题的 递归定义，然后确定问题的边界条件，从而确定递归的算法和递 归结束条件。因此，数值类问题最重要的是求出 $f(x)$和$f(x-1)$之间的关系；

比如阶乘问题：

$$ \mathrm{jiecheng}(n) = \begin{cases} 1 & n=0,或者,n=1 \ n \times \mathrm{jiecheng}(n-1) & n \ge 2 \end{cases} $$

根据数学公式可以很容易地写出程序代码：

float JieCheng(int n)
{
    float f = 0;
    if(n < 0)
        printf("n<0,error!");
    elseif(n = 0 || n = 1)
        f = 1;
    else
        f = n * JieCheng(n-1);

    return f;
}

非数值问题

汉诺达问题

在一块板上有三根杆，最左边的A杆上自上而下、由小到大放了 n个圆盘，要将Ａ杆上的圆盘，借助最右边的B杆，全部移到中间的C 杆上，条件是一次仅能移动一个盘，且不允许大盘放在小盘的上面

1. 分析1：A杆中只有一个圆盘，此时直接将该圆盘放到C杆；
2. 分析2：A干重有2个圆盘；
   1. 将A杆中上方的圆盘移到B杆；
   2. 将A杆下方的圆盘移到C杆；
   3. 将B杆中的圆盘移到C杆，则完成移动；
3. 分析3：A杆中有n(n>2)个圆盘：
   1. 将A杆中上面的(n-1)个圆盘看成整体，此时问题等价于分析2中的问题；于是将(n-1)个圆盘移到B杆；
   2. 将A杆剩下的一个圆盘移到C杆；
   3. 将B杆中(n-1)个圆盘移到C杆；可以看到分析2和分析3的情况本质上是相同的；

因此，汉诺塔问题的解决思路是：

1. 步骤1：$\color{red}{问题化简}$，假设A杆上只有一个盘子，即n=1,则只需将A盘子从A杆移动到C杆；对应的伪代码为：move(one, three);
2. 步骤2：$\color{red}{问题分解}$，对于有n(n>1)个盘子的汉诺塔问题，可分为三个步骤求解：
   1. 将A杆上的n-1个盘子借助C杆移动到B杆，伪代码为：hanoi(n-1, one, three, two);
   2. 将A杆上剩下的一个盘子移动到C杆，伪代码为：move(one, three);
   3. 将B杆上n-1个盘子借助于A杆移动到C杆，为代码为：hanoi(n-1, two, one, three);

程序的伪代码为：

    hanoi(n, one, two, three)
    {
        if(n==1) move(one, three);
        else
        {
            hanoi(n-1, one, three, two);
            move(one, three);
            hanoi(n-1, two, one, three);
        }
    }

从上面的分析可以看到，对于非数值类问题，如果能够找到解决这类问题的一系列操作步骤，就可以解决这样的问题。

• 首先我们可以将问题化简，考虑最简单的情况；也就是将问题的规模缩小到最小，分析这样的问题在最简单的情况下是怎么解决的；
• 有了简单的方法后，就可以把原来的问题分解成若干个小问题，其中至少有一个小问题和原来的问题有相同的性质，只是规模上比原来更小了。分解后的小问题作为一个独立的问题，来描述这些较小问题的解决方案，然后形成对原来较大问题的推广。

/*将盘从getone 移动到putone*/
void move(char getone, char putone) 
{ 
    printf("%c--->%c\n",g ,p etone,putone); 
}

/* 将n个盘从one杆，借助two杆，移动到three杆 */
void hanoi(int n,char one,char two,char three) 
{ 
    if(n==1) move(one,three);
    else
    { 
        hanoi(n-1,one,three,two); 
        move(one,three); 
        hanoi(n-1,two,one,three);
    }
}

int main()
{ 
    int m;
    printf("Input the number of disks:");
    scanf("%d",&m); (
    printf("The steps to moving %3d disks:\n",m);
    hanoi(m,'A','B','C');
    return 0;
}

反向输出给定整数

分析：

• 明确解法部分
• 性质相同的小问题

思路：

1. 输出给定的 n 位整数的个位上的数字；
2. 前 n-1位除以10；
3. 原问题被缩减为 n-1 位整数反向输出问题；
4. 如果 (结束条件) 执行 5, 否则循环再执行 1；
5. 递归调用结束；

如何将问题缩小以及如何控制递归的结束是两个最重要的问题!

反向输出(整数 n)
{
    if(n >=10)then
    {
        输出最后一位；
        n 除以10取整得 n_(n-1)；
        调用反向输出 n_(n-1);
    }
    else
        输出 n;
}

int main()
{
    int x;
    void int_turn(int);
    printf(“\nEnter N=”);
    scanf(%d”,&x);
    int_turn(x);                /*函数调用*/
    return 0;
}

void int_turn(int n)
{
    if(n>=10)                   /*递归判断条件*/
    {
        printf(“%d ”,n%10);     /*输出当前的最后一位*/
        int_turn(n/10);         /*原问题缩小，递归调用自身*/
    }
    else
printf(“%d”,n)