递归与递推区别

oyangningtao

一、递归

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

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

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

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

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

递归的应用场合：

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

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

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

递归设计的要素：

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

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

编写递归算法时，首先要对问题的以下三个方面进行分析：

决定问题规模的参数。      

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

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

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

解决问题的通式。      

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

二、递推

递推：递推算法是一种用若干步可重复运算来描述复杂问题的方法。

递推是序列计算中的一种常用算法。通常是通过计算机前面的一些项来得出序列中的指定象的值。

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

三、递归与递推区别

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

从程序上看，递归表现为自己调用自己，递推则没有这样的形式。

递归是从问题的最终目标出发，逐渐将复杂问题化为简单问题，最终求得问题是逆向的。递推是从简单问题出发，一步步的向前发展，最终求得问题。是正向的。

递归中，问题的n要求是计算之前就知道的，而递推可以在计算中确定，不要求计算前就知道n。

一般来说，递推的效率高于递归（当然是递推可以计算的情况下程序调用自身的编程技巧称为递归。

递推：从初值出发反复进行某一运算得到所需结果。-----从已知到未知，从小到达（比如每年长高9cm，20年180，30后270）
递归：从所需结果出发不断回溯前一运算直到回到初值再递推得到所需结果----从未知到已知，从大到小，再从小到大(你想进bat，那么编程就的牛逼，就得卸载玩者农药，努力学习）。递归(Recursion)是从归纳法(Induction)衍生出来的。一个运算（操作），可以通过不断调用本身的运算形式，
往往需要通过前一次的结果来得到当前运算的结果，因而，程序运行时，总是先一次次地「回溯」前一次的结果（回溯过程中这些结果是未知的，直到回溯到初值令回溯终止，再层层递推回来得到当前要求的值）。

举例，斐波那契的不同实现

递推实现：

int fib(int n){

    int fn   = 1;

    int fn_1 = 0;

    for(int i=0; i<n; i++) {

       int t = fn

       fn    = fn + fn_1;

       fn_1  = t;

    }

    return fn;

}

递归实现：

int fib(n){

    return n < 2 ? 1 : fib(n-1)+f(n-2);

}