递归与递推

递归与递推

1 递归

1.1 介绍

函数调用自身的编程技巧称为递归。递归做为一种算法有广泛的应用。递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量。一般来说,递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时,递归前进;当边界条件满足时,递归返回。

1.2 应用

递归算法一般用于解决三类问题:

  1. 数据的定义是按递归定义的

比如斐波那契数列,其有:

$$ F[n]=\left\{\begin{matrix} F[n-1]+F[n-2]&,&x \geq 2\\ 1&,&x=0,x=1 \end{matrix}\right. $$
  1. 问题解法按递归算法实现

这类问题虽则本身没有明显的递归结构,但用递归求解比迭代求解更简单,如汉诺塔问题。

  1. 数据的结构形式是按递归定义的

二叉树🎄,由于结构本身固有的递归特性,则它们的操作可递归地描述。

1.3 缺陷

递归算法解题相对常用的算法如普通循环等,运行效率较低。因此,应该尽量避免使用递归,除非没有更好的算法或者某种特定情况,递归更为适合的时候。在递归调用的过程当中系统为每一层的返回点、局部量等开辟了来存储。递归次数过多容易造成栈溢出❌等问题。

1.4 实例-求斐波那契数(一)*

假定你有一雄一雌一对刚出生的兔子🐇,它们在长到一个月大小时开始交配,在第二月结束时,雌兔子产下另一对兔子🐇,过了一个月后它们也开始繁殖,如此这般持续下去。每只雌兔在开始繁殖时每月都产下一对兔子🐇,假定没有兔子🐇死亡,在一年后总共会有多少对兔子🐇?

在一月底,最初的一对兔子🐇交配,但是还只有1对兔子🐇;在二月底,雌兔🐇产下一对兔子🐇,共有2对兔子🐇;在三月底,最老的雌兔🐇产下第二对兔子🐇,共有3对兔子🐇;在四月底,最老的雌兔产下第三对兔子🐇,两个月前生的雌兔产下一对兔子🐇,共有5对兔子🐇;……如此这般计算下去,兔子🐇对数分别是:1, 1, 2, 3, 5, 8, 13, 21, 34, 55,89, 144, ...看出规律了吗?(J型增长✔)从第3个数目开始,每个数目都是前面两个数目之和。这就是著名的斐波那契数列。

斐波那契数列定义就是上面的:

$$ F[n]=\left\{\begin{matrix} F[n-1]+F[n-2]&,&x \geq 2\\ 1&,&x=0,x=1 \end{matrix}\right. $$

怎么实现一个求斐波那契数的函数呢?

代码如下。

  • 例1.4.1
long long Fibonacci(int n)
{
    if (n<=1) return 1;
    return Fibonacci(n-1)+Fibonacci(n-2);
}

效率怎么样呢?让我们来实际模拟一下$n=4$时的计算,函数的调用顺序为:

$$ Fibonacci(4) \rightarrow Fibonacci(3) \rightarrow Fibonacci(2) \rightarrow Fibonacci(1) \rightarrow Fibonacci(2) $$ $$ \rightarrow Fibonacci(0) \rightarrow Fibonacci(2) \rightarrow Fibonacci(3) \rightarrow Fibonacci(1)\rightarrow Fibonacci(3) $$ $$ \rightarrow Fibonacci(4)\rightarrow Fibonacci(2) \rightarrow Fibonacci(1) \rightarrow Fibonacci(2) \rightarrow Fibonacci(0) $$ $$ \rightarrow Fibonacci(2) \rightarrow Fibonacci(4) $$

是不是还有点晕的😵?一定要自己体会一下

看上去程序的递归使用很恰当,可是我们会发现反复的调用了已经运算过的部分,也就是有一些操作是多余的。其实,这违反了递归的一个规则:合成效益法则

  • 合成效益法则(Compound interest rule):在求解一个问题的同一实例的时候,切勿在不同的递归调用中做重复性的工作。

所以需要修改一下程序,使得每个$F(n)(0\leq n \leq 4)$计算一次即可。

代码如下。

  • 例1.4.2
int f[1000005];
long long Fibonacci(int n)
{
    if (n<=1) return 1;
    if (!f[n]) 
    	f[n]=Fibonacci(n-1)+Fibonacci(n-2)
    return f[n];
}

这样,计算过的值会直接被返回而不是重新计算,有效的节省了大量时间,这样的方法叫做记忆化它也是动态规划实现的一种方式

2 递推

2.1 介绍

递推是按照一定的规律来计算序列中的每个项,通常是通过计算前面的一些项来得出序列中的指定项的值。其思想是把一个复杂的庞大的计算过程转化为简单过程的多次重复,该算法利用了计算机速度快和不知疲倦的机器特点。

2.2 递推公式

如果数列${ a_n }$的第n项与它前一项或几项的关系可以用一个式子来表示,那么这个公式叫做这个数列的递推公式。例如斐波纳契数列的递推公式为$a_n=a_{n-1}+a_{a-2}(n \geq 2)$。(数列从$a_1$开始

由数列的递推公式可以推出数列的通项公式。这可以使得算法的时间效率大大提升

2.3 递推类型

递推关系是递推的核心。常见的递推关系有:

  1. 一阶递推

在计算$a_n$时,只用到前面项中的一项,如等差数列。

  1. 多阶递推

在计算$a_n$时,要用到前面计算过的多项,如Fibonacci数列。

  1. 间接递推

在计算$a_n$时需要中间量,而计算中间量要用到之前计算过的项。

  1. 逆向递推

顾名思义,就是从后面开始往前推。

  1. 多维递推

元素处于一个多维矩阵中,递推需要使用矩阵中其他位置的元素。

2.4 再谈-求斐波那契数(二)

之前介绍了如何利用递归来求斐波那契数,现在来讨论一下如何用递推求斐波那契数。

由递推公式$a_n=a_{n-1}+a_{a-2}(n \geq 2)$和初始条件$a_1=a_2=1$可以写出,代码如下。

  • 例2.4.1
a[1]=a[2]=1;
for (int i=3;i<=n;i++)
    a[i]=a[i-1]+a[i-2];

还有一种逆推的思想,代码如下。

  • 例2.4.2
a[1]=1;
for (int i=1;i<=n-1;i++)
{
    a[i+1]+=a[i];
    a[i+2]+=a[i];
}

当然还有一种更简单的方法,即用由斐波那契数列的递推公式求得的通项公式来直接计算斐波那契数。斐波那契数列的通项公式为

$$ a_n=\frac{1}{\sqrt{5}}\left [ \left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right ] $$

求通项公式的过程很复杂,不介绍。这样计算的时间复杂度为$O(logn)$。(取决于幂运算

2.5 实例-平面分割问题

  • 问题1:现在给你一个平面和n条线,请问最多能将平面分割成多少个小的平面?

让我们来实际操作一下。可以看出怎样的规律?请仔细思考再往下看

平面分割

可以发现,新画的一条线在经过每条已经画的线都会产生一个新的平面。在这里,封闭的曲线看成一条线。那这样问题就十分简单了。我们可以很容易得到递推式和初始条件:

$$ a_n=a_{n-1}+n-1(n \geq 2),a_1=1 $$

这样便可以写出代码了,代码如下。

  • 例2.5.1
a[1]=1;
for (int i=2;i<=n+1;i++)  //n条线,求n+1项
    a[i]=a[i-1]+i-1;

求出通项公式的方法更快,来试着求一下:

$$ a_n=a_1+1+2+3+...+(n-2)+(n-1)=a_1+\frac{n \times (n-1)}{2}=\frac{1}{2}n^2-\frac{1}{2}n+1 $$

所以,当通项公式简单易求时,可以用通项公式来代替递推。

  • 问题2:现在给你一个平面和n条线,其中有m(m<=n)条相交于一点的线,请问最多能将平面分割成多少个小的平面?

这个简单。我们只需要先求出m条相交于一点的直线所分割的平面数加上n-m条线在前面的基础上分割出的平面数就可以了,代码请自行实现。

  • 问题3:现在给你一个平面和n条封闭曲线,且封闭曲线只能两两相交,请问最多能将平面分割成多少个小的平面?

这个与之前的条件有所不同,请思考一下再往下看

平面分割2

思路1:可以发现,新加进来的封闭曲线把之前的封闭曲线分出的平面都分成了两半。

思路2:把n=1设为初始状态,每个新加来的封闭曲线被每个已经存在的封闭曲线切成两半,可以将切出来的弧看成直线,这样就与问题一的做法相同,对照即可。

这样递推关系和初始条件为:

$$ a_n=2a_{n-1}(n \geq 2),a_1=2 $$

代码和通项公式请自己完成。

2.6 递推与动态规划

递推和动态规划是什么关系?很多人说递推就是动态规划,这是不对的。

递推不是动态规划。动态规划也不是算法。动态规划是一种思想,而这种思想可以由递推记忆化搜索来实现,再者,动态规划有决策的过程,而不是单纯的递推。


感谢浏览😝!

此文章可能会在后续更新,欢迎纠错。