递归方法

Question

我很难掌握递归。例如我有以下方法。当 if 语句 return 为真时，我希望从该方法中得到 return。但是查看 Windbg 中的方法执行，Visual Studio 表明该方法继续执行。对于一般性问题，我深表歉意，但非常感谢您的反馈。

N如何递减以满足if条件？

long factorial(int N)
{
    if(N == 1)
        return 1;
    return N * factorial(N - 1);
}

Answer 1

我认为最好的掌握方法是手动完成代码。假设你调用 factorial(4)，会发生什么？4 不等于 1。Return 4 * factorial(4-1).

阶乘 3 的 return 值是多少？ 3 不等于 1 return 3* 阶乘(3-1).

阶乘 2 的 return 值是多少？ 2 不等于 1 return 2* 阶乘(2-1).

阶乘 1 的 return 值是多少？ 1 等于 1 为真。 Return 1. 这是基本情况。现在我们回到递归。 Return 1. 这是阶乘 (2-1) Return2*1。这是阶乘 (3-1) Return 3*2 这是阶乘(4-1) Return 4*6 这是 factorial(4)，你最初的调用。

你的想法是你有一个具有基本情况的函数（当 n=1 return 1 时）并且该函数以将函数移向基本情况的方式调用自身（阶乘（n** -**1))。

Answer 2

编译和反汇编函数你应该得到一个类似这样的反汇编

0:000> cdb: Reading initial command 'uf fact!fact;q'
fact!fact:
00401000 55              push    ebp
00401001 8bec            mov     ebp,esp
00401003 837d0801        cmp     dword ptr [ebp+8],1
00401007 7507            jne     fact!fact+0x10 (00401010)

fact!fact+0x9:
00401009 b801000000      mov     eax,1
0040100e eb13            jmp     fact!fact+0x23 (00401023)

fact!fact+0x10:
00401010 8b4508          mov     eax,dword ptr [ebp+8]
00401013 83e801          sub     eax,1
00401016 50              push    eax
00401017 e8e4ffffff      call    fact!fact (00401000)
0040101c 83c404          add     esp,4
0040101f 0faf4508        imul    eax,dword ptr [ebp+8]

fact!fact+0x23:
00401023 5d              pop     ebp
00401024 c3              ret
quit:

让我们假设在输入函数时 N == 5 即 [ebp+8] 将保留 5 只要 [ebp+8] > 1 jne 就会被占用

在这里你可以看到 N 正在递减 (sub eax ,1) 递减的 N 再次传递给函数 fact（在没有 return 的情况下递归返回给调用者）循环再次发生并且递减的 N 被重新发送到 fact 这一直发生直到 jne 不被采用，直到 N 或[ebp+8] == 1

当N变为1时jne不被取而jmp 401023被取其中 returns 到调用者调用者是函数 fact(int N)

那就是 return 40101c，其中 eax 的乘法发生，结果存储回 eax；

这将一直发生，直到 ret 指向 main() 中的第一个调用，请在第一次执行 pop ebp 之前查看下面的堆栈

0:000> kPL
ChildEBP RetAddr  
0013ff38 0040101c fact!fact(
            int N = 0n1)+0x23
0013ff44 0040101c fact!fact(
            int N = 0n2)+0x1c
0013ff50 0040101c fact!fact(
            int N = 0n3)+0x1c
0013ff5c 0040101c fact!fact(
            int N = 0n4)+0x1c
0013ff68 0040109f fact!fact(
            int N = 0n5)+0x1c
0013ff78 0040140b fact!main(
            int argc = 0n2, 
            char ** argv = 0x00033ac0)+0x6f

递归方法

Recursive methods

visual-studio-2010

recursion

windbg