孟婆汤递归问题：C++ 代码实现

孟婆汤递归问题：C++ 代码实现

孟婆想尝尝孟婆汤什么味，但是又担心自己喝了之后什么都不记得了，于是写了一张纸条贴在醒目的地方：'我想尝尝这汤什么味'。咕噜咕噜……孟婆：'我是谁？我在哪？我要干什么？' 抬头一看：'我要尝尝这汤什么味'。'好咧！' 咕噜咕噜…………

从我们的角度看来，她属于是无限递归。

现在想请你计算下面这个程序，递归 n 层之后 sum 等于多少？(sum 是全局变量)

C++ 代码

void dfs(int cnt) {  // cnt 从 1 开始 如同 dfs(1)
    for(int i = 1; i <= cnt; i++) {
    	sum++;
    }
    dfs(cnt + 2);
}

输入格式

输入一个整数 n， $0 \leq n \leq 1000$。

输出格式

输出一个整数，表示 sum 的最终结果。

样例 #1

样例输入 #1

2

样例输出 #1

4

代码实现

#include<bits/stdc++.h>
using namespace std;
int sum=0;
void dfs(int cnt){
    for(int i=1;i<=cnt;i++){
        sum++;
    }
    if(cnt+2<=1000){
        dfs(cnt+2);
    }
}
int main(){
    int n;
    cin>>n;
    dfs(1);
    cout<<sum<<endl;
    return 0;
}