递归算法是什么意思?哪些算法题中可以使用递归?

什么是递归

递归是在方法的内部调用自己的方法,所有具有自己调用的方法都是递归的

如果你在谷歌上搜索递归,那么你将会看到如下的信息。

当你点击红色框中的递归,然后看到的还是这个页面,直到你明白递归。会不会是谷歌调皮了?这个问题有待研究。

递归算法是什么意思?哪些算法题中可以使用递归?

递归是一种神奇的算法,是编程书籍中最笨拙的部分。 这些书通常会向您展示递归阶乘实现,然后会警告您,尽管它可以工作,但它非常慢,并且可能溢出和崩溃。 虽然人们对此表示怀疑,但这并不影响递归是该算法中最强大的想法。

第一次接触递归

递归算法在数学阶乘的计算中敏锐而生动地体现,阶乘是置换组合的结果,任何大于1的自然数n都可以表示为:n! = 1 x 2 x 3 x …x n。另外,0!=1;

现在来看这个问题,确实是太简单了,因此我这里就给大家找了一个求6的阶乘图,让大家理解一下。

递归算法是什么意思?哪些算法题中可以使用递归?

有兴趣的朋友呢,可以尝试手动编写一下这个程序,绝大多数的编程语言都可以实现。我这里给大家一个C++版本的。也是教科书上的源码程序给大家参考一下。

#include <iostream>
using namespace std;
int  Factorial(int n){
	int sum=0;          //定义一个累乘的sum量
	if(n==0)return 1;         //递归结束出口,当递归到n=0时,返回1值
	else{                     
		sum=n*Factorial(n-1); //递归调用
	}
	return sum;
}

int main()
{
	int n;
	int sum;
	cin>>n;
	sum=Factorial(n);
	cout<<sum;
	return 0;
}

另外,在教科书中还有一个练习题就是,斐波那契数列。这个我在这里就不给大家说了,大家有兴趣的话呢,可以去了解一下。是一个非常有意思的数列。

那些算法题中可以使用递归?

数据的定义是按递归定义的。如Fibonacci函数。

问题解法按递归算法实现。如Hanoi问题。

数据的结构形式是按递归定义的。如二叉树、广义表等。

在常见的算法面试题中,我们会经常使用递归来解决一些问题。一般来说,能用递归解决的问题,那么使用动态规划也可以解决。

动态规划的三要素

一、最优子结构

二、边界

三、状态转移方程

这三点在我的算法面试详解的视频中都有详细描述。

总结

递归和动态规划的区别是,递归是自顶向底解决问题,动态规划是自底向顶解决问题。

递归在某些算法题中需要进行剪枝。如果不进行剪枝,那么递归就会进行很多重复的计算,因此使用递归需要进行剪枝优化,通常来说动态规划比递归更优。

但是动态规划的难点在于最优子结构的选择以及寻找状态转移方程。这些都是需要平常的积累。

所以,只有当你做了大量的算法练习题之后,你就能够清楚的了解递归和动态规划思想。

声明:本文由会火号官方原创,如若转载,请注明出处:https://www.huihuohao.com/s/2226.html

发表评论

登录后才能评论