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