首页 IT技术

递归调用详解(图文并茂)

时间:2019-11-06 15:14:29 分类:IT技术

递归调用

**

本文主要依据C程序设计(第四版) 谭浩强著,这本书Hanoi的实例,详细讲解递归调用

。**

代码如下

#include<stdio.h>

void move(int x, int y)
{
	printf("%c--->%c\n", x, y);
}
void hanoi(int n, char one, char two, char three)
{
	if (n == 1)
		move(one, three);
	else
	{
		hanoi(n - 1, one, three, two);
		move(one, three);
		hanoi(n - 1, two, one, three);
	}
}

int main()
{
	int m;
	printf("input the number of diskes:");
	scanf("%d",&m);
	printf("the step to move %d diskes:\n",m);
	hanoi(m, 'A', 'B', 'C');
}

看图说明:黑色箭头代表回溯阶段,橘色箭头代表逆推阶段,箭头上的数字代表整个递归程序运行的顺续。本例设盘数n==3…

在main函数的调用中,传递给Hanoi的参数列表为(3,A,B,C)A->one,B->two,C->three…。然后进入到选择语句,执行Hanoi(3-1,one,three,two),由于Hanoi(3-1,one,three,two)的参数列表中的参数顺序已经改变,由one,two,three变为one,three,two,所以此时传过来的参数变为Hanoi(2,A,C,B),当执行Hanoi(2-1,one,three,two)时,参数列表又变为Hanoi(2,A,B,C)。。。。。此后调用参数的变化情况与之类似。

说明:当再次调用Hanoi时,此时参数列表中每个参数位置上的参数的内容(one,three,two)对应到上次函数参数列表中每个对应位置上的参数。

例如:上次函数参数列表为(3,one(A),two(B),three©) -->(3,A,B,C)

下次调用时参数列表为(3-1,one(A),three©,two(B)) -->(2,A,C,B)

再次调用时参数列表为(2-1,one(A),three(B),two©) -->(1,A,B,C)

move(one,three)函数中的one,three对应当前函数体中函数参数列表,第一,三位置上的参数。

第一步:main函数调用Hanoi(3,A,B,C);

第二步:经判断语句,调用 Hanoi(3-1,one,three,two)–> Hanoi (2,A,C,B) 。第一个箭头所示步骤

第三步:经判断语句,调用 Hanoi(2-1,one,three,two)–> Hanoi (1,A,B,C) 。第二个箭头所示步骤

第四步:经判断语句,执行move(one,three) -->move(A,C) 。

第五步:返回到 Hanoi(2-1,one,three,two)的位置,继续执行下一行语句 。第三个箭头所示步骤

第六步:执行move(one,three) -->move(A,B)

第七步:调用 Hanoi(2-1,two,one,three)–> Hanoi (1,C,A,B) 。第四个箭头所示步骤

第八步:经判断语句,执行move(one,three) -->move(C,B)

第九步:返回到 Hanoi(2-1,two,one,three)的位置 。第五个箭头所示步骤

第十步:返回到 Hanoi(3-1,one,three,two)的位置 。第六个箭头所示步骤

第十一步:执行move(one,three)–>move(A,C),继续执行下一行语句

第十二步:调用 Hanoi(3-1,two,one,three)–> Hanoi (2,B,A,C) 。第七个箭头所示步骤

第十三步:经判断语句, 调用 Hanoi(2-1,one,three,two)–>Hanoi(1,B,C,A)。 第八箭头所示步骤

第十四步:经判断语句,执行move(one,three) -->move(B,A)

第十五步:返回到 Hanoi(2-1,one,three,two)的位置,继续执行下一条语句。第九个箭头所示步骤

第十六步:执行move(one,three)–>move(B,C)

第十七步:调用 Hanoi(2-1,two,one,three)–> Hanoi (1,A,B,C) 。第十个箭头所示步骤

第十八步:经判断语句,执行move(one,three)–>move(A,C)

第十九步:返回到 Hanoi(2-1,two,one,three)的位置。第十一个箭头所示步骤

第二十步:返回到 Hanoi(3-1,two,one,three)的位置。第十二个箭头所示步骤

OVER

递归调用示意图

文章最后发布于: 2019-04-07 14:33:26

推荐文章

重点栏目推荐