说递归之前，先说一说循环。

循环

1、应用场景：在一定范围内重复运算

2、条件：需要设置初始值、中止条件。

优点：相对递归效率高

缺点：涉及到树的操作稍复杂

递归

1、应用场景：本质是将一个问题分解为多个问题，且多个问题有重叠部分（二叉树就是典型的递归）

2、自己调自己:在一个函数内部调用函数自身（具体怎么调用，要自己总结数学模型 eg:f(n)=f(n-1)+f(n-2)

4、有可能出现的问题：当递归调用层次太多，就会出现栈溢出（crash了，如下图）

优点：编程简单，特别是涉及到二叉树的先序、中序、后序等遍历时

缺点：相对效率低，因为每次函数调用，都需要在内存栈中分配空间保存参数、返回地址、临时变量等

举一个简单的例子说明一下：

//计算：1+2+3+...+n

//递归的方式

int AddForm1ToN1(int n){

  return n <=0 ?0 : n +AddForm1ToN1(n-1);   

}

//循环的方式

int AddForm1ToN2(int n){

  int sum =0;

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

       sum = sum + i;

    }

  return sum;

}

循环很简单，我就不说了。对于递归来讲，代码很简单，但是想到这种方法不容易。

写一个递归函数思路

最重要的是两点：1、递归的中止条件  2、递归的函数

1、递归的中止条件：上面的中止条件很显然是n＝0，当n＝0递归过程结束还是回归。

2、递归的函数：一般来讲就是对要处理的数据总结数学模型，下面我就一步一步的演示一下总结过程，比如：

设f(n) = n + n-1 +n - 2…+ 3 + 2 + 1                ………………(1)

那f (n-1) =  n-1 + n-2 … + 3 + 2+ 1                  .……………..(2)

由(1)、(2)可以得到 f(n) = n + f(n-1)……也可以推出来f(n-1) = n-1＋f(n-2)

斐波那契数列

fabonacci数列是一个经典的递归调用

当n＝0时，f(n) = 0                                ………………..(3)

当n＝1时，f(n) = 1                                ………………..(4)

当n > 1时，f(n) = f(n-1) + f(n-2)          ………………..(5)

一个fabonacci数列：0，1，1，2，3，5，8，13

有(3)、(4)可以得到递归的中止条件，有(5)数学模型可以得到递归的函数

int fabonacci(intn){

           if (n == 0)       return 0;

           if( n == 1)    return 1;

           return fabonacci(n-1) +fabonacci(n-2)

}

斐波那契数列的优化

开篇的时候有讲递归的一个缺点就是压入和弹出内存栈会耗费大量资源，且调用层级太多还会导致栈溢出的问题。那么我们可以用一种反向的思维来对递归来优化。简而言之就是将中间项保存起来，从下往上计算（数学的方式优化掉递归的方程，只留下回调过程）

long fabonacci(intn){

     int a[2] = {0,1};

     if ( n < 2)  return a[n];

     int n1 = 0;

     int n2 = 1;

     for ( inti = 2 ;i <= n ;i++ ){

inttemp  = n1 + n2;

n1= n2;

n2= temp;

     }

}

001.深入浅出理解［递归］