1、递归

定义

递归算法（recursion algorithm）在计算机科学中指一种通过重复将问题分解为子问题而解决问题的方法。

步骤

（1）建立函数，确定函数的输入
首先要明确函数的功能，确定传递的参数。

// 计算n的阶乘（假设n不为0）
int f(int n) {
    // 先不管内部实现逻辑
}

（2）明确递归的结束条件
递归最重要的是在函数内部明确递归的结束条件，否则会一直调用自己形成死循环。

// 计算n的阶乘（假设n不为0）
int f(int n) {
    if (n <= 2) {
        return n;
    }
}

（3）通过数学关系式来写递归关系

// 计算n的阶乘（假设n不为0）
int f(int n) {
    if (n <= 2) {
        return n;
    }
    // 加入f(n)的等价操作逻辑
    return n * f(n - 1);
}

实例一：斐波那契数列

斐波那契数列的是这样一个数列：1、1、2、3、5、8、13、21、34、….，即第一项 f(1) = 1、第二项 f(2) = 1、…..、第 n 项目为 f(n)=f(n-1)+f(n-2)，求第 n 项的值是多少。
第一步：建立函数，因为返回值为整数，故取int；确定输入，即n的值

//斐波那契数列
int f(int n){
    //建立函数
}

第二步:明确递归结束的条件，当n=1或者n=2时，f(1)=f(2)=1，故递归结束的条件可为n<=2。

//斐波那契数列
int f(int n){
    if(n<=2){
       return 1;
    }
}

第三步：写出等价的关系式：f(n)=f(n-1)+f(n-2)

//斐波那契数列
int f(int n){
    if(n<=2){
       return 1;
    }
    return f(n-1)+f(n-2);
}

实例二：小青蛙跳台阶

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个n级的台阶总共有多少种跳法。
第一步：确定函数功能，球多少跳法，返回int量，输入台阶的数量n。

//跳台阶
int f(int n){

}

第二步：确定结束条件，当n=1时，f(1)=1，故将1作为结束条件。

//跳台阶
int f(int n){
   if(n==1){
      return 1;
   }
}

第三步：找函数的等价关系
1.假设台阶只有一级，那么显然只有一种跳法。
2.要是有两级台阶，那么就有两种跳法：一种是一次跳一级台阶，一种是一次跳两级台阶。
3.要是有三级台阶，青蛙的第一步就有两种跳法：当青蛙第一步跳了一级台阶，那么就只剩下了两级台阶，将问题转化成为两级台阶的跳法，当青蛙第一步跳了两级台阶，那么就只剩下了一级台阶，就将问题转化为了一级台阶的跳法。
4.n阶台阶与三阶台阶的分析是一样的。

我们把跳n级台阶时的跳法看成是n的函数，记为f(n)。当n=1时，f(1)=1；当n=2时，f(2)=2；当n=3时，f(3)=f(2)+f(1)；当n=4时，f(4)=f(3)+f(2)......当n=n的时候，f(n)=f(n-2)+f(n-1)，显然这是一个斐波那契数列。

//跳台阶
int f(int n){
   if(n==1){
      return 1;
   }
   return f(n-1)+f(n-2);
}

因为只设置n=1的条件，不能满足n=2的情况，所以需要将返回条件完善：

//跳台阶
int f(int n){
   if(n==0){
      return 0;
   }
   if(n==1){
      return 1;
   }
   if(n==2){
      return 2;
   }
   return f(n-1)+f(n-2);
}

实例三：反转单链表

反转单链表是一个常见的算法。例如链表为1->2->3->4。反转后为 4->3->2->1。
首先链表节点的定义：

class Node {
    int date;
    Node next; // 存储下一个节点
}

第一步：确定函数的返回值，为反转后链表的头结点，故返回Node，输入为原链表的头结点。

//反转单链表
Node *reverseList(Node *head) {

}

第二步：确定函数的结束条件，遍历到最后节点为空时则结束。

//反转单链表
Node *reverseList(Node *head) {
     if(head==NULL || head->next==NULL){
         return head
      }
}

第三步：找关系式，先遍历到最后的节点，再让最后节点的.next指向前一个节点，最后到头节点时，另其next为空。

//反转单链表
Node *reverseList(Node *head) {
     if(head==NULL || head->next==NULL){
         return head
      }
      Node *newList = reverseList(head->next);
      //令现有节点的next指向前一个节点
      Node *t1 = =head->next;
      t1->text = head;
      head->next=null;
      return newList;
}

优化的递归-避免重复

在递归中，有时会将关系式计算多次，例如f(n)=f(n-1)+f(n-2)，在每次计算f(n-2)有可能已经计算过了，故可以通过一个全局的数组来存储已经计算过的算式：

//设定一个arr数组，初始化为-1
vector<int> arr(n,-1);
int f(int n) {
    if (n <= 1) {
        return n;
    }
    // 先判断有没计算过
    if (arr[n] != -1) {
        // 计算过，直接返回
        return arr[n];
    } else {
        // 没有计算过，递归计算,并且把结果保存到 arr数组里
        arr[n] = f(n - 1) + f(n - 2);
        reutrn arr[n];
    }
}