1加到n

[[TOC]]

题目引入

TODO 对应的roj上的题目

题目描述

有$1,2 \cdots n$个这$n$个数，请使用递归的方法，来计算这$n$个数的和

输入样例

10

输出样例

55

解析1: 递归代码for循环

可以想到，这个题目能使用for循环来做：

int s = 0;
cin >> n;
for(int i =1;i<=n;i++)
    s += i;
cout << n;

但是题目要求我们使用++递归++来做，代码是如何编写呢?如下

#include <iostream>
using namespace std;

int n; //全局变量
// calc是calculate的缩写，表示计算
// a表示给的数，
// s表示前面已经加起的数的和
int calc(int a,int s)
{
    if( a == n+1)
        return s;
    return calc(a + 1, s + a);
}

int main()
{
    cin >> n;//读取数字n
    int ans = calc(1,0); //从1开始计算
    cout << ans << endl; //输出结果
    return 0;
}

同学们按照上面的代码自己写一遍，运行并输入数据，查看结果。

经过验证后，上面的代码执行的结果是正确的，如果去理解上面的代码呢？

先回忆函数的运行的过程

1. 调用函数时:根据的函数名字跳转到对应的行去执行
2. 函数执行完:再跳回运行处

例如下面的代码

#include <iostream>
using namespace std;

int n; //全局变量
int calc(int a,int s)           // <-+
{                               //   |
    if( a == n+1)               //   |
        return s;               //   |   ---+ second
    return calc(a + 1, s + a);  //   |      |
}                               //   |      |
                                //   |      |
int main()                      //   |      |
{                               //   |      |
    n = 0; //                        |      |
    int ans = calc(1,0); // first ---+      |
            //  ^                           |
            //  |                           |
            //  +---------------------------+
    cout << ans << endl;
    return 0;
}

1. 在第15行,调用calc(1,0)函数,然后跳转到第5行执行,得到a=1,s=0
2. 然后执行第7行,因为n=0,a=1,a == 0+1,所以if语句成立
3. 执行第8行,return s返回s的值,也就是0,整个函数结束
4. 然后返回到函数调用处,第15行,这一行变成int ans = 0
5. 于是ans得到一个值

上面的执行的过程,完全符合++函数执行的过程++,很好理解,只是没有执行递归而已.那如果执行了递归那代码是怎么运行的呢?看如下的代码

#include <iostream>
using namespace std;

int n; 
int calc(int a,int s)           
{                               
    if( a == n+1)               
        return s;               
    return calc(a + 1, s + a);  
} 
int main()             
{                       
    n = 2; 
    int ans = calc(1,0); 
    cout << ans << endl;
    return 0;
}

发现上面的代码,只有第13行的改变了,变成了n = 3

那么整个代码执行的过程如下图所示

1. 首先在main里面的第14行调用calc(1,0),跳转到5行,得到a=1,s=0,注意这里的a,s都是属于这层calc函数的局部变量,可以认为代码新申请了一段内存空间来存只属于这层函数的变量a,s,这层函数成为++第一层++,
2. 第一层calc执行第9行,再次调用calc(2,1),跳转到5行,得到a=2,s=0,同样变量a,s只属于这层函数，这层函数称为++第二层++
3. 第二层的calc执行第9行,再次调用calc(3,3),跳转到5行,得到a=3,s=3,同样变量a,s只属于这层函数，这层函数称为++第三层++
4. 第三层的calc执行第9行,再次调用calc(3,6),跳转到5行,得到a=3,s=6,同样变量a,s只属于这层函数，这层函数称为++第四层++
5. 第四层calc先执行if (a==n+1)成立,于是执行第8行的return s,也就是return 6，返回到第三层的第9行
6. 第三层执行return 6，返回到第二层的第9行
7. 第二层执行return 6，返回到第一层的第9行
8. 第一层执行return 6，返回到main函数的第14行

在$n=3$时,递归的执行过程一共有$8$步,其中

• 第$1 \to 5$步,我们称为递归的++前进++
• 第$5 \to 8$步,我们称为递归的++回溯++
• 第$5$步,我们称为递归的++边界++

可以想到递归必须有边界,不然递归不能停止.

怎么感性的理解上面代码执行的过程呢?

发现上面执行的过程,就是对for循环的模拟,calc的第一个参数a表示加到了第几个数,即现在正在处理数字a,前面的a-1数已经处理完了.

第二个参数s,表示前面a-1个数的和.所以边界为n+1,因为执行的$n+1$层时,就表示s的值已经是从1加到n了,也就是前面$(n+1)-1$个数已经加完了.

还可以利用小朋友法来理解.

有4个小朋友,分别叫做$1,2,3,4$,每个小朋友做的任务如下

• 第一个小朋友从提问都那里得到一个初始值:$s=0$
• 把左边的给的小朋友的值加上自己编号,得到一个新的值s,然后传递给右边的小朋友
• 最后一个小朋友,第$n+1$在进行回溯,把得到的$s$值传递给左边
• 一直回溯到第一个小朋友,然后把$s$值给提问者
• 问题解决

解析2: 分解问题

根据上面的解析,小朋友法显然更容易理解.

我们可以这样想,我们把一个问题:计算1到n的和这个问题交给一个小朋友来帮我们计算,为了方便(其实是为了少写字),我们把这个问题设为$f(n)$,那么解决$f(n)$这个问题的小朋友是一个聪明的人,于是他又找了个小朋友,问他$f(n-1)$是什么,因为$f(n) = n+f(n-1)$,$f(n-1)$这个小朋友也会继续找下一个小朋友来计算$f(n-2)$,这样一直把问题++分解++下去,最后有一个小朋友来解决$f(1)$,显然问题十分简单了,不用再分解了,这个小朋友就是边界,直接回答为$1$,这样问题不停的回溯,直到$f(n)$也解决了.

于是我们可以把上面的过程,写成下面的公式

小朋友法: 当你有一个问题的时候,你把这个问题给一个小朋友,小朋友解决这个问题的一个很小的部分,然后再把问题给下一个朋友.这样问题目不停的分解下去,最后一定会变得十分简单,直接就可以看出来,这种方法,我们称为++分解子问题法++

根据上面的公式,我们可以写出如下的代码

#include <iostream>
using namespace std;
int n;
int f(int n)
{
    //边界
    if( n == 1)
        return 1;
    return n + f(n - 1);
}
int main() {
    cin >> n;
    int ans = f(n);
    cout << ans << endl;
    return 0;
}

显然这个代码要简洁很多.