2021年递归程序设计.ppt

一个函数被调用，在尚未执行完之前，又直接或间接地调用了这个函数本身，这样的函数称递归函数。
递归函数分为直接递归函数和间接递归函数。这种函数的示意图如下：
递归程序设计
2021/1/15
1
递归程序设计
2021/1/15
2
1)直接递归函数
如果一个函数在其定义中直接调用自己，则称这种函数为直接递归函数。
递归程序设计
2021/1/15
3
比如下面函数求n的阶乘，采用的是直接递归调用形式，因此是直接递归函数：
    long factorial(int n)
   { if(n==0) return 1;
     return factorial(n-1)*n;
   }
递归程序设计
2021/1/15
4
2）间接递归函数
如果一个函数通过在其定义中调用其它函数，再由其它函数调用该函数，称这种函数为间接递归函数。
递归程序设计
2021/1/15
5
比如下面的代码定义了两个函数，它们构成了间接递归调用：
int f1(int a)
{ int b;
    b=f2(a+1);    //间接递归调用 ：f1()调用了f2()
                  //...
}
int f2(int a)
{ int c;
    c=f1(s-1);    //间接递归调用 ：f2()又调用了f1()
                  //...
}　
在上面代码中，f1()调用了f2()，而f2()又调用了f1()，这样f1()、f2()各自实现了间接递归调用自己。
递归程序设计
2021/1/15
6

已知Fibonacci序列的数学定义如下：
                      
使用递归程序计算Fibonacci数序列。
递归程序设计
2021/1/15
7
分析如下：
    设n为5，则有：
    F(5)=F(3)+F(4)
    =F(1)+F(2)+F(2)+F(3)
    =F(1)+F(0)+F(1)+F(0)+F(1)+F(1)+F(2)
    =F(1)+F(0)+F(1)+F(0)+F(1)+F(1)+F(0)+F(1)
    =1+1+1+1+1+1+1+1
    =8
递归程序设计
2021/1/15
8
因此可以归纳为函数：　
  int fibonacci(int n)       //n是大于等于0 的整数
  { if((n==0)||(n==1))
return 1;
    if(n>1)
return (fibonacci(n-2)+fibonacci(n-1));
  }
递归程序设计
2021/1/15
9

1)至少存在一个基本解(不再递归)。
2)每一次求解过程都可归结为把对一个较大较为复杂的问题的求解转化为对较为小较为简单的同类问题的求解。
3)经过执行有限步之后，总能达到基本解。
递归程序设计
2021/1/15
10