递归
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);}
}
谢谢你看完了！

[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课