【算法总结】递归

算法总结-递归

定义：

所谓递归即函数直接或间接地调用函数本身，调用的方式按照问题的不同人为定义，这种调用方式被称为递归方式。同时，为了不使这样的递归无限的发生，我们必须设定递归的出口，即当函数达到某种条件时停止递归。

问题的求解过程->划分成相同性质的子问题的求解->子问题的求解过程可以很容易地求出->这些子问题的解就构成原问题的解。

递归和枚举的区别：

枚举——把一个子问题划分成一组子问题，依次对这些子问题求解。子问题之间是横向的，同类的关系；递归——把一个问题逐级分解成子问题。子问题与原问题之间是纵向的，同类的关系。

注意：

使用递归函数务必注意递归的层数。一个程序可以使用的栈空间是有限的，当递归的过深或者每层递归所需的栈空间太大将会造成栈的溢出，使评判系统返回程序运行时异常终止的结果，一旦你的递归程序出现了这种错误，你就要考虑是否是由递归的太深而造成了爆栈。这是使用递归程序一个很重要的注意要点。具体可使用的栈大小，每个评判系统不同而有所差异，需要自行测试后确定。

套路：

待求解问题的解->输入变量x的函数f(x)通过寻找函数g(),使得f(x) = g(f(x-1)且已知f(0)的值，就可以通过f(0)和g()求出f(x)的值。

推广——扩展到多个输入变量x,y,z等，(x-1)也可以推广为(x-x1)。

要点：

递归式：如何将原问题划分成子问题。

递归出口：递归终止的条件，即最小子问题的求解，可以允许多个出口。

界函数：问题规模变化的函数，它保证递归的规模向出口条件靠拢。

例题-阶乘函数

#include<cstdio> int Factorial(int n) { if (n == 0)return 1;//递归出口 else return n * Factorial(n - 1);//递归式 } int main() { int n; scanf("%d", &n); int ans = Factorial(n); printf("the Factorial of %d is %d", n, ans); return 0; }

 

转载于:https://www.cnblogs.com/yun-an/p/11048445.html

相关资源：15个典型的递归算法的JAVA实现