算法学习笔记——递归
递归
每个递归函数都要有两部分:
- 基线条件:递归的结束条件,从而避免形成无限循环
- 递归条件:函数调用自己
下面结合一个实际的例子来理解:
1 | function fib($n) |
如何写好一个递归,要多去思考上面的两个条件应该怎么写。
调用栈
栈是一种简单的数据结构,在使用递归时,用到了调用栈。
用于存储多个函数的变量的栈,被称为调用栈。
每当调用一个函数,计算机会将函数调用所涉及的所有变量的值存储到内存中,如果此时,再次调用了另一个函数,那么计算机也会为这个函数调用分配一块内存。
计算机使用一个栈来表示这些内存块,其中第二个内存块位于第一个内存块上面。如果函数调用返回,此时,栈顶的内存块就会被弹出。
下面用一张图来解释调用栈的过程:
使用栈虽然很方便,但是也要付出代价:存储调用栈的详尽信息需要占用大量的内存。因为每个函数调用都需要占用一定的内存,如果栈很高,就意味着计算机存储了大量函数调用的信息。
在这种情况下,就不建议继续使用递归了,有两种选择:
- 使用循环
- 使用尾递归
例如 Leetcode 的第70题,既可以用递归解决,也可以使用循环(动态规划)解决,但是前者在达到一定深度之后,执行时间就会变得很长。