对递归的理解【笔录】
数据结构和算法的学习，最难掌握的有两个，一个是动态规划，另一个则是递归。
实际工程中递归的应用非常广泛，也是开发者经常被考察的重点。
- 1.理解“递归”
有这样一个场景，假设你在排队，前面排了很多人，但不知道自己排的是第几（每个人都不知道自己是第几名，除了第一个知道自己是第一名）。当你想知道你排第几的时候怎么做？当然你可以从第一个开始数（遍历一遍），还有一种方案就是偷懒的做法，你问你前面的人是第几名，你前面的人再问他前面的人......直到问到第一个人为止，然后再从前往后告知（每个人的名次都是前面的加1），到你自己你就知道自己是第几名。这不就是“递归”的思想吗？
上面的例子中，从后往前问排第几体现在“递”这个字，即一步一步往前递推；而回来告知结果体现在“归”。用递推公式表示为：
f(n) = f(n-1) + 1;其中 f(1) = 1。
用代码写出来为：
int f(int n)
{
if(n == 1)
return 1;
else
return f(n-1) + 1;
}- 2.递归的三要素
（1）问题可分解为子问题
（2）子问题的解决思路完全一致
（3）存在终止条件
从这三个条件与上面排队的例子可以找到对应的关系。
- 3.怎么写递归代码
关键在于找到递推公式和终止条件
- 4.递归难理解在哪？
难在考虑递归过程的时候总会去想递归一层一层的调用，想着想着就乱了，其实这是计算机的思维方式，因为计算机的优势就是能存储每次递归的状态，即堆栈，而人并不能记忆那么多东西。所以，考虑递归的时候只需要通过递推公式和终止条件去推敲，不需要考虑每层的关系。
- 5.递归注意的事项
（1）防止递归过深----有堆栈溢出的风险
（2）防止重复计算----消耗资源
- 6.递归程序怎么调试
（1）打印日志
（2）添加条件和断点