求大神指导调用递归函数中的栈是怎么运行的

回溯法与树的遍历
回溯法:其求解过程实质是一个先序遍历一棵“状态树”的过程,只是这棵树不是遍历前预先建立的,而

是隐含在遍历过程中。

题目描述:求含n个元素的集合的幂集。

例:A={1,2,3},则A的幂集为{{1,2,3},{1,2},{1, 3},{2,3},{1},{2},{3},{}}

解题思路:求幂集的过程可看成是依次对集合A中的元素进行取或舍的过程。

  1.   选择合适的数据结构——假设以线性表表示集合。
    
  2.   树根结点表示幂集元素的初始状态(空集),叶子结点表示终结状态(幂集的元素),第i层表
    

示已对前i-1个元素进行了取舍的当前状态

编码:

#include "stdafx.h"
#include< iostream.h>

#define N 10

typedef struct
{
int data[N];
int length;
}SqList;

//输出线性表B
void Output(SqList& B)
{
int i;
if(B.length ==0)
cout<<"空集\n";
else
{
for(i=0;i<B.length ;i++)
cout<<B.data [i]<<"\t";
cout<<endl;
}

}

//求集合A的幂集,其中B为暂存幂集元素的线性表,i表示从第i个元素开始取舍,当
//i>n时则求得幂集的一个元素,并输出
void GetPowerSet(int i,SqList A,SqList& B)
{
int x,k,j;
if(i>=A.length )
Output(B);
else
{
x=A.data [i];
k=B.length ;
B.data [k]=x;
B.length ++;
GetPowerSet(i+1,A,B);
B.length --;
GetPowerSet(i+1,A,B);
}
}
A={1,2,3},则A的幂集为{{1,2,3},{1,2},{1, 3},{2,3},{1},{2},{3},{}}

int main(int argc, char* argv[])
{
SqList A,B;
int i;
cout<<"输入A集合的元素个数\n";
cin>>A.length ;
cout<<"输入A集合的元素\n";
for(i=0;i cin>>A.data [i];
B.length =0;
GetPowerSet(0,A,B);

return 0;
}

我不解的是第一次执行完output函数后该怎么办,如果继续执行下面的语句,即b.length--和递归函数,那第二次输出的集合显然与答案不符,求大神指点,我记得老师说过还有什么出栈的过程,求指导

4个回答

算法理解:
理解1:
宏观上我们可以这样理解:要将A上的n个盘子按照要求移动到C上,我们可以想到:先将上边的 n-1 个盘子移动到B上,再将A上剩余的最大的盘子移动到C上,然后将B上所有的盘子移动到C上,这是比较简单的理解,但是对于算法实现的过程,还是没有弄透彻。
理解2:
我们知道当盘子数为n时,移动的次数应该为 2^n-1;这个有公式 H(n) = 2H(n-1) +1 得来,理解为:上边的n-1个盘子先翻转到B上,将最大的盘子移动到C上,花费1步,然后将B上的盘子翻转到C上,花费2H(n-1)步。
后来美国的一位学者发现一种出人意料的简单的算法,只要轮流两步操作既可以实现:首先,把三张桌子按顺序首尾相接的排列,形成一个环,然后对A上的盘子开始移动,顺时针摆放成 A B C的顺序:
若n为奇数,圆盘的移动顺序是 A->C->B->A->C->B->A......... 即 间隔两个步长移动 。此处的n代表盘子位的层数,比如说 3 层汉诺塔就是从下往上数第1、3 个盘子移动的顺序。
若n为偶数,圆盘移动的顺序为A->B->C->A->B->C->A..........即 间隔一个步长移动。对n的解释同上 第二个盘子移动 A->B->C。

现在开始算法:
首先先找到能够移动的 即 A的最上边的那个盘子 如代码:
[cpp] view plaincopy
recursion_hano(n-1,A,C,B);

该调用从下往上数层数,第一次调用时是第二层的移动 应该为: A->B
第二次调用时为第三层的移动,经过两次调用B、C翻转,应该为 :A->C
........................
如此到最高层来移动第一个盘子
接下来:
A上的盘子移动过之后,我们要移动B、C上的盘子,移动策略同上
第二段代码的理解为:
[cpp] view plaincopy
moveAC(A,C);

对塔顶的两个盘子,最上层的盘子假如移动到了C上,下一层的盘子就移动到B上,因为第一段代码调用一次,B、C的顺序翻转一次。
最后一段代码的理解:
[cpp] view plaincopy
recursion_hano(n-1,B,A,C);

交换B、A的顺序是为了将 B上的盘子移动到C上,此处相当于为了实现步长为 1 的移动。

按照这样的理解,可非常清楚的了解递归每一步实现的是什么
如3阶汉诺塔的移动:A→C,A→B,C→B,A→C,B→A,B→C,A→C

楼主,您的代码有误,我就不参照您的代码回答了。在这里我举一个简单的例子,说明一下函数调用尤其是递归函数调用栈是如何增长开销的。

请题主看下面的伪代码:
func(.....)
{
if(...) return .......;//通过某种条件判断是否还要递归调用自身。

func(......);
......  //这里设置一个标志,取名叫【递归中间】吧
func(......);

return ......;

}

接下来我们来看看程序怎么递归的,当调用func时,计算机先push若干参数,设置好对应的基栈指针等,然后第一次进入func函数,按照我们的伪代码,程序先判断if条件是否为真,发现不是真,程序接着往下执行,然后在func里面遇到了调用自身的语句【func(......);】,然后计算机push参数,设置基栈指针等,程序第二次进入func函数,进入后,还是那老一套,先判断if是否为真,结果这次发现为真了,那么这次func后面所有的代码,只能永远goodbye了,因为这次的func要return了,但return后的程序要跳到哪里去执行呢?当然是上次调用func函数的语句那里了【至于计算机是怎么记住这个位置的,那是因为当初在调用时,push参数的时候顺带就把当前执行代码的位置一起push进去了】,在外面的例子中,程序就是回到了【递归中间】的那个位置,然后往下执行,结果又遇到了调用自身的语句func(......); 没办法,程序只好第三次进入func函数,还是例行公事判断if,发现是真,然后再次return,但这次return后程序所在的位置,就是func函数里面第二次调用func语句后面的位置了。return之后,程序往下执行,直至遇到func函数最后的语句,那个【return......;】,到了这里,这个func的递归表演,也就正式结束了。

题主,我的这个递归调用是比较简浅的,但所有的递归调用或互嵌调用,其本质都是共通的。希望我的回答对您会有所帮助,就这样。。。

wenpinglaoyao
纹枰老妖 楼主楼上这个链接值得一看http://www.cnblogs.com/biyeymyhjob/archive/2012/07/20/2601204.html如果这里面有不懂的,请告知我,我尽量解惑
4 年多之前 回复
wenpinglaoyao
纹枰老妖 回复qq_23865443: 至于您说的【n = 4】的执行过程的步骤,恕我拒绝。因为如果真要分析这个过程,就算我用简化的方式,估计上千字也写不下,实在是太大了啊!!因为递归这玩意,层数越多,复杂度就是指数级增长啊,见谅!!
4 年多之前 回复
wenpinglaoyao
纹枰老妖 回复qq_23865443: 首先谢谢题主您的邀答,因为您给的代码让我发现原来汉诺塔也可以这样玩,有意思!其次我仔细思考了您给的汉诺塔例子,在这里必须要说,汉诺塔递归和我举得例子简直是完美契合!我给的那段伪代码您就当成是汉诺塔代码好了,伪代码中的if对应汉诺塔中的if,汉诺塔中的else部分有两次递归调用,分别对应那两次func,而汉诺塔中的【 printf("将编号为%d的盘子直接从%c柱子移到%c柱子\n",n,A,C); 】语句则对应func中的【递归中间】标志,然后您在看看我的回答即可。
4 年多之前 回复
qq_23865443
qq_23865443 # include <stdio.h> void hannuota(int n,char A,char B ,char C) { if (1 == n) { printf("将编号为%d的盘子直接从%c柱子移到%c柱子\n",n,A,C); } else { hannuota(n-1,A,C,B); printf("将编号为%d的盘子直接从%c柱子移到%c柱子\n",n,A,C); hannuota(n-1,B,A,C); } } int main(void) { char ch1 = 'A'; char ch2 = 'B'; char ch3 = 'C'; int n ; printf("请输入要移动盘子的个数:"); scanf("%d",&n); hannuota(n,'A','B','C'); return 0; } 请大神把汉诺塔程序的详细执行过程说一下,就用n=4来说吧,还请您不吝赐教,谢谢了,真的很想1明白
4 年多之前 回复
qq_23865443
qq_23865443 # include <stdio.h> void hannuota(int n,char A,char B ,char C) { if (1 == n) { printf("将编号为%d的盘子直接从%c柱子移到%c柱子\n",n,A,C); } else { hannuota(n-1,A,C,B); printf("将编号为%d的盘子直接从%c柱子移到%c柱子\n",n,A,C); hannuota(n-1,B,A,C); } } int main(void) { char ch1 = 'A'; char ch2 = 'B'; char ch3 = 'C'; int n ; printf("请输入要移动盘子的个数:"); scanf("%d",&n); hannuota(n,'A','B','C'); return 0; } 请大神把汉诺塔程序的详细执行过程说一下,就用n=4来说吧,还请您不吝赐教,谢谢了,真的很想1明白
4 年多之前 回复
qq_23865443
qq_23865443 # include <stdio.h> void hannuota(int n,char A,char B ,char C) { if (1 == n) { printf("将编号为%d的盘子直接从%c柱子移到%c柱子\n",n,A,C); } else { hannuota(n-1,A,C,B); printf("将编号为%d的盘子直接从%c柱子移到%c柱子\n",n,A,C); hannuota(n-1,B,A,C); } } int main(void) { char ch1 = 'A'; char ch2 = 'B'; char ch3 = 'C'; int n ; printf("请输入要移动盘子的个数:"); scanf("%d",&n); hannuota(n,'A','B','C'); return 0; } 关于栈我还是不太理解,你能给我详细的说一下汉诺塔的执行过程吗?请大神不吝赐教。您就用n=4来说吧,包括栈里的数据更新也说一下
4 年多之前 回复

1)输出的结果,并不是{{1,2,3},{1,2},{1, 3},{2,3},{1},{2},{3},{}}
虽然 幂集的每个子集都是对的,但是输出顺序并非这个顺序。
2)并非每次递归调用都会输出
3) 输出和不输出之间,递归的步数,并非一致的

qq_23865443
qq_23865443 # include <stdio.h> void hannuota(int n,char A,char B ,char C) { if (1 == n) { printf("将编号为%d的盘子直接从%c柱子移到%c柱子\n",n,A,C); } else { hannuota(n-1,A,C,B); printf("将编号为%d的盘子直接从%c柱子移到%c柱子\n",n,A,C); hannuota(n-1,B,A,C); } } int main(void) { char ch1 = 'A'; char ch2 = 'B'; char ch3 = 'C'; int n ; printf("请输入要移动盘子的个数:"); scanf("%d",&n); hannuota(n,'A','B','C'); return 0; } 请大神把汉诺塔程序的详细执行过程说一下,就用n=4来说吧,还请您不吝赐教,谢谢了,真的很想1明白
4 年多之前 回复
qq_23865443
qq_23865443 # include <stdio.h> void hannuota(int n,char A,char B ,char C) { if (1 == n) { printf("将编号为%d的盘子直接从%c柱子移到%c柱子\n",n,A,C); } else { hannuota(n-1,A,C,B); printf("将编号为%d的盘子直接从%c柱子移到%c柱子\n",n,A,C); hannuota(n-1,B,A,C); } } int main(void) { char ch1 = 'A'; char ch2 = 'B'; char ch3 = 'C'; int n ; printf("请输入要移动盘子的个数:"); scanf("%d",&n); hannuota(n,'A','B','C'); return 0; } 请大神把汉诺塔程序的详细执行过程说一下,就用n=4来说吧,还请您不吝赐教,谢谢了,真的很想1明白
4 年多之前 回复

算法理解:
理解1:
宏观上我们可以这样理解:要将A上的n个盘子按照要求移动到C上,我们可以想到:先将上边的 n-1 个盘子移动到B上,再将A上剩余的最大的盘子移动到C上,然后将B上所有的盘子移动到C上,这是比较简单的理解,但是对于算法实现的过程,还是没有弄透彻。
理解2:
我们知道当盘子数为n时,移动的次数应该为 2^n-1;这个有公式 H(n) = 2H(n-1) +1 得来,理解为:上边的n-1个盘子先翻转到B上,将最大的盘子移动到C上,花费1步,然后将B上的盘子翻转到C上,花费2H(n-1)步。
后来美国的一位学者发现一种出人意料的简单的算法,只要轮流两步操作既可以实现:首先,把三张桌子按顺序首尾相接的排列,形成一个环,然后对A上的盘子开始移动,顺时针摆放成 A B C的顺序:
若n为奇数,圆盘的移动顺序是 A->C->B->A->C->B->A......... 即 间隔两个步长移动 。此处的n代表盘子位的层数,比如说 3 层汉诺塔就是从下往上数第1、3 个盘子移动的顺序。
若n为偶数,圆盘移动的顺序为A->B->C->A->B->C->A..........即 间隔一个步长移动。对n的解释同上 第二个盘子移动 A->B->C。

现在开始算法:
首先先找到能够移动的 即 A的最上边的那个盘子 如代码:
[cpp] view plaincopy
recursion_hano(n-1,A,C,B);

该调用从下往上数层数,第一次调用时是第二层的移动 应该为: A->B
第二次调用时为第三层的移动,经过两次调用B、C翻转,应该为 :A->C
........................
如此到最高层来移动第一个盘子
接下来:
A上的盘子移动过之后,我们要移动B、C上的盘子,移动策略同上
第二段代码的理解为:
[cpp] view plaincopy
moveAC(A,C);

对塔顶的两个盘子,最上层的盘子假如移动到了C上,下一层的盘子就移动到B上,因为第一段代码调用一次,B、C的顺序翻转一次。
最后一段代码的理解:
[cpp] view plaincopy
recursion_hano(n-1,B,A,C);

交换B、A的顺序是为了将 B上的盘子移动到C上,此处相当于为了实现步长为 1 的移动。

按照这样的理解,可非常清楚的了解递归每一步实现的是什么
如3阶汉诺塔的移动:A→C,A→B,C→B,A→C,B→A,B→C,A→C

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问
相关内容推荐