您好,欢迎来到北风网!

递归调用中不明白的地方

加关注
13 746
fallall fallall 2016-02-14 16:13:22 C

先贴下代码吧。

#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的输出呢

请先登录注册
5266210zxl
5266210zxl 的回复

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

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

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

2016-02-15 16:13:52 回复 0
请先登录注册
u_95740873
u_95740873 的回复

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

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

2016-02-15 16:14:24 回复 0
请先登录注册
wang_59768
wang_59768 的回复

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

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

2016-02-15 16:15:35 回复 0
请先登录注册
yingzi901
yingzi901 的回复

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

2016-02-15 16:15:49 回复 0
请先登录注册
sbearking
sbearking 的回复

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

2016-02-15 16:16:04 回复 0
请先登录注册
yinzei
yinzei 的回复

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

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

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

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

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

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

2016-02-15 16:20:27 回复 0
请先登录注册
saga012312
saga012312 的回复

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

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

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

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

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

2016-02-15 16:20:42 回复 0
请先登录注册
小芝麻先生
小芝麻先生 的回复

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

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的内容。

2016-02-15 16:20:56 回复 0
请先登录注册
faneddie
faneddie 的回复

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

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

你把四次对up函数的调用写成四个不同的函数:例如up1up2up3up4,然后依次用前面的调用后面的就理解了。

2016-02-15 16:22:09 回复 0
请先登录注册
面包小艺
面包小艺 的回复

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

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

2016-02-15 16:26:56 回复 0
请先登录注册