c++ - 递归函数(纸笔帮我理解)

Question

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

#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？

Answer 1

1. 我们的深度总是a (8)
2. 每次调用都会调用自身 2 次，一次 2b 和一次 2b+1 传递
3. 返回两次调用中较大的结果
4. 因为 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

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