面试题中很多都涉及到递归与非递归，比如二分法，冒泡，归并，快排，二叉树前中后遍历等等，建议能直接给出非递归形式，如果面试官想要看到递归形式也能熟练的写出来。
典型的面试题比如说：汉诺塔问题，斐波那契数列等
递归是什么？和循环的区别
答：
递归从字面意思理解是自己调用自己，实际上递归是将问题逐渐分解减小，但是和原问题有着相同解法的问题，并且存在一个问题的出口。
循环就是重复执行同一段代码
打一个比方吧，从前有座山，山里有座庙，庙里有个老和尚和小和尚，老和尚对小和尚说，从前有座山，山里有座庙，庙里有个老和尚和小和尚，老和尚对小和尚说，从前有座山，山里有座庙，庙里有个老和尚和小和尚，老和尚对小和尚说...... 这就是递归，循环就是?从前有座山，山里有座庙，庙里有个老和尚和小和尚。从前有座山，山里有座庙，庙里有个老和尚和小和尚。从前有座山，山里有座庙，庙里有个老和尚和小和尚。从前有座山，山里有座庙，庙里有个老和尚和小和尚。从前有座山，山里有座庙，庙里有个老和尚和小和尚。
循环和递归存在相似性但是存在本质的不同，比如都是重复操作，但是循环是一次正向的过程，递归却需要回溯。
理论上所有的递归都可以变成非递归形式，比如使用栈和循环。但是循环却不能改成递归
尾递归优化：
一些语言在编译或者解释的时候能够自动对尾递归形式进行优化，但是python并不能，所以在python中将递归改成尾递归形式仍然不能改变递归的效率差和爆栈的问题。
针对尾递归优化的语言可以通过尾递归防止栈溢出。尾递归事实上和循环是等价的，没有循环语句的编程语言只能通过尾递归实现循环。
递归效率低的原因：
递归的简单理解：
递归就是自己调用自己，
递归的总结：
- 找到递归出口(终止递归的条件)
- 找出递归表达式(规律)
下面这个就是用递归的方式计算阶乘
首先是递归的出口 n = 1
递归表达式 fact(n) = n * fact(n-1)
===> fact(5)
===> 5 * fact(4)
===> 5 * (4 * fact(3))
===> 5 * (4 * (3 * fact(2)))
===> 5 * (4 * (3 * (2 * fact(1))))
===> 5 * (4 * (3 * (2 * 1)))
===> 5 * (4 * (3 * 2))
===> 5 * (4 * 6)
===> 5 * 24
===> 120递归的缺点：
递归的缺点有两个，首先是时间效率低，需要一个展开和回溯的过程，改成循环的方式就可以避免展开的过程，其次是用栈的问题，python的递归深度最大是1000，win10系统是2MB大小，（使用ulimit -a命令查看大小限制），受限于这两种限制，使用递归就容易出现爆栈的问题。
递归改非递归：
使用栈来模拟递归展开和回溯的过程，可以避免爆栈的问题
在支持尾递归优化的语言中可以将递归改成尾递归的形式
https://www.cnblogs.com/bakari/p/5349383.html