这个递归函数如何工作？

Question

可能是一个非常基本的问题,但我只是坚持下去.我试图运行以下递归函数:

   //If a is 0 then return b, if b is 0 then return a,
   //otherwise return myRec(a/2, 2*b) + myRec(2*a, b/2)

但它只是陷入无限循环.任何人都可以帮助我运行该代码并解释该函数究竟是如何工作的吗？我建立了各种递归功能,没有任何问题,但这只是在我脑海中钻了一个洞.谢谢.

这是我试图做的:

#include<iostream>

int myRec(int a, int b){

    if (a==0){
        return b;
    }

    if (b==0){
        return a;
    }
    else return myRec(a/2, 2*b) + myRec(2*a, b/2);
}

int main()
{

    if (46 == myRec(100, 100)) {
        std::cout << "It works!";
    }
}

Answer 1

好吧,让我们在心理上跟踪一下:

Starting with a, b (a >= 2 and b >= 2)  
myRec(a/2, 2*b) + something  
something + myRec(2*a', b'/2)

我们得到了代替a/2代表a'和2*b代表b' myRec(2*(a/2), (b*2)/2),这正是我们开始的地方.

因此,我们永远不会到任何地方

(请注意,我在这里省略了一些舍入,但你应该很容易看到,通过这种舍入,你只会向下舍入a到最近的偶数,此时它将永远在该数字和数字的一半之间交替)