C/C++ 语法教程(9)——函数(2)

C/C++ 语法教程(9)——函数(2)

Contents

函数(续)

函数应用进阶——递归

问题模型

我们学过一些数列的若干阶递推公式,比如斐波那契数列 $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
    

 

点赞 1

No Comments

Add your comment