有人可以帮助我理解函数内部的这个简单的C++操作函数

Question

我是编程和学习C++新手。我知道C++的基础知识，但我找到了这段代码

#include <iostream>
#include <string>
using namespace std;
int program(int a, int b) {
if (a > b) 
{
return 0;   
}
else 
{
return a + program(a*2+1, b);   
}
}
int main() {
cout << program(1,2018);
return 0;
}

输出：

2036

我知道如果回报只是a，显而易见的答案是1。我很困惑是program(a*2+1, b)的计算，为什么答案是 2036 年？

Answer 1

它是递归函数，每次调用它都会执行 (a*2 +1)，直到这个表达式小于 b。 所以调用堆栈看起来像

program(1   , 2018)
program(3   , 2018)
program(7   , 2018)
program(15  , 2018)
program(31  , 2018)
program(63  , 2018)
program(127 , 2018)
program(255 , 2018)
program(511 , 2018)
program(1023, 2018)

所以你的结果将是第一个参数的总和，等于 2036

Answer 2

因此，让我们进行递归：

1. 我们得到return 1 + program(3, 2018)

但是program(3, 2018)会得到什么回报呢？

它返回3 + program(7, 2018)！

但我们必须将program(3, 2018)的结果重新替换为return 1 + program(3, 2018)

所以我们得到return 1 + 3 + program(7, 2018)

这加起来return 1 + 3 + 7 + 15 + 31 + ... + program(2047, 2018)

program(2047, 2018)自 2047 年以来返回 0> 2018

因此cout << 2036

Answer 3

我将从一个更简单的问题开始。

什么是输出

cout << program(9999,2018);

？

好吧，你设置a和b，看看program的身体：

if (9999 > 2018) 
{
return 0;   
}
else 
{
return 9999 + program(9999*2+1, 2018);
}

所以

if (9999 > 2018) 

如果分支被采用，它将运行

{
return 0;   
}

答案是它打印0.

接下来，让我们看看

cout << program(2000,2018);

我们再次替换：

if (2000 > 2018) 
{
return 0;   
}
else 
{
return 2000 + program(2000*2+1, 2018);
}

现在第一个if分支条件是假的——2000 > 2018是假的——所以我们取else分支。

return 2000 + program(2000*2+1, 2018);

那么什么是program(2000*2+1, 2018)？ 首先，让我们评估一下。

program(4001, 2018)

我们不知道这一点，所以我们重复上面的分析。 我们使用与9999和2000相同的技术来求解值。

if (4001 > 2018) 
{
return 0;   
}
else 
{
return 4001 + program(4001*2+1, 2018);
}

这里

if (4001 > 2018) 

条件是true，所以我们取第一个分支和

return 0;

得到 0。 所以program(4001, 2018)的价值是0.

回头看：

return 2000 + program(4001, 2018);

我们将其替换回

return 2000 + 0;

现在我们可以解决它

return 2000;

program(2000, 2018)的值是2000。

现在，我们再次尝试program(1000, 2018). 它采用第二个分支，并返回1000 + program(2001, 2018)，在重复上述工作后变为1000+(2001+0)，然后计算结果为3001。 随意自己尝试。

。

回到原来的问题，我们看program(1,2018)：

if (1 > 2018) 
{
return 0;   
}
else 
{
return 1 + program(1*2+1, 2018);
}

这需要 else 分支，然后执行

return 1 + program(3, 2018);

所以我们接下来必须解决program(3, 2018)问题。

这称为递归程序。 当其中一个值总是增长/收缩，并且在某个边界不再执行"递归调用"之后，这样的程序很容易显示递归最终停止。

在这里我们知道这一点，因为每个递归调用上的a变大，当它通过b(每次调用都不会更改)时，它会停止递归。 因此，如果你只是通过每个评估来磨练，你最终会得到一个整个事情返回的值。