C/C++ 语法教程（9）——函数（2）

wzf2000
2019年11月3日

C/C++ 语法教程（9）——函数（2）

函数（续）

函数应用进阶——递归

问题模型

我们学过一些数列的若干阶递推公式，比如斐波那契数列 $f_n = f_{n - 1} + f_{n - 2}$。

当然，根据前面的数组（可以不用）和循环语句，我们能写出递推 $f_n$ 的方法。

但如果我们想用一个函数 $f(n)$ 来计算斐波那契数列怎么办呢。

$f(n) = f(n - 1) + f(n - 2)$ 这样的 $f$ 递推式用到了 $f$ 本身，也就是函数需要调用自身。

当然，可以预想到，如果一直不断调用，这个调用无法终止。

所以我们往往需要边界值，比如 $f(0) = f(1) = 1$。

代码示例

int f(int n)
{
    if (n<=1) return 1;
    else return f(n-1)+f(n-2);
}

定义

这样的函数自己调用自己的使用方法一般就叫做递归。（当然也可以两个函数互相调用）

在分析之前我们需要先认识一下函数调用栈。

函数调用栈

思考一下代码的执行顺序：

//头文件部分（省略）
void f3()
{
    //do something...(1)
}
void f2()
{
    //do something...(2)
    f3();
    //do something...(3)
}
int f1()
{
    //do something...(4)
    f2();
    //do something...(5)
    f3();
    //do something...(6)
}
int main()
{
    f1();
    return 0;
}

如果对于程序结构有着清晰的认知，我们应该能够想到如下的执行顺序：

$f1\ (4) \to f2\ (2) \to f3\ (1) \to f2\ (3) \to f1\ (5) \to f3\ (1) \to f1\ (6)$

如果了解栈，会发现这个程序过程跟栈非常像。

栈，是一种基本的数据结构，用于存储一系列元素的数据，进出栈的顺序是先进先出。

比如说，对于上面的函数可以理解为：

$f1$ 入栈，$f2$ 入栈，$f3$ 入栈，$f3$ 出栈，$f2$ 出栈，$f3$ 入栈，$f3$ 出栈，$f1$ 出栈。
$$
\begin{array}{}
\varnothing & \to & f1 & \to & f1 & \to & f1 & \to & f1 & \to & f1 & \to & f1 & \to & f1 & \to & \varnothing \\
& & & & f2 & & f2 & & f2 & & & & f3 \\
& & & & & & f3 \\
\end{array}
$$
也就是，当一个函数（包括主函数）执行到某一步时，如果需要调用另一个函数（包括它自己）时，就会先执行另一个函数，执行完再回来执行当前函数的后续部分。

看起来调用函数就是一个将函数入栈的过程，返回（return）则是一个函数出栈的过程。

分析

根据函数调用栈的学习，我们应该能大致理解上面这个求斐波那契数列函数的调用过程了。

当然这时候你会发现，这个函数简直是在疯狂调用本身。

我们设 $T(n)$ 为计算 $f(n)$ 的时间复杂度（或者运算次数），则 $T(n) = T(n - 1) + T(n - 2) +O(1)$。

可以估计得到 $T(n) = O(f(n))$。

根据斐波那契数列的增长趋势我们可以料想到，当 $n$ 稍微大一点时，程序就很难得出结果了。

优化

为什么这种递归算法会有如此高的复杂度？究其根本还是因为计算了过多次的重复答案。

比如 $f(n - 2)$ 在 $f(n)$ 和 $f(n - 1)$ 的计算时分别被调用了一次。当然 $n$ 越小，被调用次数肯定越多。

所以我们可以设置 $a[n] = f(n)$，如果 $a[n] = 0$（也就是初值），说明 $f(n)$ 未知，否则代表 $f(n)$ 已经被计算出来过。

那么代码就可以写为：

int a[N]={1,1};
int f(int n)
{
    return a[n]?a[n]:a[n]=f(n-1)+f(n-2);
}

这样会发现，复杂度显然为 $O(n + m)$（$m$ 为询问次数），因为每个 $f(n)$ 最多被计算一次。

而且代码似乎也变得更加简单。

当然，在这里，这种优化与下面一般的递推相比，显得有些没有意义。

int a[N]={1,1};
for (int i=2;i<N;i++)
    a[i]=a[i-1]+a[i-2];

但是，在后面的数据结构与算法教程中，我们将在记忆化搜索算法中反复强调这种优化方法，那时候，就很难转化成这种简单的递推形式了。（或者转化后复杂度变高）。

递归习题

1. 用教程中所讲前后两种方法实现对于求取下面这些数列的第 $n$ 项。
   1. $f_{n+1} = a f_n^2 + bf_n + c$，其中 $a,b,c,f_1,n$ 由输入给出。
   2. $s(n,m)=s(n - 1,m - 1) + s(n - 1,m) \times m $，也就是第二类斯特林数，保证 $m \le n(s(n,m) = 0,if \ m > n)$，$S(0,0) = 1$。
2. 验证角谷定理，并输出过程：

   输入一个自然数，若为偶数，则除以 $2$，否则乘 $3$ 加 $1$，直到结果为 $1$。

   输入样例：

   7
   

   输出样例：

   7*3+1=22
   22/2=11
   11*3+1=34
   34/2=17
   17*3+1=52
   52/2=26
   26/2=13
   13*3+1=40
   40/2=20
   20/2=10
   10/2=5
   5*3+1=16
   16/2=8
   8/2=4
   4/2=2
   2/2=1
   

 教程 语法