C++程序设计-大模型思维与实践课件 第11章 递归

第十一章递归C++程序设计——大模型思维与实践1递归的定义3引言递归是一种编程技术，它允许一个函数直接或间接地调用自身，形成一种循环。递归函数通常会将一个大问题分解为一个或多个小问题，然后对这些小问题进行递归处理。每个递归调用都会使问题规模减小，直到达到一个基本情况，这个基本情况可以直接解决，而无需进一步的递归调用。递归可以分成直接递归和间接递归两类。直接递归指一个函数直接调用自身。例如，下面的函数f内部又调用了f函数：intf(intx)

{

intz;

z=f(x+1);

return

(2*z);

}

注意：这个函数的递归没有结束条件，会无限递归下去，直到栈溢出4引言间接递归是指一个函数通过一系列的函数调用最终调用自身。例如，下面的函数f1和f2的相互调用构成了一个间接递归的例子：注意：f1函数调用了f2函数，f2函数又调用了f1函数，形成了一个间接递归。同样，这个间接递归也没有结束条件，所以会无限递归下去，直到栈溢出。voidf1()

{

//其它语句

f2();

}

voidf2()

{

//其它语句

f1();

}间接递归在实际应用中非常罕见，因为它几乎总是导致无限循环。在设计递归函数时，应该总是确保存在明确的结束条件防止无限递归。2递归示例6计算n!例：计算n！。公式可以写成如下形式：

使用递归思想解决问题：将计算n的阶乘分解为计算(n-1)的阶乘并乘以n。5的阶乘（5!）可以看作是4的阶乘（4!）乘以5，4的阶乘（4!）又可以看作是3的阶乘（3!）乘以4，以此类推，直到1的阶乘（1!），它的值是1。1的阶乘等于1是递归的基本情况，也就是递归结束的条件。7计算n!基本情况和递归情况的设计：基本情况：递归函数中不需要进一步递归就能直接得出答案的情况。在计算n的阶乘的递归程序中，基本情况是当n等于1时。递归情况设计：定义了函数如何通过调用自身来解决问题。在计算n的阶乘时，递归情况是将n的阶乘表示为(n-1)的阶乘与n的乘积，即n!=n*(n-1)!。long

longfact(intn)

{

if

(n==

0

||n==

1)

{

return

1;

}

else

{

returnn*fact(n-

1);

}

}

intmain()

{

intnumber;

cin>>number;

cout<<number<<

"!="

<<fact(number)

<<endl;

return

0;

}程序运行结果为：55!=1208理解递归执行流程cout<<fact(5)mainreturn5*fact(4)fact:n=5return4*fact(3)fact:n=4return3*fact(2)fact:n=3return2*fact(1)fact:n=2return1fact:n=112624120long

longfact(intn)

{

if

(n==

0

||n==

1)

{

return

1;

}

else

{

returnn*fact(n-

1);

}

}

9计算n!intmain()

{

intnumber;

cin>>number;

cout<<number<<

"!="

<<fact(number)

<<endl;

return

0;

}long

longfact(intn)

{

if

(n==

0

||n==

1)

{

return

1;

}

else

{

returnn*fact(n-

1);

}

}

main内存区number5fact(5)n5long

longfact(intn)

{

if

(n==

0

||n==

1)

{

return

1;

}

else

{

returnn*fact(n-

1);

}

}

fact(4)n4longlongfact(intn){if(n==0||n==1){

return

1;

}

else{

returnn*fact(n-1);

}

}

10计算n!long

longfact(intn)

{

if

(n==

0

||n==

1)

{

return

1;

}

else

{

returnn*fact(n-

1);

}

}

long

longfact(intn)

{

if

(n==

0

||n==

1)

{

return

1;

}

else

{

returnn*fact(n-

1);

}

}

fact(4)n4fact(3)n3fact(2)n2longlongfact(intn){

if(n==0||n==1){

return

1;

}

else{

returnn*fact(n-1);

}

}

11计算n!fact(2)n2fact(1)n11212long

longfact(intn)

{

if

(n==

0

||n==

1)

{

return

1;

}

else

{

returnn*fact(n-

1);

}

}

12计算n!fact(3)n3fact(4)n426longlongfact(intn){

if(n==0||n==1){

return

1;

}

else{

returnn*fact(n-1);

}

}

4624longlongfact(intn){

if(n==0||n==1){

return

1;

}

else

{

returnn*fact(n-1);

}

}

326intmain(){intnumber;cin>>number;cout<<number<<"!="<<fact(number)<<endl;

return

0;

}12013计算n!longlongfact(intn){

if

(n==

0

||n==

1)

{

return

1;

}

else{

returnn*fact(n-1);

}

}

fact(5)n5mainnumber52452412014递归与迭代的对比鉴于问题本身的简易性，通过循环迭代方法实现显然能更直接高效地达成目标，那么为何还需引入递归这一可能使问题复杂化的手段？递归：递归，作为一种函数自我调用的机制，精髓在于将复杂问题拆解为一系列相同或相似的子问题，进而逐一解决。这一特性使得递归在处理诸如树形结构遍历、图论中的深度优先搜索等自然具备层次或嵌套结构的问题时，展现出无与伦比的逻辑清晰度和实现便捷性。15递归与迭代的对比迭代：迭代方法通过循环结构（如for、while循环）的不断迭代，直至满足既定条件，实现了对重复性任务的高效处理。迭代过程无需额外占用函数调用栈的空间（除循环控制变量等必要资源外），因此，在性能上往往优于递归，尤其适用于处理深度较大的递归问题，以避免潜在的栈溢出风险。对于某些复杂问题的迭代实现，可能需要设计者构建更为复杂的逻辑结构，以模拟递归的分解过程，从而增加了实现的难度。3斐波那契数列17设计递归程序设计递归程序例：斐波那契数列为：0,1,1,2,3,5,8,13,...，其中每个数字是其前两个数字的和。计算其第n项的公式如下：将问题分解为更小的子问题，并找到递归终止的条件（基本情况）。包括以下步骤：（1）明确问题定义明确要解决的问题是什么。上述例子中，问题为计算斐波那契数列的第n个数。

18设计递归程序（2）识别基本情况识别出递归的基本情况。上述例子中，基本情况为当n等于0或1时，斐波那契数列的值分别是0和1。这是递归的终止条件。（3）定义递归情况定义递归情况。上述例子中，递归情况为当n大于1时，通过递归调用fib(n-1)和fib(n-2)计算斐波那契数列的第n个数。这是将问题分解为更小规模的子问题的过程。（4）设计递归函数最后，根据基本情况和递归情况设计递归函数。上述例子中，需要定义一个名为fib的函数，接受一个整数n作为参数，并根据基本情况和递归情况返回相应的斐波那契数。19intfib(intn)

{

if

(n==

0)

return

0;

else

if

(n==

1)

return

1;

else

{

intn1=fib(n-

1);

intn2=fib(n-

2);

return

(n1+n2);

}

}

intmain()

{

intn=5;

inty;

y=fib(n);

cout<<y;

return

0;

}设计递归程序20理解递归执行流程

intmain()

{

intn=3;

inty;

y=fib(n);

cout<<y;

return

0;

}

intfib(intn)

{

if

(n==

0)

return

0;

else

if

(n==

1)

return

1;

else

{

intn1=fib(n-

1);

intn2=fib(n-

2);

return

(n1+n2);

}

}

intfib(intn)

{

if

(n==

0)

return

0;

else

if

(n==

1)

return

1;

else

{

intn1=fib(n-

1);

intn2=fib(n-

2);

return

(n1+n2);

}

}

main内存区f3内存区nyn33f2内存区n2n1n1F3F2F1F1F0

intfib(intn){if(n==0)

return

0;

elseif(n==1)

return

1;

else{intn1=fib(n-1);

intn2=fib(n-

2);

return

(n1+n2);

}

}

10121

intfib(intn)

{

if

(n==

0)

return

0;

else

if

(n==

1)

return

1;

else

{

intn1=fib(n-

1);

intn2=fib(n-

2);

return

(n1+n2);

}

}

f2内存区f1内存区f0内存区nnn210n11n20

intfib(intn)

{

if

(n==

0)

return

0;

else

if

(n==

1)

return

1;

else

{

intn1=fib(n-

1);

intn2=fib(n-

2);

return

(n1+n2);

}

}

F3F2F1F1F0理解递归执行流程intfib(intn){

if(n==0)

return

0;

elseif(n==1)

return

1;

else{intn1=fib(n-1);

intn2=fib(n-

2);

return

(n1+n2);

}

}

21122理解递归执行流程

intfib(intn)

{

if

(n==

0)

return

0;

else

if

(n==

1)

return

1;

else

{

intn1=fib(n-

1);

intn2=fib(n-

2);

return

(n1+n2);

}

}

f3内存区n3n11n2f1内存区n11F3F2F1F1F023理解递归执行流程

intmain(){intn=3;inty;

y=fib(n);cout<<y;

return

0;

}main内存区ny3224汉诺塔25

汉诺塔问题描述汉诺塔问题描述例：汉诺塔问题起源于一个古老的传说，其数学模型由法国数学家ÉdouardLucas在1883年提出。问题描述如下：环境设定：在一个平台上，竖立着三根相隔一定距离的针，分别标记为A、B、C。初始状态：针A上按大小顺序套叠着64个圆盘，大盘在下，小盘在上。目标状态：需要将所有圆盘从针A移动到针C上，同时保持圆盘的顺序不变，即大盘在下，小盘在上。26汉诺塔问题描述移动规则：每次只能移动一个圆盘。任何时候，任何针上的圆盘都必须保持大盘在下，小盘在上，即不能将一个较大的圆盘放在一个较小的圆盘上面。可以使用针B作为中间的辅助针，帮助完成圆盘的移动。27汉诺塔问题描述如果只有3个圆盘，如图，则移动顺序怎样？：步骤1：将最小的圆盘1从A移动到C。步骤2：将第二小的圆盘2从A移动到B。ABCn=328汉诺塔问题描述如果只有3个圆盘，如图，则移动顺序怎样？：步骤3：将圆盘1从C移动到B，现在圆盘2在B针上，圆盘1在它的上面。ABCn=329汉诺塔问题描述如果只有3个圆盘，如图，则移动顺序怎样？：步骤4：将最大的圆盘3从A移动到C。ABCn=330汉诺塔问题描述如果只有3个圆盘，如图，则移动顺序怎样？：步骤5：将圆盘1从B移动到A。步骤6：将圆盘2从B移动到C，现在圆盘3在C针上，圆盘2在它的上面。ABCn=331汉诺塔问题描述如果只有3个圆盘，如图，则移动顺序怎样？：步骤7：将圆盘1从A移动到C。ABCn=3n更大些怎么办？第1步：将问题简化假设A杆上只有2个圆盘，即汉诺塔有2层，n＝2将1号圆盘从A移到B将2号圆盘从A移到C将1号圆盘从B移到CABC设计递归程序第2步：对于一个有n（n>1）个圆盘的汉诺塔，将n个圆盘分为两部分：上面n-1个圆盘和最下面的n号圆盘。将“上面n-1个圆盘”看成一个整体将n-1个圆盘从A移到B将n号圆盘从A移到C将n-1个圆盘从B移到CACB设计递归程序34设计递归程序将问题分解为更小的子问题，并找到递归终止的条件。步骤：（1）明确问题定义：需要将n个圆盘从一根针（起始针）移动到另一根针（目标针），移动过程中可以借助一根辅助针，同时满足每次只能移动一个圆盘，且任何时候大圆盘在下，小圆盘在上。（2）识别基本情况：当只有一个圆盘需要移动时，可以直接将其从起始针移动到目标针。这是递归的终止条件。（3）定义递归情况：当有多于一个圆盘需要移动时，首先将上面的n-1个圆盘从起始针移动到辅助针，然后将最大的圆盘（第n个）从起始针移动到目标针，最后将n-1个圆盘从辅助针移动到目标针。这是将问题分解为更小规模的子问题的过程。（4）设计递归函数：定义一个名为move的函数，接受一个整数n（表示圆盘数量）和三个字符x、y、z（分别表示起始针、辅助针和目标针）作为参数，并根据基本情况和递归情况进行相应的操作。35设计递归程序voidmove(intn,charx,chary,charz)

{

if(n==1)

cout<<x<<"-->"<<z<<endl;

else

{

move(n-1,x,z,y);

cout<<x<<"-->"<<z<<endl;

move(n-1,y,x,z);

}

}intmain()

{

inth;

cout<<"inputnumber:";

cin>>h;

cout<<"thestepstomovingdiskes:\n";

move(h,'a','b','c’);

return

0;

}理解递归执行流程intmain()

{

inth;

cout<<"inputnumber:";

cin>>h;

cout<<"thestepstomovingdiskes:\n";

move(h,'a','b','c’);

return

0;

}voidmove(intn,charx,chary,charz)

{

if(n==1)

cout<<x<<"-->"<<z<<endl;

else

{

move(n-1,x,z,y);

cout<<x<<"-->"<<z<<endl;

move(n-1,y,x,z);

}

}voidmove(intn,charx,chary,charz)

{

if(n==1)

cout<<x<<"-->"<<z<<endl;

else

{

move(n-1,x,z,y);

cout<<x<<"-->"<<z<<endl;

move(n-1,y,x,z);

}

}move(3,a,b,c)move(2,a,c,b)move(1,a,b,c)move(1,c,a,b)main36理解递归执行流程voidmove(intn,charx,chary,charz){if(n==1)

cout<<x<<"-->"<<z<<endl;

else{move(n-1,x,z,y);cout<<x<<"-->"<<z<<endl;

move(n-1,y,x,z);

}

}move(3,a,b,c)voidmove(intn,charx,chary,charz)

{

if(n==1)

cout<<x<<"-->"<<z<<endl;

else

{

move(n-1,x,z,y);

cout<<x<<"-->"<<z<<endl;

move(n-1,y,x,z);

}

}move(2,a,c,b)move(1,a,b,c)voidmove(intn,charx,chary,charz)

{

if(n==1)

cout<<x<<"-->"<<z<<endl;

else

{

move(n-1,x,z,y);

cout<<x<<"-->"<<z<<endl;

move(n-1,y,x,z);

}

}move(1,c,a,b)main37理解递归执行流程voidmove(intn,charx,chary,charz){if(n==1)

cout<<x<<"-->"<<z<<endl;

else{move(n-1,x,z,y);cout<<x<<"-->"<<z<<endl;

move(n-1,y,x,z);

}

}move(3,a,b,c)move(2,a,c,b)move(1,a,b,c)move(1,c,a,b)38理解递归执行流程voidmove(intn,charx,chary,charz){if(n==1)

cout<<x<<"-->"<<z<<endl;

else{move(n-1,x,z,y);

cout<<x<<"-->"<<z<<endl;

move(n-1,y,x,z);

}

}move(3,a,b,c)voidmove(intn,charx,chary,charz)

{

if(n==1)

cout<<x<<"-->"<<z<<endl;

else

{

move(n-1,x,z,y);

cout<<x<<"-->"<<z<<endl;

move(n-1,y,x,z);

}

}voidmove(intn,charx,chary,charz)

{

if(n==1)

cout<<x<<"-->"<<z<<endl;

else

{

move(n-1,x,z,y);

cout<<x<<"-->"<<z<<endl;

move(n-1,y,x,z);

}

}move(2,b,a,c)move(1,b,c,a)move(1,a,b,c)voidmove(intn,charx,chary,charz)

{

if(n==1)

cout<<x<<"-->"<<z<<endl;

else

{

move(n-1,x,z,y);

cout<<x<<"-->"<<z<<endl;

move(n-1,y,x,z);

}

}39理解递归执行流程intmain(){inth;cout<<"inputnumber:";cin>>h;cout<<"thestepstomovingdiskes:\n";move(h,'a','b','c’);

return

0;

}4041递归中的参数传递move(3,a,b,c)voidmove(intn,charx,chary,charz)

{

if(n==1)

cout<<x<<"-->"<<z<<endl;

else

{

move(n-1,x,z,y);

cout<<x<<"-->"<<z<<endl;

move(n-1,y,x,z);

}

}3abcn:3x:a

y:bz:cvoidmove(intn,charx,chary,charz)

{

if(n==1)

cout<<x<<"-->"<<z<<endl;

else

{

move(n-1,x,z,y);

cout<<x<<"-->"<<z<<endl;

move(n–1,y,x,z);

}

}3abcn:2x:a

y:cz:bmove(3,a,b,c)move(2,a,c,b)mainmove(1,a,b,c)move(1,c,a,b)main函数：cin>>h;//输入3move(h,'a','b','c');42递归中的参数传递voidmove(intn,charx,chary,charz)

{

if(n==1)

cout<<x<<"-->"<<z<<endl;

else

{

move(n-1,x,z,y);

cout<<x<<"-->"<<z<<endl;

move(n-1,y,x,z);

}

}move(3,a,b,c)move(2,a,c,b)mainn:2x:a

y:cz:bmove(1,a,b,c)move(1,c,a,b)2acbvoidmove(intn,charx,chary,charz)

{

if(n==1)

cout<<x<<"-->"<<z<<endl;

n:1x:a

y:bz:c43递归中的参数传递voidmove(intn,charx,chary,charz){if(n==1)cout<<x<<"-->"<<z<<endl;

else{move(n-1,x,z,y);cout<<x<<"-->"<<z<<endl;

move(n-1,y,x,z);

}

}move(3,a,b,c)move(2,a,c,b)mainn:2x:a

y:cz:bmove(1,a,b,c)move(1,c,a,b)voidmove(intn,charx,chary,charz)

{

if(n==1)

cout<<x<<"-->"<<z<<endl;

n:1x:a

y:bz:c4344递归中的参数传递voidmove(intn,charx,chary,charz){if(n==1)

cout<<x<<"-->"<<z<<endl;

else{move(n-1,x,z,y);cout<<x<<"-->"<<z<<endl;

move(n-1,y,x,z);

}

}move(3,a,b,c)move(2,a,c,b)mainn:2x:a

y:cz:bmove(1,a,b,c)move(1,c,a,b)voidmove(intn,charx,chary,charz)

{

if(n==1)

cout<<x<<"-->"<<z<<endl;

n:1x:c

y:az:b2acb44递归中的参数传递move(3,a,b,c)move(2,a,c,b)mainmove(1,a,b,c)move(1,c,a,b)move(3,a,b,c)voidmove(intn,charx,chary,charz){if(n==1)cout<<x<<"-->"<<z<<endl;

else{move(n-1,x,z,y);cout<<x<<"-->"<<z<<endl;

move(n-1,y,x,z);

}

}n:3x:a

y:bz:cvoidmove(intn,charx,chary,charz){if(n==1)cout<<x<<"-->"<<z<<endl;

else{move(n-1,x,z,y);cout<<x<<"-->"<<z<<endl;move(n-1,y,x,z);

}

}n:2x:a

y:cz:b45voidmove(intn,charx,chary,charz)

{

if(n==1)

cout<<x<<"-->"<<z<<endl;

n:1x:c

y:az:b右边的执行过程和左边类似5递归程序分析47递归程序分析例11-4：请分析以下程序的执行结果：intfun(inta,

intb){

if(b==0)

returna;

else

{

return

(fun(--a,

--b)+b);

}

}

intmain(){

cout<<fun(4,2)<<endl;

return

0;

}48递归程序分析例：请分析以下程序的执行结果：main(){

fun(4,2);

}intfun(inta,

intb){

if(b==0)

returna;

elsereturn

(fun(--a,

--b)+b);

}

intfun(inta,

intb){

if(b==0)

returna;

elsereturn

(fun(--a,

--b)+b);

}

intfun(inta,

intb){

if(b==0)

returna;

elsereturn

(fun(--a,

--b)+b);

}

fun(4,2)内存区a4b2fun(3,1)内存区a23b1fun(2,0)内存区a2b0233120voidfun(intx)

{

if(x>1)

fun(x/2);

cout<<x<<““;

}

intmain()

{

fun(7);

return

0;

}intmain()

{

fun(7);

return

0;

}49递归程序分析例11-5：请分析以下程序的执行结果：voidfun(intx)

{

if(x>1)

fun(x/2);

cout<<x<<““;

}

fun(7)内存区x7fun(3)内存区x3voidfun(intx)

{

if(x>1)

fun(x/2);

cout<<x<<““;

}

intmain(){fun(7);return0;}voidfun(intx){

if(x>1)fun(x/2);

cout<<x<<““;}50递归程序分析例：请分析以下程序的执行结果：voidfun(intx){

if(x>1)fun(x/2);

cout<<x<<““;

}

fun(3)内存区x3fun(1)内存区x1voidfun(intx)

{

if(x>1)

fun(x/2);

cout<<x<<““;

}

fun(7)内存区x751递归程序分析例：请分析以下程序的执行结果：fun(7)内存区x7intmain(){fun(7);

return

0;

}voidfun(intx){

if(x>1)fun(x/2);

cout<<x<<““;

}

6应用实例53应用实例

N初始1234567鸭子数5102541266230146254应用实例代码实现intducks(intn)

{

if

(n==

7)

return

2;

else

return

2*(ducks(n+1)+1);

}

intmain()

{

cout<<ducks(1);

return

0;

}

55应用实例例11-7：递归输出一个非负整数的各个位上的数字。分析：以输出3527为例，可以先输出352的各个位上的数字，最后输出7即可。思路：对于一个非负整数n，可以将其分解为两部分：除以10的商：n/10，表示去掉最后一位的数字。模10的余数：n%10，表示最后一位数字。

通过递归调用，先处理n/10（输出它的各个位），再输出n%10

递归思想：（1）终止条件：当数字n小于10时（即只剩一位数），直接输出该数字。（2）递归步骤：分解问题：将数字n分解为高位部分（即n/10）和个位（即n%10）。递归调用：先递归输出高位部分，再输出个位。voidprint(intn)

{

if

(n<

10)

cout<<n;

else

{

print(n/

10);

cout<<

(n%

10);}

}

intmain()

{

intnum;

cin>>num;

print(num);

return

0;

}56应用实例例11-8：使用递归算法将一个十进制的非负整数转换为其它进制，并保存在数组中。常见的进制有2、8、10、16，在转换函数里，必须定义一个参数base代表目标进制。参照上例，递归的具体思想可如下设计：（1）终止条件：当数字n小于base时（即只剩一位数），直接将该数字保存到数组中。（2）递归步骤：分解问题：将数字n分解为高位部分（即n/base）和最后一位（即n%base）。递归调用：先将n/base的各位数字保存到数组中，再将最后一位n%base保存到数组中。57应用实例voidconvert(intn,

intbase,vector<char>&digits)

{

if

(n<base)

digits.push_back((n<

10)

?

(n+

'0')

:

(n-

10

+

'A'));

else

{

convert(n/base,base,digits);

intd=n%base;

digits.push_back((d<

10)

?

(d+

'0')

:

(d-

10

+

'A'));

}

}

intmain()

{

intnum,base;vector<char>result;

cin>>num>>base;

convert(num,base,result);

cout<<

"转换结果为：";

for

(inti=

0;i<result.size();i++)

{cout<<result[i];

}

return

0;

}58应用实例intmain()

{

intnum,base;

vector<char>result;

cin>>num>>base;

convert(num,base,result);

cout<<

"转换结果为：";

for

(inti=

0;i<result.size();i++)

{

cout<<result[i];

}

return

0;

}voidconvert(intn,

intbase,vector<char>&digits)

{

if

(n<base)

digits.push_back((n<

10)

?

(n+

'0')

:

(n-

10

+

'A'));

else

{

convert(n/base,base,digits);

intd=n%base;

digits.push_back((d<

10)

?

(d+

'0')

:

(d-

10

+

'A'));

}

}

voidconvert(intn,

intbase,vector<char>&digits)

{

if

(n<base)

digits.push_back((n<

10)

?

(n+

'0')

:

(n-

10

+

'A'));

else

{

convert(n/base,base,digits);

intd=n%base;

digits.push_back((d<

10)

?

(d+

'0')

:

(d-

10

+

'A'));

}

}

8C输出：8C循环输出result，这里直接给出循环后输出的结果resultmain内存区convert内存区（1）convert内存区（2）140nn816base16basebasenumdigitsdigits14016d1259应用实例例11-9：使用递归算法判断一个字符串是否为回文。回文是指一个字符串或数字，从左到右读和从右到左读完全相同。例如“madam”是一个回文字符串。boolpalin(chars[],

intleft,

intright)

{

if

(left>=right)

return

true;

if

(s[left]

!=s[right])

return

false;

returnpalin(s,left+

1,right-

1);}

intmain()

{

charstr[]

=

"madam";

intlen=strlen(str);

cout<<

(palin(str,

0,len-

1)

?

"Yes"

:

"No");

return

0;

}60应用实例intmain()

{

charstr[]

=

"madam";

intlen=strlen(str);

cout<<

(palin(str,

0,len-