首页
论坛
课程
招聘
[原创]递归
2007-2-24 16:45 11070

[原创]递归

2007-2-24 16:45
11070
递归
kflnig又名狂枫
    在看这篇文章之前我希望你已经看过了,我的上一篇文章《你所不知道的爆破》。那里的一丁点知识这里要用。写这篇文章的时候心情很不好!
其实见识了那个crackme中的递归我对递归已经有了更加深入的了解,考虑到还有很多不懂的朋友,所以就写了一篇。也防止自己还有不理解的地方。
以前本来就很害怕递归,总之是怎么都想不通,现在学了点汇编,就想去搞一下看看到底CPU是怎么操作了。语言,还是汇编的好!这句话肯定很遭扁!大家别骂我,我随便说的。
在我们用VC中写代码之前,我们先来设置一下。让VC输出自己的汇编代码。
工程――>设置――>c/c++――>分类中选listing file下面的列表文件类型选Assembly-only listing。不好懂,还是给大家截一张图吧。如图1


图1
好了,我们用VC写如下的代码。
#include <iostream.h>
int digui(int n);
void main()
{int c,a;
  cin>>c;
  a=digui(c);
}
int digui(int n)
{
        if (n==0)
        return -1;
                else
        {
                digui(n-1);
                cout<<n;
        };
}
太简单了是吧!可是当年,我怎么都想不通digui(n-1)这么执行之后的cout<<n怎么会执行。所以也不知道它将会输出什么。
说句鼓励的话:大家永远不要否定自己,我在写这个c代码的时候还在查if语句怎么用呢!汗颜吧!但是用过一次就知道了。对了,问大家个问题PASCL中exit对应的c语言是什么?我本来设置的递归是void的,可是exit指令我的VC不认识。《白月光》张信哲,真好听。
我们来看它的汇编代码。在我的DEBUG目录下就有一个digui.asm的文件了。我们把关键的地方提取一下。
; File D:\c++ project\digui\digui.cpp

        push        ebp
        mov        ebp, esp
        ……
        call        ??5istream@@QAEAAV0@AAH@Z        ;就是cin>>c了。 istream::operator>>
  ……
        push        ecx;变量c传值吧
        call        ?digui@@YAHH@Z                                ; digui
        add        esp, 4
        mov        DWORD PTR _a$[ebp], eax;怎么看都像a=digui(c),eax作为返回值不是吗?
  ……
        ret        0
_main        ENDP
?digui@@YAHH@Z PROC NEAR                                ; digui, COMDAT

        push        ebp
        mov        ebp, esp
        ……
        cmp        DWORD PTR _n$[ebp], 0
        jne        SHORT $L1295;

        or        eax, -1;EAX的值赋为-1,和FFFFFFFF做或运算除了FFFFFFFF可以有其它的值吗?
        jmp        SHORT $L1296;退出

        mov        eax, DWORD PTR _n$[ebp]
        sub        eax, 1
        push        eax
        call        ?digui@@YAHH@Z                                ; digui
        add        esp, 4

        mov        ecx, DWORD PTR _n$[ebp]
        push        ecx
        mov        ecx, OFFSET FLAT:?cout@@3Vostream_withassign@@A
        call        ??6ostream@@QAEAAV0@H@Z                ;就是输出了 ostream::operator<<
$L1296:
        ……
        ret        0
?digui@@YAHH@Z ENDP                                        ; digui
END
上面的代码只是我们把C语言改成了汇编,没有用啊!
现在我们便要从汇编的角度,来考虑递归。我们基本上不用去考虑main函数,因为在处理的都是我们的digui函数。所以我们把精力集中在这里。
这里我要说一句点拨的话:call和retn的作用。再说一遍吧!
retn的作用是esp=esp+4,再改变eip的值,所以retn的作用相当于pop eip。
call的作用等价于push 下一行代码的地址然后jmp到call地址。
所以我有时候思考上述递归程序的时候,是这样的:
……到底值……倒推。
上个程序的底值就是0因为n=0时这个digui就要一点点从栈里出来了。所以我们的digui已经过了一半。下一条重要指令就是retn,retn到哪里呢?我们就想到见面一个call是PUSH call的下一行地址。然后再进来这个call的。所以就retn到call的下一行。也就是输出1,接着每个retn就要一点点输出接下来的数字。
当我输入4时,上面的程序就输出的是1234。
当然思考递归并没有定式,或许你有更好的方法。
上面只是单个递归。我不会专业术语。看看来两个递归的菲波那契数列的递归写法。要是我没有记错:菲波那契数列是1  1  2  3  5  8        13        21        34……纵使错了也没关系,反正我们要求的就是第c个的值。如果有兴趣看下去的朋友要有心理准备,因为下面的文章我表述的实在不好,希望哪位朋友来写一个好的。
看代码。
#include <iostream.h>
int digui(int n);
void main()
{int c,a;
  cin>>c;
  cout<<digui(c);
}
int digui(int n)
{int b;
        if (n==1 ||n==2)
        return 1;
        else {
            b=digui(n-1)+digui(n-2);
                return b;
        }
}
此刻我来说说我的想法。先看最最关键的汇编代码。
        cmp        DWORD PTR _n$[ebp], 1
        je        SHORT $L1297
        cmp        DWORD PTR _n$[ebp], 2
        jne        SHORT $L1296
$L1297:
        mov        eax, 1
        jmp        SHORT $L1298;出去喽!
$L1296:
        mov        eax, DWORD PTR _n$[ebp]
        sub        eax, 1
        push        eax
        call        ?digui@@YAHH@Z                                ; digui
        add        esp, 4
        mov        esi, eax
        mov        ecx, DWORD PTR _n$[ebp]
        sub        ecx, 2
        push        ecx
        call        ?digui@@YAHH@Z                                ; digui
        add        esp, 4
        add        esi, eax
        mov        DWORD PTR _b$[ebp], esi
        mov        eax, DWORD PTR _b$[ebp];把返回值保存到eax中
我们换种眼光看。忽略值的计算那么就是这样的。
line1
当n=1或2时数据处理一下后,程序结束
n=n-1
PUSH n
call line1
pop n
n=n-2
PUSH n
call line1
所以好理解,OD调试时我得出的结论。假如我们输入的c=5。那么b=digui(n-1)+digui(n-2);就是先执行digui(n-1)。忽略值的计算就是在n??直到到传入参数=2后。然后digui(n-2),这里n第一次是3了。然后一下子就出去了。然后是n=4由于4-2=2所以也一下子就出去了。最后是n=5,由于5-2>2所以digui(n-1),digui(n-2)都要执行。总的看来,重复计算了好多次。我们列一下。冒号前面的表示哪个digui函数中进去的。
所以,这双递归的执行就像是V字型,先从一端入,然后到底才可以推上去。
还是来理一下吧!CPU的执行顺序:
digui(1)+digui(2)=>digui(3)
digui(3)+digui(2)=>digui(4)
digui(3)=digui(1)+digui(2)
digui(4)+digui(3)=>digui(5)
从这里我们看到说递归效率低下不是一定的。就单个递归来讲,递归的效率是等同于非递归的,但是一旦出现双递归,那么这样它的效率往往会输给递推等非递归算法,做了太多的重复计算。比如说上面的digui(3)就求了两次。
既然学习了,那么顺便写个递归的求最小公倍数,写这个东西只是为了练习。顺便这里运用了不少c++知识,也算是最近学习c++的运用吧!通常来讲递归的好处就是代码量少。这里真正的求gcd只用了这么一点,通常我们都是while或for循环。swap函数无论是用递归或者非递归都是必须的。
#include <iostream.h>
int gcd(int a,int b);
void swap(int &a, int &b)
{
        int c;
        if (a<b)
        {
                c=a;
                a=b;
                b=c;
        }
}
void main()
{
        int a,b;
        cin>>a>>b;
        swap(a,b);
        cout<<gcd(a,b);
}
int gcd(int a,int b)
{
        if (b==0) return a;
        else {a=a % b;swap(a,b);gcd(a,b);}
}
谢谢你看完了!

看雪招聘平台创建简历并且简历完整度达到90%及以上可获得500看雪币~

收藏
点赞0
打赏
分享
最新回复 (17)
雪    币: 2028
活跃值: 活跃值 (20)
能力值: ( LV9,RANK:220 )
在线值:
发帖
回帖
粉丝
阿健 活跃值 5 2007-2-25 10:33
2
0
呵呵,支持!!!
雪    币: 201
活跃值: 活跃值 (11)
能力值: ( LV12,RANK:210 )
在线值:
发帖
回帖
粉丝
sdzbyy 活跃值 5 2007-2-25 12:36
3
0
顶一下~学习
雪    币: 352
活跃值: 活跃值 (11)
能力值: ( LV9,RANK:350 )
在线值:
发帖
回帖
粉丝
hopy 活跃值 8 2007-2-27 12:01
4
0
woo!
雪    币: 218
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
JillPal 活跃值 2007-2-27 12:45
5
0
原来如此,谢谢指教!
雪    币: 104
活跃值: 活跃值 (18)
能力值: ( LV6,RANK:90 )
在线值:
发帖
回帖
粉丝
sbright 活跃值 2 2007-2-27 13:34
6
0
要是大家都象你一样学习,而不去等着那些无用动画片,就
好了
雪    币: 59
活跃值: 活跃值 (12)
能力值: ( LV12,RANK:210 )
在线值:
发帖
回帖
粉丝
jjnet 活跃值 5 2007-3-2 12:01
7
0
老实说, 讲的非常罗嗦
雪    币: 59
活跃值: 活跃值 (12)
能力值: ( LV12,RANK:210 )
在线值:
发帖
回帖
粉丝
jjnet 活跃值 5 2007-3-2 12:02
8
0
不过还是要支持的呐
雪    币: 1613
活跃值: 活跃值 (33)
能力值: (RANK:1010 )
在线值:
发帖
回帖
粉丝
北极星2003 活跃值 25 2007-3-4 18:53
9
0
kflnig的学习积极性很高,又会总结,值得鼓励!
雪    币: 200
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
dblfloat 活跃值 2007-3-6 02:13
10
0
书上都说递归最符合人的自然思维,容易理解,代码简洁.代码简洁倒是真的,可我觉得我思考那些经典的递归问题的时候一开始思维就不是递归的,呵呵.我是花了一阵时间才理解它的.最初通过一个经典的算阶乘的例子了解的.
雪    币: 200
活跃值: 活跃值 (12)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
oooooooo 活跃值 1 2007-3-6 07:48
11
0
谢谢楼主,学习,学习...
雪    币: 243
活跃值: 活跃值 (15)
能力值: ( LV12,RANK:410 )
在线值:
发帖
回帖
粉丝
王仁军 活跃值 10 2007-4-6 13:53
12
0
学习嘛就要这样,自己要钻,不能放弃。
雪    币: 202
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
WisdomZh 活跃值 2007-4-9 21:00
13
0
多递归的效率低是众所周知的
雪    币: 201
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
saltdragon 活跃值 2007-4-18 19:10
14
0
先下了。有时间看。
多谢了
雪    币: 200
活跃值: 活跃值 (10)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
ekin 活跃值 1 2007-4-19 15:02
15
0
为什么每次 call  ?digui@@YAHH@Z        ; digui
总要           add  esp, 4
使esp + 4了?
雪    币: 204
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
Ajampie 活跃值 2007-4-19 16:16
16
0
看了看,但是没有刊名百,,递归就是一种算法么,在汇编语言里面。。。还没有考虑好下面的话怎么说那
雪    币: 202
活跃值: 活跃值 (11)
能力值: ( LV9,RANK:210 )
在线值:
发帖
回帖
粉丝
blue_devil_bomb 活跃值 5 2007-4-28 22:27
17
0
树的遍历,图的遍历最短路径问题都要使用递归的思想,^_^
雪    币: 200
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
魔一天 活跃值 2007-5-26 02:56
18
0
不错,好好学习.
游客
登录 | 注册 方可回帖
返回