递归调用中不明白的地方

Question

先贴下代码吧。

#include<stdio.h>
int main(void)
{
    up(1);
    return 0;
}

void up(int n)
{
    printf("rank1 %d: location %p\n", n, &n );
    if (n < 4)    
        up(n+1);
    printf("rank2 %d: location %p\n", n, &n );
}

rank1 1: location 0029FEA0
rank1 2: location 0029FE80
rank1 3: location 0029FE60
rank1 4: location 0029FE40
rank2 4: location 0029FE40 //之前认为到这一步就结束了，为什么会有接下去的3个输出
rank2 3: location 0029FE60
rank2 2: location 0029FE80
rank2 1: location 0029FEA0

不明白的地方就是：程序不能直接返回到main()中的初始调用部分吗？是因为递归的存在而导致的每一级逐步返回吗？为什么会出现4-->1的输出呢

Answer 1

我觉得可以按照这种方式来分析：

main()
    -> up(1)
    -> print rank1
        -> up(2)
        -> print rank1
            -> up(3)
            -> print rank1
                -> up(4)
                -> print rank1
                -> print rank2
                -> return to up(3)
            -> print rank2
            -> return to up(2)
        -> print rank2
        -> return to up(1)
    -> print rank2
    -> return to main()
-> return

不知道你有没有意识到问题，就是你之前的分析是假设up(4)在返回的时候是回到main()的，但实际上是返回到上一层，即up(3)。up(3)会接着执行调用up(4)的语句之后的部分，因此会打印出rank2的内容。

Answer 2

因为你的up函数调用了四次，参数分别是1、2、3、4。函数被调用后，只要中间没有return语句并且没有异常终止的话，一定会执行到最后一行才会返回的吧？

所以四次函数调用返回了四次，第二个printf必然执行了四次啊。至于为什么是从4到1，那是因为嵌套调用，返回顺序必然跟调用顺序相反啊。

你把四次对up函数的调用写成四个不同的函数：例如up1、up2、up3、up4，然后依次用前面的调用后面的就理解了。

Answer 3

每个函数 里面有两条输出啊 1到4 4次函数一共是8条
up(1) 就是 rank1 1: + up(2) + rank2 1:

Answer 4

仔细想想递归的定义你就明白了。

递归时，每个层级处理完成后就 返回上一个层级 而不是直接结束整个程序。

Answer 5

可以把递归理解成对Stack使用的简化。其实，就是函数调用栈入栈和出栈的问题。

你理解的结束只是所有的函数均已经入栈：up(1)-up(2)-up(3)-up(4)。

但是，函数调用栈必须全部出栈，递归函数才是真正的完结。而栈是FILO的数据结构，所以从栈顶开始依次出栈，就有了后续的输出。

Answer 6

很明显吧，执行rank1的打印后就要马上进入up(2)->up（3）-up(4),所以一直到up（4）的时候才不会进入up(n+1)里面去，那么就会执行4次rank1的打印，那么自然会打印rank2 4的打印，然后此方法结束，自然是up(3),因为up(3)
还没执行完毕，所以会打印 rank2 3，以次类推。

递归没什么特别的，其实还是按顺序执行，所以你还得按照顺序去看，不能因为到了最后忘记了外层要执行的方法了。

Answer 7

程序没有办法直接返回到main中。就像你认为的， 递归会逐级返回。
在你的代码中，up(n+1) 执行完成后返回到调用这个函数的地方继续执行，也就是下面的代码

printf("rank2 %d: location %p\n", n, &n );

所以你会看到显示1 --> 4 然后是 4 --> 1

另外既然你能看到最后一步， 显示rank2 4:,就应该能理解其他，因为最后一次调用会执行完毕，其他的调用也应该要执行完毕。

再多说一句，对于递归，如果看不懂，可以在纸上简单画一下流程图，调用之间的路径就很明了。

Answer 8

递归调用时默认就是一层层的入栈，一层层的出栈的过程，一来一回就是你那结果。

想直接回到初次调用部分方法很多啊，你可以记录早期的sp，直接跳过去，或者自己计算弹出函数栈。

Answer 9

递归调用是多次执行一个函数，也就是多次将一个函数压栈，请注意，这里是将整个完整的函数压栈，而栈是一个先入先出的数据结构。递归的本质其实都可以用for循环来替代。在你的代码中，递归调用函数的顺序，也就是压栈的操作是up1,up2,up3,up4.而up2的调用时间是在up1内，up3得调用时间在up3内，up4得调用在up3内，所以up1得函数是在up2出栈以后才出栈，up2是在up3出栈以后才出栈，up3是在up4出栈以后才出栈。这样推一下，你就清楚函数的执行顺序和先后出栈顺序啦！

Answer 10

不明白的地方就是：程序不能直接返回到main()中的初始调用部分吗？是因为递归的存在而导致的每一级逐步返回吗？为什么会出现4-->1的输出呢

• 有栈的调用, 遵循LIFO规则, 最后被调用的函数先结束

• 函数执行完毕后会返回直接调用它的那个函数

• 打印2的up(记为up2)函数只不过是被打印1的那个up(记为up1)函数调用的

   * up1并未结束, 他只是在等待up2结束后返回, 并再打印一个1
  

所以: 前面的1,2,3,4打印是函数调用次序, 后面的4,3,2,1是函数结束次序

Answer 11

执行4次up(),每个up()打印两条语句,最后肯定打印8条语句啊.

Answer 12

因为运行up(4)的时候，调用它的是up(3)，所以up(4)运行完毕返回的是up(3)。同理up(3)会返回up(2)，up(2)返回up(1)，因此才会有所有函数的第二次print。

Answer 13

http://www.digitaltechnologylicensing.com/mastbanda89-ride-along-2-online