算法基础（二）：递归（一）

慕课：程序设计与算法（二）算法基础 郭玮老师课程的学习笔记

递归：函数自己调用自己本身

递归跟普通函数调用都是函数的调用，只是他的一个不同在于，每次函数执行时都会在递归调用的地方暂停并开始下一次函数调用，直到最后一次进行完毕，又开始往回继续执行函数，即堆栈的形式，这样造成了一个理解的复杂点，但是一旦你弄明白递归的过程以及问题求解时递归的使用，你就会发现递归是个非常好用的形式，可以帮助我们求解问题。

例题：n!求n得阶乘

以n!为例，当n=4初始时，4*F(3)->3*F(2)*3->4*3*2*F(1)->4*3*2*1=24，每次函数执行到return n*Factorial(n-1)都会停止并调用下一个函数，即将当前的调用压到堆栈中，直到n=1时返回1，则开始从栈中倒着推出，直到结束

如图，一层一层压栈，直到返回1，则一层一层又往回退

所以，理解这种堆栈的实现对于递归是非常重要的，要记住这种形式！

递归是高级编程中必不可少的算法，其应用和具体问题分析必须要我们掌握熟练！

1、汉诺塔问题

问题一开始是要解决将n个盘子从A移到C，以B做中转，可以分解为，将n-1个盘子移到B，然后将最后一个盘子移到C，再将n-2个盘子移到A，第n-1个盘子移到C。。。

如图，当n==1时直接将之移到目的即可，当n!=1时，需要用目的当中转，将起始地的盘子移到中间地，然后将中间地的盘子以起始地为中转移到目的地去。是一个典型的递归问题。

2、N皇后问题

将n个皇后摆在n*n的棋盘上，注意不能同行同列，且不能斜对角摆放

所以递归的形式就是假定前面所有的皇后已经摆好，摆放当前以及之后的皇后，从0号皇后开始摆放

如果最后j==k则没有break,与之前都没冲突，则可以放置当前的位置

从0开始，每个皇后都尝试n种摆放位置，第0号皇后的位置确定好后，开始第1号皇后，然后是第2号皇后。。。每个皇后摆放时其前面皇后的位置都已经摆放完毕，只要确定当前皇后与之前不会冲突即可摆放。。。

只要不冲突则尝试当前的摆放，即可以尝试所有的情况，因为每次递归调用都会返回，所以可以继续尝试下一种摆放，即时当前k-1个皇后的位置没有可以摆放的位置时也会回溯到第k-2个皇后尝试下一个位置，直到后面所有皇后都可以找到一个不冲突的位置即可结束递归返回最一开始的调用处

3、逆波兰表达式

逆波兰表达式本身就是一个递归定义的问题，直接可以想到使用递归进行解决

运算符前置，越先出现的运算符越后计算，当出现符号的时候则递归生成两边的运算式，当出现数字的时候则递归返回