递归函数及其应用

读书笔记

1、递归：是指函数直接或间接地调用函数本身

如：

#include<stdio.h>
void print()
{
    printf("hello world");
    print();
}
int main()
{
    print();　　　　　　　　　　　　//程序会重复的在屏幕上输出hello world
    return 0;
}

程序设计中无条件的递归通常是无意义的，但如果给递归调用增加限制条件，可达成我们想要的效果

为了保证程序能在有限次递归调用后结束，应该定义好递归的出口条件

如：

#include<stdio.h>
void print(int n)
{
    if (n>0)　　　　　　　　　　　　　　　　//出口条件为n>0
    {
        printf("%d: 
",n);
　　　　 printf("hello world
");
　　　　 print(n-1);
　　}
}
int main()
{
　　print(3);
　　return 0;
}

 使用递归策略实现算法问题的算法程序，其前提是必须使用划分技术，把需求解的问题划分成若干和原问题结构相同，但规模较小的子问题，

这样可以使原问题的解建立在子问题解的基础上，而子问题的解建立在更小的子问题解的基础上，由于问题的求解是从原问题开始的，因此其`

求解过程是自顶向下产生的计算序列

（1）用递归函数实现阶乘问题

long fact(int n)
{
　　if (n==0) return 1;
　　else return n*fact(n-1);
}
int main()
{
　　int n;
　　long f;
　　printf("Please input an integer : ");
　　scanf("%d",&n);
　　f = fact(n);
　　pirntf("%d != %ld
",n,f);
　　retutn 0;
}

（2）用递归函数解决汉诺塔问题

#include<stdio.h>
void move (int n,char source,char goal);
void moveTower(int n,char source,char temp,cahr goal)
int main()
{
　　int n;
　　printf("Please enter the number of disks: ");
　　scanf("%d",&n);
　　printf("steps of moving %d disks from A to C by means of B:
",n);
　　moveTower(n,'A','B','C');
　　return 0;
}
void move(int n,char source,char goal)
{　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　//盘片编号n，移动起点source,移动终点goal
　　printf("move %d:from %c to %c
",n,source,goal);
}
void moveTower(int n,char source,char temp,char goal)　　　　　　　　//盘片编号n，移动起点source，临时中点temp，移动重点goal
{
　　if (n==1)
　　　　move(n,source,goal);　　　　　　　　　　　　　　　　　　　　　　　//将第n个圆盘从source移动到goal
　　else
　　{
　　　moveTower(n-1,source,goal,temp);　　　　　　　　　　　　　　　　　　//将第n-1个圆盘借助goal从source移动到temp
　　　move(n,source,goal);　　　　　　　　　　　　　　　　　　　　　　　　//将第n个圆从source移动到goal
　　　moveTower(n-1,temp,source,goal);　　　　　　　　　　　　　　　　　//将n-1个圆盘借助source从temp移动到goal
　　}
}