4.6函数的递归调用（课件）-高一《程序设计基础》同步教学（江苏教育出版社）

任务六 函数的递归调用 一个函数在它的函数体内调用它自身称为递归调用。这种函数称为递归函数。在递归调用中，主调函数又是被调函数。执行递归函数将反复调用其自身，每调用一次就进入新的一层。 例如， long f（long x） { long y; z=f（y）; return z; } 这个函数是一个递归函数。但是运行该函数将无休止地调用其自身，这当然是不正确的。为了防止递归调用无终止地进行，必须在函数内有终止递归调用的手段。常用的办法是加条件判断，满足某种条件后就不再作递归调用，然后逐层返回。 任务六 函数的递归调用 【例4-6】 用递归法计算n!。 long ff（int n） { long f; if（n<0） printf（"n<0，input error"）; else if（n==0||n==1） f=1; else f=ff（n-1）*n; return（f）; } main（） { int n; long y; printf（"＼ninput a inteager number: ＼n"）; scanf（"%d"，&n）; y=ff（n）; printf（"%d!=%ld"，n，y）; } 用递归法计算n!可用下述公式表示: n!=1（n=0，1） n!=n×（n-1）!（n>1） 任务六 函数的递归调用 【例4-7】 Hanoi塔问题。 本题算法：设A上有n个盘子。 如果n=1，则将圆盘从A直接移动到C。 如果n=2，则: (1) 将A上的n-1（等于1）个圆盘移到B上。 (2) 再将A上的一个圆盘移到C上。 (3) 最后将B上的n-1（等于1）个圆盘移到C上。 如果n=3，则: (1)将A上的n-1（等于2，令其为n）个圆盘移到B（借助于C），步骤如下: ① 将A上的n-1（等于1）个圆盘移到C上。 ② 将A上的一个圆盘移到B上。 ③ 将C上的n-1（等于1）个圆盘移到B上。 (2)将A上的一个圆盘移到C上。 (3) 将B上的n-1（等于2，令其为n）个圆盘移到C上（借助A），步骤如下: ① 将B上的n-1（等于1）个圆盘移到A上。 ② 将B上的一个盘子移到C上。 ③ 将A上的n-1（等于1）个圆盘移到C上。 到此，完成了三个圆盘的移动过程。 一块板上有三根针，分别为A、B、C。A针上套有64个大小不等的圆盘，大的在下，小的在上。要把这64个圆盘从A针移动到C针上，每次只能移动一个圆盘，移动可以借助B针进行。但在任何时候，任何针上的圆盘都必须保持大盘在下，小盘在上。 任务六 函数的递归调用 从上面分析可以看出，当n≥2时，移动的过程可分解为三个步骤: (1)第一步： 把A上的n-1个圆盘移到B上。 (2)第二步： 把A上的一个圆盘移到C上。 (3)第三步： 把B上的n-1个圆盘移到C上；其中第一步和第三步是类同的。 当n=3时，第一步和第三步又分解为类同的三步，即把n-1个圆盘从一个针移到另一个针上，这里的n=n-1。 显然这是一个递归过程。 【例4-7】 Hanoi塔问题。 任务六 函数的递归调用 程序： move（int n，int x，int y，int z） { if（n==1） printf（"%c-->%c＼n"，x，z）; else { move（n-1，x，z，y）; printf（"%c-->%c＼n"，x，z）; move（n-1，y，x，z）; } } main（） { int h; printf（"＼ninput number: ＼n"）; scanf（"%d"，&h）; printf（"the step to moving %2d diskes: ＼n"，h）; move（h，a，b，c）; } 【例4-7】 Hanoi塔问题。 运行结果： input number: 4 the step to moving 4 diskes: a→b a→c b→c a→b c→a c→b a→b a→c b→c b→a c→a b→c a→b a→c b→c 任务六 函数的递归调用 任务七 数组作为函数参数 数组元素就是下标变量，它与普通变量并无区别， 因此它作为函数实参使用与普通变量是完全相同的。在发生函数调用时，把作为实参的数组元素的值传送给形参，实现单向的值传送。 1. 数组元素作函数实参 任务七 数组作为函数参数 void nzp（int v） { if（v>0） printf（"%d "，v）; else printf（"%d "，0）; } main（） { int a［5］，i; printf（"input 5 numbers＼n"）; for（i=0;i<5;i++） {scanf（"%d"，&a［i］）; nzp（a