【算法】-再谈递归

递归recursive问题作为算法的常见问题，今天来聊一聊。

好多人把递归和迭代傻傻分不清楚，其实，当你理解了其中一个，另一个就很好区分开了。

递归就好比是：一个先进后出的栈，每一次递归调用函数本身，就入栈；每一次递归结束，就出栈。直到递归结束。

举一个递归的简单例子。求阶乘n！

我们都知道，求3的阶乘就是3*2*1，求6的阶乘就是6*5*4*3*2*1……求n的阶乘n！就是n*（n-1）！

可以得到公式

用java实现一下。

public class Main {

public static void main(String args[]) {

System.out.println(jiecheng(5));

}

public static int jiecheng(int n){

if (n == 0) //终止条件

return 1;

else //递归部分

return n * jiecheng(n - 1);

}

}

调试运行，结果为120

除了求阶乘，递归还有很多常见的用途：

比如说，

（1）求二叉树深度（小米面试题）

面到这个问题，当时对递归理解的很浅，回过头来看，这个问题用递归就可以解决。

思路：比较左右子树的深度，二叉树的深度就是左右子树中深度大的那个+1；当左右子树为空时，返回0

首先定义二叉树节点

算法如下

运行结果为2