目录

一、递归定义

百度百科

其他

二、循环与递归

三、几个经典题

斐波那契数

题目

基本思路

递归解法

动态规划解法 

 汉诺塔

题目 

基本思路

一、递归定义

百度百科

递归，就是在运行的过程中调用自己。

函数嵌套调用过程示例

构成递归需具备的条件：

1. 子问题须与原始问题为同样的事，且更为简单；

2. 不能无限制地调用本身，须有个出口，化简为非递归状况处理。

其他

递归是一种解决问题的有效方法，在递归过程中，函数将自身作为子例程调用。

你可能想知道如何实现调用自身的函数。诀窍在于，每当递归函数调用自身时，它都会将给定的问题拆解为子问题。递归调用继续进行，直到到子问题无需进一步递归就可以解决的地步。

为了确保递归函数不会导致无限循环，它应具有以下属性：

• 一个简单的基本案例 —— 能够不使用递归来产生答案的终止方案。
• 一组规则，也称作递推关系，可将所有其他情况拆分到基本案例。

二、循环与递归

举个栗子，你用你手中的钥匙打开一扇门，结果去发现前方还有一扇门，紧接着你又用钥匙打开了这扇门，然后你又看到一扇们...但是当你开到某扇门时，发现前方是一堵墙无路可走了，你选择原路返回——这就是递归

但是如果你打开一扇门后，同样发现前方也有一扇们，紧接着你又打开下一扇门...直到打开最后一扇门出去，或者一直没有碰到尽头 （死循环）——这就是循环。

三、几个经典题

斐波那契数

题目

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。

f(n) = f(n-1) + f(n-2)

基本思路

上面那个链接可以用递归求解

这道题在剑指offer中实际是当作递归的反例来说的。（用动态规划来解）

递归的本质是吧一个问题分解成两个或者多个小问题，如果多个小问题存在互相重叠的情况，那么就存在重复计算。

f(n) = f(n-1) + f(n-2)这种拆分使用递归是典型的存在重叠的情况，所以会造成非常多的重复计算。

另外，每一次函数调用爱内存中都需要分配空间，每个进程的栈的容量是有限的，递归层次过多，就会造成栈溢出。

递归是从最大数开始，不断拆解成小的数计算，如果不去考虑递归，我们只需要从小数开始算起，从底层不断往上累加就可以了，其实思路也很简单。

递归解法

/**
 * @param {number} n
 * @return {number}
 */
var fib = function(n) {
    if(n<=1){
        return n
    }
    return fib(n-1)+fib(n-2)
};

动态规划解法 

/**
 * @param {number} n
 * @return {number}
 */
var fib = function(n) {
    if(n<=1){
        return n
    }
    let pre=0,current=1,result=0,i=1
    while(i++<n){
        result=pre+current
        pre=current
        current=result
    }
    return result
};

 汉诺塔

题目 

在经典汉诺塔问题中，有 3 根柱子及 N 个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。一开始，所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。移动圆盘时受到以下限制:
(1) 每次只能移动一个盘子;
(2) 盘子只能从柱子顶端滑出移到下一根柱子;
(3) 盘子只能叠在比它大的盘子上。

请编写程序，用栈将所有盘子从第一根柱子移到最后一根柱子。

你需要原地修改栈。

基本思路

采用递归的思路
三要素如下：
递归结束条件：只剩下最后一个盘子需要移动
递归函数主功能：
1.首先将 n-1 个盘子，从第一个柱子移动到第二个柱子
2.然后将最后一个盘子移动到第三个柱子上
3.最后将第二个柱子上的 n-1 个盘子，移动到第三个柱子上
函数的等价关系式：
f(A,B,C,n) 表示将n个盘子从A移动到C
f(A,B,C,n)=f(A,C,B,n-1)+f(A,B,C,1)+f(B,A,C,n-1)

/**
 * @param {number[]} A
 * @param {number[]} B
 * @param {number[]} C
 * @return {void} Do not return anything, modify C in-place instead.
 */
var hanota = function(A, B, C) {
    let n=A.length
    return move(A,B,C,n)
};
function move(A,B,C,n){
    if(n===0) return;
    move(A,C,B,n-1)
    C.push(A.pop())
    move(B,A,C,n-1)
}