qq_23865443
qq_23865443
采纳率20%
2015-12-22 04:23 阅读 2.6k

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

20

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

是隐含在遍历过程中。

题目描述:求含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条回答 默认 最新

  • wenpinglaoyao 纹枰老妖 2015-12-22 07:09

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

    请题主看下面的伪代码:
    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的递归表演,也就正式结束了。

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

    点赞 1 评论 复制链接分享
  • lm_whales lm_whales 2015-12-22 05:51

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

    点赞 评论 复制链接分享
  • John_ToString John_ToString 2015-12-22 06:47
  • John_ToString John_ToString 2015-12-22 08:52

    算法理解:
    理解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

    点赞 评论 复制链接分享

相关推荐