递推与递归（区别）

2024-07-12 08:42| 来源: 网络整理| 查看: 265

递推与递归

本文中部分内容转自他人博客，作者相关信息以及博客地址在文末。

概念递归：从已知问题的结果出发，用迭代表达式逐步推算出问题的开始的条件，即顺推法的逆过程，称为递归。

递归的定义：在一个函数的定义中又直接或间接地调用本身。

递归思想：把规模大的、较难解决的问题变成规模较小的、易解决的同一问题。规模较小的问题又变成规模更小的问题，并且小到一定程度可以直接得出它的解，从而得到原来问题的解。

递归优点：符合人的思维方式，递归程序结构清晰，可读性，容易理解

递归缺点：通过调用函数实现，当递归层数过多时，程序的效率低。例如求Fibonacii数列的第1000项?

递归的应用场合：

1、数据的定义形式是递归的，例如求Fibonacii数列的第n项。

2、数据之间的逻辑关系（即数据结构）是递归的，如树、图等的定义和操作。

3、某些问题虽然没有明显的递归关系或结构，但问题的解法是不断重复执行一组操作，只是问题规模由大化小，直至某个原操作（基本操作）就结束。例如：汉诺塔问题。

递归设计的要素：

1、在函数中必须有直接或间接调用自身的语句；

2、在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口（或递归边界）。

编写递归算法时，首先要对问题的以下三个方面进行分析：决定问题规模的参数。

需要用递归算法解决的问题，其规模通常都是比较大的，在问题中决定规模大小（或问题复杂程度）的量有哪些？把它们找出来。

问题的边界条件及边界值。

在什么情况下可以直接得出问题的解？这就是问题的边界条件及边界值。

解决问题的通式。

把规模大的、较难解决的问题变成规模较小、易解决的同一问题，需要通过哪些步骤或公式来实现？这是解决递归问题的难点。把这些步骤或公式确定下来。

递推：递推算法是一种用若干步可重复运算来描述复杂问题的方法。递推是序列计算中的一种常用算法。通常是通过计算机前面的一些项来得出序列中的指定象的值。

递推：数学推导发现规律重复简单运算

递归与递推区别：相对于递归算法,递推算法免除了数据进出栈的过程，也就是说,不需要函数不断的向边界值靠拢,而直接从边界出发,直到求出函数值。算法举例1

斐波那契数列：已知f(1) = 1 , f(2) = 1 , 且满足关系式f(n) = f(n-1) + f(n-2)，则f(50)等于多少？

分析：根据初始条件f(1) = 1 , f(2) = 1 和关系式f(n) = f(n-1) + f(n-2)，可知，f(3) = f(2) + f(1) , f(3) = f(2) + f(1) …….

编写代码（递归） public class Fibonacci { static int fun(int n){ if(n == 1 || n == 2){ return 1 ; }else{ return fun(n-1) + fun(n-2) ; } } public static void main(String[] args) { for(int i = 1 ; i

【本文地址】

公司简介

联系我们

递推与递归 （区别）

递推与递归（区别）