c++ - 递归函数(通过笔和纸帮助我理解)

首先，我不得不说我可以在像斐波那契这样的简单示例上使用递归函数，但是我不明白如何对这种递归进行空运行(用笔和纸解决):

#include<iostream>
using namespace std;

int max(int a, int b)
{
    if(a>b)return a;
    return b;
}

int f(int a, int b)
{
    if(a==0)return b;
    return max( f(a-1,2*b), f(a-1,2*b+1) );
}

int main()
{
    cout<<f(8,0);
}

我该如何使用笔和纸，比如a = 5和b = 6来做到这一点？

最佳答案

我们总是有一定深度的a(8)

每次调用都会调用2次，一次是2b，一次是2b+1传递

返回两个调用的更大结果

作为2b + 1 > 2b，只有最大调用的正确位置才有意义(2b + 1)

现在让我们以数学方式进行第一次迭代:

2 * b + 1                           = 2^1 * b + 2^0
2 * (2^1 * b + 2^0) + 1             = 2^2 * b + 2^1 + 2^0
2 * (2^2 * b + 2^1 + 2^0) + 1       = 2^3 * b + 2^2 + 2^1 + 2^0
2 * (2^3 * b + 2^2 + 2^1 + 2^0) + 1 = 2^4 * b + 2^3 + 2^2 + 2^1 + 2^0

如您所见，背后有一个系统。因为b = 0是第一次迭代，所以我们可以忽略左侧。因此，最终值为:

2^0 + 2^1 + 2^2 + 2^3 + 2^4 + 2^5 + 2^6 + 2^7
=
1 + 2 + 4 + 8 + 16 + 32 + 64 + 128
=
255

如果我们运行程序，我们将获得完全相同的值

关于c++ - 递归函数(通过笔和纸帮助我理解)，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/21099619/