如何理解递归

Posted on Edited on In Word count in article: 1.2k Reading time ≈ 4 mins.
希望能加强你们对递归的理解吧

函数

函数在一任何语言里，都起着无比重要的作用。但是对初学者来说，计算机的函数可能会比较抽象，那么就先来看看数学里的函数。

数学里的函数可以简单的看作一个数集通过一定法则到另一个数集的映射。

那么，在计算机中，带有返回值的函数也可以同样理解。只不过计算机的函数的功能远远大于数学中函数的，除了得到值于值之间的关系，你可以在一个函数中写出你想拥有的任何功能 （只要你会写）。

而无返回值的函数就由此诞生了，它不需要值于值之间的对应关系，或者这个对应关系可以通过指针参数来完成导致它不需要返回值。

例如，在数学中，我们可以定义如下函数： \[ f(x)=\frac{sinx}{x} \] 同样的，在 \(C\) 语言中，我们可以通过构造一个函数实现相同的功能：

1
2
3
double f(double x) {
	return sin(x) / x;
}

当然，在 \(C\) 语言中，你可以定义很多带有多个自变量（参数）、或者更为抽象的函数：

1
2
3
4
5
6
7
8
9
10
int count_num(int x, int t) {
	int count = 0;
    while (x) {
		if (x % 10 == t) ++count;
        x /= 10;
    }
    return count;
}//统计数字x中，各位数字t出现的次数

int sort(int x[], bool cmp(int, int));//排序函数，就不细写了

至此，你可以认为，在计算机中，函数的概念是包括了数学的函数，也远大于数学的函数的。

函数的调用

在理解指针之前，先不考虑函数做参数的情况。

同样的，这个部分也可以和数学类比： \[ f(x) = g(x) + h(x) + \varphi(x) \] 那么在程序里，也可以有同样的写法：

1
2
3
4
5
6
7
8
9
int f(int x) {
	return g(x) + h(x) + phi(x);
}//都是有返回值的函数

void f(int x) {
	g(x);
    h(x);
    phi(x);
}//也有可能表示的是一种没有返回值的功能

特例：递归

其实递归与函数的调用是没有本质的区别的，无非就是调用的自己。

数学里也有类似的例子，例如： \[ 已知f(1) = 1,\;f(x) =kf(n/k), \quad 求f(k) \] 可以看见，这里也有对自己的调用。

那么这个问题用程序怎么解决？（虽然肉眼能看出来，但是写写递归有助于理解）

CODE 
1
2
3
4
double f(double x) {
    if (x == 1) return 1; 
	return x * f(1);
}

那么在来一个抽象一点的。

你站在第零级台阶（地面上），在你的面前有 \(n\) 级台阶，每次你可以跨一级或者两级台阶，问你有多少种方案可以到达第 \(n\) 级台阶？

提示：用 \(f(x)\) 表示走到第 \(x\) 级台阶的方案数

CODE 
1
2
3
4
5
int f(int x) {
	if (x == 0) return 1;
    if (x == 1) return 1;
    return f(x - 1) + f(x - 2);
}

如何理解？

已知 \(f(x)\) 表示的是走到第 \(x\) 级台阶的方案数，那么 \(f(x)\) 可以怎么表示呢？

反过来想，上一步可能在那里？

从 \(x - 1\) 跨一步到 \(x\)，从 \(x - 2\) 跨两步到 \(x\)。

那么就可以得到 \(f(x) = f(x - 1) + f(x - 2)\)

这就是斐波那契数列的一个实现方式——递归

例题 数的计算

这个题略有一些抽象，因为你可能不知道怎么用函数去表达这个答案。

那么请你再仔细读一次题，去找到一个和题目有相似之处的子问题。

想法

想知道以 \(x\) 开头的方案数，就是求所有小于等于以 \(\frac x2\) 开头的数的方案之和。

由此可以写出代码：

1
2
3
4
5
6
7
int f(int x) {
    if (x == 0) return 1;//细节处理，加零可看作就是x本身不往后添加任何数字
    int ans = 0;
    for (int i = 0; i <= x / 2; ++i)
        ans += f(i);
    return ans;
}
CODE 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <stdio.h>

int f(int x) {
    if (x == 0) return 1;//细节处理，加零可看作就是x本身不往后添加任何数字
    int ans = 0;
    for (int i = 0; i <= x / 2; ++i)
        ans += f(i);
    return ans;
}

int main () {
    int n;
    scanf ("%d", &n);
    printf ("%d\n", f(n));
    return 0;
}

当然，你也可以发现一个问题，就是这样写你拿不到满分。

为什么呢，当 \(n\) 足够大时，你会发现有很多数其实是被重复计算过了的，那么只需要用一个数组保存一下这个答案，当再次调用它时，可以直接返回这个答案。

CODE 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <stdio.h>

int count[1005] = {1};

int f(int x) {
    if (count[x]) return count[x];//已经知道答案的，就不需要再次计算了
    int ans = 0;
    for (int i = 0; i <= x / 2; ++i)
        ans += f(i);
    return count[x] = ans;
}

int main () {
    int n;
    scanf ("%d", &n);
    printf ("%d\n", f(n));
    return 0;
}

还有一个八皇后，就暂时不急了，有空了再更新一下博客吧~