第8讲B-递归函数市赛课一等奖全省微课优质课特等奖PPT课件省名师优质课赛课获奖课件市赛课一等奖课件

递归函数/11/261/56一个经过重复将问题分解为同类子问题从而处理问题方法“Thepowerofrecursionevidentlyliesinthepossibilityofdefininganinfinitesetofobjectsbyafinitestatement.Inthesamemanner,aninfinitenumberofcomputationscanbedescribedbyafiniterecursiveprogram,evenifthisprogramcontainsnoexplicitrepetitions.”NiklausWirth递归2/56阶乘n!=n*(n-1)!Fibonacci数列

f(n)=f(n-1)+f(n-2)…什么问题适合递归处理？3/56函数递归调用在调用一个函数过程中又出现直接或间接地调用该函数本身，称为函数递归调用。4/56f2函数调用f1函数函数递归调用f函数调用f函数f1函数调用f2函数直接调用本函数间接调用本函数5/56函数递归调用

例7.6有5个学生坐在一起问第5个学生多少岁？他说比第4个学生大2岁问第4个学生岁数，他说比第3个学生大2岁问第3个学生，又说比第2个学生大2岁问第2个学生，说比第1个学生大2岁最终问第1个学生，他说是10岁请问第5个学生多大6/56函数递归调用解题思绪：要求第５个年纪，就必须先知道第４个年纪要求第４个年纪必须先知道第３个年纪第３个年纪又取决于第２个年纪第２个年纪取决于第１个年纪每个学生年纪都比其前１个学生年纪大２7/567.6函数递归调用解题思绪：age(5)=age(4)+2age(4)=age(3)+2age(3)=age(2)+2age(2)=age(1)+2age(1)=108/56age(5)=age(4)+2age(4)=age(3)+2age(3)=age(2)+2age(2)=age(1)+2age(1)=10age(2)=12age(3)=14age(4)=16age(5)=18

递归边界9/56#include<stdio.h>intage(intn);intmain(){printf("NO.5,age:%d\n",age(5));return0;}

intage(intn){intc;if(n==1)c=10;elsec=age(n-1)+2;return(c);}10/56age(5)输出age(5)mainc=age(4)+2age函数n=5c=age(3)+2age函数n=4c=age(1)+2age函数n=2c=age(2)+2age函数n=3c=10age函数n=1age(1)=10age(2)=12age(3)=14age(4)=16age(5)=181811/56例7.7用递归方法求ｎ！。解题思绪：求ｎ！能够用递推方法：即从１开始，乘２，再乘３……一直乘到ｎ。递推法特点是从一个已知事实(如1!=1)出发，按一定规律推出下一个事实(如2!=1!*2)，再从这个新已知事实出发，再向下推出一个新事实(3!=3*2!)。n!=n*(n-1)!。12/56例7.7用递归方法求ｎ！。解题思绪：求ｎ！也能够用递归方法，即５！等于４！×５，而４！＝３！×４…，１！＝１可用下面递归公式表示：13/56#include<stdio.h>intfac(intn);intmain(){intn=0;inty=0;printf("inputanintegernumber:");scanf("%d",&n);y=fac(n);printf("%d!=%d\n",n,y);return0;}14/56intfac(intn){intf;if(n<0) printf("n<0,dataerror!");elseif(n==0||n==1) f=1;elsef=fac(n-1)*n;returnf;}注意溢出15/56fac(5)输出fac(5)mainf=fac(4)×5fac函数n=5f=fac(3)×4fac函数n=4f=fac(1)×2fac函数n=2f=fac(2)×3fac函数n=3f=1fac函数n=1fac(1)=1fac(2)=2fac(3)=6fac(4)=24fac(5)=12012016/56

例7.8汉诺塔（Hanoitower）问题。古代有一个梵塔，塔内有3个座A、B、C，开始时Ａ座上有64个盘子，盘子大小不等，大在下，小在上。有一个老和尚想把这64个盘子从Ａ座移到Ｃ座，但要求每次只允许移动一个盘，且在移动过程中在3个座上都一直保持大盘在下，小盘在上。在移动过程中能够利用B座。要求编程序输出移动盘子步骤。17/5664个盘子从A座移动到C座，需要移动大约264

次盘子，每1秒移动1次，则需约5840亿年18/56思绪：假如有另外一个和尚能有方法将上面63个盘子从一个座移到另一座。那么，问题就处理了。此时老和尚只需这么做：19/56转化为递归形式：(1)命令第2个和尚将63个盘子从A座移到B座(2)自己将1个盘子（最底下、最大盘子）从A座移到C座(3)再命令第2个和尚将63个盘子从B座移到C座20/56ABC……将63个从A到B第1个和尚做法21/56……ABC让第2个和尚将63个从A到B第1个和尚做法22/56……ABC自己将1个从A到C第1个和尚做法23/56……ABC自己将1个从A到C第1个和尚做法24/56……ABC让第2个和尚将63个从B到C第1个和尚做法25/56……ABC让第2个和尚将63个从B到C第1个和尚做法26/56ABC……将62个从A到C第2个和尚做法27/56ABC……让第3个和尚将62个从A到C第2个和尚做法28/56ABC……自己将1个从A到B第2个和尚做法29/56ABC……自己将1个从A到B第2个和尚做法30/56ABC……让第3个和尚将62个从C到B第2个和尚做法31/56ABC……让第3个和尚将62个从C到B第2个和尚做法32/56第3个和尚做法第4个和尚做法第5个和尚做法第6个和尚做法第7个和尚做法……第63个和尚做法第64个和尚仅做：将1个从A移到C33/56ABC将3个盘子从A移到C全过程将2个盘子从A移到B34/56ABC将3个盘子从A移到C全过程将2个盘子从A移到B35/56ABC将3个盘子从A移到C全过程将1个盘子从A移到C36/56ABC将3个盘子从A移到C全过程将1个盘子从A移到C37/56ABC将3个盘子从A移到C全过程将2个盘子从B移到C38/56ABC将3个盘子从A移到C全过程将2个盘子从B移到C39/56ABC将2个盘子从A移到B过程将1个盘子从A移到C40/56ABC将2个盘子从A移到B过程将1个盘子从A移到C41/56ABC将2个盘子从A移到B过程将1个盘子从A移到B42/56ABC将2个盘子从A移到B过程将1个盘子从A移到B43/56ABC将2个盘子从A移到B过程将1个盘子从C移到B44/56ABC将2个盘子从A移到B过程将1个盘子从C移到B45/56ABC将2个盘子从B移到C过程46/56ABC将2个盘子从B移到C过程47/56ABC将2个盘子从B移到C过程48/56ABC将2个盘子从B移到C过程49/56由上面分析可知：将n个盘子从A座移到C座能够分解为以下3个步骤：(1)将A上n-1个盘借助C座先移到B座上(2)把A座上剩下一个盘移到C座上(3)将n-1个盘从B座借助于Ａ座移到C座上50/56能够将第(1)步和第(3)步表示为：将“one”座上n-1个盘移到“two”座(借助“three”座)。在第(1)步和第(3)步中，one、two、three和A、B、C对应关系不一样。对第(1)步，对应关系是one对应A，two对应B，three对应C。对第(3)步，对应关系是one对应B，two对应C，three对应A。51/56把上面3个步骤分成两类操作：(1)将n-1个盘从一个座移到另一个座上（n＞1）。这就是大和尚让小和尚做工作，它是一个递归过程，即和尚将任务层层下放，直到第64个和尚为止。(2)将1个盘子从一个座上移到另一座上。这是大和尚自己做工作。52/56编写程序。用hanoi函数实现第1类操作（即模拟小和尚任务）用move函数实现第2类操作（模拟大和尚自己移盘）函数调用hanoi(n,one,two.three)表示将n个盘子从“one”座移到“three”座过程(借助“two”座)函数调用move(x,y)表示将1个盘子从x座移到y座过程。x和y是代表A、B、C座之一，依据每次不一样情况分别取A、B、C代入53/56#include<stdio.h>intmain(){voidhanoi(intn,charone,chartwo,charthree);intm;printf(“thenumberofdiskes:");scanf("%d",&m);printf("move%ddiskes:\n",m);

hanoi(m,'A','B','C');}54/56voidhanoi(intn,charone,chartwo,charthree){