频道栏目
首页 > 资讯 > C语言 > 正文

一步一步写算法(之递归和堆栈)

11-10-21        来源:[db:作者]  
收藏   我要投稿

 

【 声明:版权所有,欢迎转载,请勿用于商业用途。  联系信箱:feixiaoxing @163.com】

 

 

 

 

    看过我前面博客的朋友都清楚,函数调用主要依靠ebp和esp的堆栈互动来实现的。那么递归呢,最主要的特色就是函数自己调用自己。如果一个函数调用的是自己本身,那么这个函数就是递归函数。

 

    我们可以看一下普通函数的调用怎么样的。试想如果函数A调用了函数B,函数B又调用了函数C,那么在堆栈中的数据是怎么保存的呢?

 

 

view plaincopy to clipboardprint?函数A    ^ 

函数B    |    (地址递减) 

函数C    | 

函数A    ^

函数B    |    (地址递减)

函数C    |    如果是递归函数呢,举一个简单的递归函数为例:

 

 

view plaincopy to clipboardprint?int iterate(int value) 

    if(value == 1) 

        return 1; 

    return value + iterate(value -1); 

int iterate(int value)

{

       if(value == 1)

              return 1;

       return value + iterate(value -1);

}    下面我们使用一个函数进行调用,看看会发生什么情况?

 

 

view plaincopy to clipboardprint?void process() 

    int value = iterate(6); 

void process()

{

       int value = iterate(6);

}    看看此时内存堆栈是什么样的?

 

 

view plaincopy to clipboardprint?iterate(int 1) line 96 

iterate(int 2) line 97 + 12 bytes 

iterate(int 3) line 97 + 12 bytes 

iterate(int 4) line 97 + 12 bytes 

iterate(int 5) line 97 + 12 bytes 

iterate(int 6) line 97 + 12 bytes 

process() line 102 + 7 bytes 

main() line 108 

mainCRTStartup() line 206 + 25 bytes 

KERNEL32! 7c817067() 

iterate(int 1) line 96

iterate(int 2) line 97 + 12 bytes

iterate(int 3) line 97 + 12 bytes

iterate(int 4) line 97 + 12 bytes

iterate(int 5) line 97 + 12 bytes

iterate(int 6) line 97 + 12 bytes

process() line 102 + 7 bytes

main() line 108

mainCRTStartup() line 206 + 25 bytes

KERNEL32! 7c817067()

    大家也看到了上面的代码,递归函数和普通的函数也没有什么差别。除了自己调用本身之外,他就是一个普通的函数。那么这个函数递归到什么时候返回呢?这就是递归函数的关键了。我们看到iterate函数到1就停止了,所以上面的堆栈在(value == 1)即return。所以一个递归函数最关键的部分就是两点:(1)递归策略;(2)函数出口。

 

    看到这里,大家可能感到递归函数不过如此,事实上也是这样。但是,还有一点大家需要牢记在心,递归的深度是我们必须考虑的一个问题。只有递归深度在一个可控的范围内,那么整个递归过程都是可控的。那什么时候不可控呢?那就是递归深度超过了一定的数字?这个数字和具体的线程堆栈长度有关?等到堆栈溢出了,那么获得的数据已经失去了真实性,所以也就没有意义了。

 

    我们把上面的问题推广一下,如何用自己定义的堆栈模拟上面的递归调用呢?这样既能满足递归的属性,又能确保函数深度可控。

 

    大家可以先写一下自己的方案,下面只是我个人的一个思路。

 

 

view plaincopy to clipboardprint?int iterate(int value) 

    int count = 0; 

    int number  =0; 

 

    push(value); 

    while(-1 != (number = pop())) 

    { 

        if(1 != number) 

            push(number -1); 

        count += number; 

    } 

 

    return count; 

int iterate(int value)

{

       int count = 0;

       int number  =0;

 

       push(value);

       while(-1 != (number = pop()))

       {

              if(1 != number)

                     push(number -1);

              count += number;

       }

 

       return count;

}

 

 

 

 

 

 

 

【预告: 下面一篇博客介绍算法和内存】

相关TAG标签
上一篇:一步一步写算法(之查找)
下一篇:面试知识总结(一)
相关文章
图文推荐

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站