小艾的自留地

Stay foolish, Stay hungry

算法学习笔记——递归

递归

每个递归函数都要有两部分:

  1. 基线条件:递归的结束条件,从而避免形成无限循环
  2. 递归条件:函数调用自己

下面结合一个实际的例子来理解:

1
2
3
4
5
6
7
8
9
10
function fib($n)
{
if ($n <= 2) {
// 基线条件
return $n;
}

// 递归条件
return fib($n-1) + fib($n - 2);
}

如何写好一个递归,要多去思考上面的两个条件应该怎么写。

调用栈

栈是一种简单的数据结构,在使用递归时,用到了调用栈。

用于存储多个函数的变量的栈,被称为调用栈。

每当调用一个函数,计算机会将函数调用所涉及的所有变量的值存储到内存中,如果此时,再次调用了另一个函数,那么计算机也会为这个函数调用分配一块内存。

计算机使用一个栈来表示这些内存块,其中第二个内存块位于第一个内存块上面。如果函数调用返回,此时,栈顶的内存块就会被弹出。

下面用一张图来解释调用栈的过程:

使用栈虽然很方便,但是也要付出代价:存储调用栈的详尽信息需要占用大量的内存。因为每个函数调用都需要占用一定的内存,如果栈很高,就意味着计算机存储了大量函数调用的信息。

在这种情况下,就不建议继续使用递归了,有两种选择:

  1. 使用循环
  2. 使用尾递归

例如 Leetcode 的第70题,既可以用递归解决,也可以使用循环(动态规划)解决,但是前者在达到一定深度之后,执行时间就会变得很长。

评论