递归算法：通过重复的单一解题过程调用自己来解决问题的一种算法。
通过上一篇的第一篇：认识计算机程序和算法 我们可以知道，各种算法都是一步一步演变过来的。而递归算法也是比较接近我们的思想的，这一次我们来讲一下比较容易理解和入门的递归算法吧。

1. 递归简介

递归算法可以分为递和归，递的意思是顺着次序一个接一个地，归的意思就是返回的意思。
由此我们可以得知去回之间问题迎刃而解。
首先我们看看递归的数学表达式：

自然数n的阶乘写作n!。1808年，基斯顿·卡曼引进这个表示法。
5！= 5 * 4 * 3 * 2 * 1 = 120

上面的算法看不懂，那我们来看一下图吧：
可以看到左边的是栈的形式，右边是树的形式（后期剪枝算法就是从二叉树重复计算的分支减去）。

上面的图是求5的阶乘算法图解，从图中我们可以看到左边的是递，右边的是归。
我们求5的阶乘等于5 * 4！，这里未知的就是4的阶乘，
同样的道理4的阶乘等于4 * 3！，到这里我们又不知道3的阶乘是多少，
于是又出现3的阶乘等于3 * 2！，2的阶乘我们如果不知道就往下走，
2的阶乘等于 2 * 1！，这里我们知道1的阶乘就是1，
这个时候我们就要一个一个的返回了。

一来一去之间将问题分解步步为营，一一攻克之。

2. 递归算法框架模板

1. 必须要有明确的终止返回值（比如我们都知道1的阶乘为1）
2. 可以构造重复逻辑调用自己，不断缩小至终止返回值（比如以此求得n-1的阶乘值）

可以看到上面的条件必须满足第一条，不然就永远得不到结果。

2.1 二叉树遍历

树的遍历常见的有：
前序遍历：根、左、右
中序遍历：左、根、右
后序遍历：左、右、根
可以看到以根为中序，前序就是根在前面，中序就是根在中间，后序是根在最后。

下面是二叉树的什么遍历？

public void traverse(TreeNode root, List<Integer> result) {if (root == null) {return;}traverse(root.left, result);result.add(root.val);traverse(root.right, result);}

大家可以把方法traverse看成是一个整体，
参数代表其作用，比如看成整个左子树等。
如果是作为List返回，就在方法里面new一个，
可以把分支看成是一个list，最后合并即可。
注意一定要有一个空判断进行返回，因为子节点下面都是null。
大部分树的解题都可以用递归哟~

2.2 爬楼梯、跳台阶

// 这里我们将结果存入一个表里面。
static int[] arr = new int[100];
public int climbStairs(int n) {if(n==1){return 1;}if(n==2){return 2;}// 先去查表，如果有些值已经计算过了直接剪枝了！if(arr[n]>0){return arr[n];}arr[n] = climbStairs(n-1) + climbStairs(n-2);return arr[n];
}

3. 递归演示代码

这里的代码都是以阶乘的算法来介绍的。
Java代码演示：

public class Recursive {public static void main(String[] args) {int result = recursive(5);System.out.println("5的阶乘为：" + result);createTreeTest();}private static int recursive(int num) {// 必须要有一个返回if (num == 1) {return 1;}// 逐步分解return num * recursive(num - 1);}
}

Python代码演示：

def rec(num):if num == 1:return 1return num * rec(num - 1)print(rec(5))

C++代码演示：
C++是C语言的超集，所以很多语法很相似

#include <iostream>
using namespace std;int rec(int num) {if (num == 1){return 1;}return num * rec(num - 1);
}int main(int argc, char** argv) {cout << "5!= " << rec(5);return 0;
}

Typescript代码演示：

function rec(num) {if (num == 1) {return 1;}return num * rec(num - 1);
}
console.log(rec(10));

shell脚本演示：
注意这里的return的范围是： 0~255 之间的整数，其中只有 0 表示成功
所有这里会有问题，后期在研究为啥吧。

#!/bin/bashecho "请输入求阶乘的数："
read numfunction rec() {if [ $1 -eq 1 ];thenresult=1elselet tmp=$1-1rec $tmplet "result=$1 * $?"fireturn $result
}rec $num
echo "结果为：$?"

Go语言演示：

package mainfunc main() {print(rec(5))
}func rec(num int) int {if num == 1 {return 1}return num * rec(num-1)
}

4. 递归算法经典案例

这里的案例只是提及名称和题目，后期会一一讲解。

1. 阶乘
2. 汉诺塔
3. 杨辉三角
4. 斐波那契数列（兔子繁殖）

LeetCode关于递归的题目：
https://leetcode.cn/problemset/all/?page=1&topicSlugs=recursion

通过上面的学习可以解决：
144. 二叉树的前序遍历
94. 二叉树的中序遍历
145. 二叉树的后序遍历
226. 翻转二叉树
70. 爬楼梯
剑指 Offer 10- II. 青蛙跳台阶问题
…