文档介绍：计算机科学系陈垚
*
张福祥主编辽宁大学出版社
计算机科学系陈垚
*
我们先看这样一个例子:
说有一只调皮的小猴子,摘了一堆水果,第一天吃了水果的一半,又多吃了一个;第二天吃了剩下水果的一半,又多吃了一个;依次类推….到第十天,发现只剩下了1个水果,请问这只猴子到底摘了多少个水果?
计算机科学系陈垚
*
一、函数递归的特点
函数递归调用
后一部分与原始问题类似
后一部分是原始问题的简化
1、定义:调用一个函数时直接或间接调用自身,
称之为函数的递归。
2、一个问题能够成为递归必须具备的条件是:
许多数学函数都是用递归的形式定义的:
计算机科学系陈垚
*
1. 直接递归调用:函数直接调用本身
二、程序中的递归方式
2. 间接递归调用:函数间接调用本身
计算机科学系陈垚
*
说明
C语言对递归函数的自调用次数没有限制
必须有递归结束条件
int f(x)
int x ;
{ int y, z ;
……
z =f(y) ;
……
return(2*z) ;
}
直接调用
间接调用
int f1(x)
int x ;
{ int y, z ;
……
z =f2(y) ;
……
return(2*z) ;
}
int f2(t)
int t ;
{ int a, c ;
……
c =f1(a) ;
……
return(3+c) ;
}
计算机科学系陈垚
*
思考如下问题:
例1: 有5个人坐在一起,问第5个人多少岁,
他说比第4个人大2岁;问第4个人岁数,他说比
第3个人大2岁;问第3个人,又说比第2个大2岁;
问第2个人,说比第1个人大2岁;最后问第1
个人,他说他10岁;请问第5个人多大?
比她大2岁
比她大2岁
比她大2岁
比她大2岁
我10岁
计算机科学系陈垚
*
age(5)
=16+2=18
age(4)
=14+2=16
age(3)
=12+2=14
age(2)
=10+2=12
10 (n=1)
age(n) =
age(n-1)+2 (n>1)
设 age 表示年龄,则有如下:
age(5)
=age(4)+2
age(4)
=age(3)+2
age(3)
=age(2)+2
age(2)
=age(1)+2
age(1)
=10
计算机科学系陈垚
*
main()
{
printf(“%d”, age(5));
}
age(int n)
{ int c;
if(n==1) c=10;
else c = age(n-1)+2;
return(c) ;
}
age(5)
c=10
n=1
c=age(3)+2
n=4
c=age(2)+2
n=3
c=age(1)+2
n=2
c=age(4)+2
n=5
c=10+2=12
c=12+2=14
c=14+2=16
c=16+2=18
计算机科学系陈垚
*
例2: 汉诺塔(Hanoi)问题
B
C
问题: 将A塔上n个盘子移至C(借助于B)。移动时,保证三个塔始终是大盘在下,小盘在上,并且每次只能移动一个盘子。
A
n个盘子
计算机科学系陈垚
*
必须用递归方式解决
1) 先将A塔n –1个盘子借助于C移至B上
2) 将A上剩下的一个移至C上.
3) 将B上n –1个盘子借助于A移至C上.
可以看到:
1)、3)为同一问题,都为n –1个盘子借助于一个
空塔移至另一塔上。