欢迎访问郭晓龙个人博客
你的位置:首页  > Python  > 如何理解“递归”?

如何理解“递归”?

本文内容摘自-极客学院 数据结构与算法之美 王争

如何理解递归?

递归是一种应用非常广泛的算法(或者编程技巧)。 递归本身一点都不“高冷”,咱们生活中就有很多用到递归的例子。

周末带着女朋友去电影院看电影,女朋友问你,咱们现在坐在第几排啊?电影院里面太黑了,看不清,没法数,现在你怎么办?

别忘了你是程序员,这个可难不倒你,递归就开始排上用场了。于是你就问前面一排的人他是第几排,你想只要在他的数字上加一,就知道自己在哪一排了。但是,前面的人也看不清啊,所以他也问他前面的人。就这样一排一排往前问,直到问到第一排的人,说我在第一排,然后再这样一排一排再把数字传回来。直到你前面的人告诉你他在哪一排,于是你就知道答案了。

这就是一个非常标准的递归求解问题的分解过程,去的过程叫“递”,回来的过程叫“归”。基本上,所有的递归问题都可以用递推公式来表示。刚刚这个生活中的例子,我们用递推公式将它表示出来就是这样的:

f(n)=f(n-1)+1 其中,f(1)=1

f(n) 表示你想知道自己在哪一排,f(n-1) 表示前面一排所在的排数,f(1)=1 表示第一排的人知道自己在第一排。有了这个递推公式,我们就可以很轻松地将它改为递归代码,如下:

int f(int n) {
  if (n == 1) return 1;
  return f(n-1) + 1;
}

递归需要满足的三个条件

刚刚这个例子是非常典型的递归,那究竟什么样的问题可以用递归来解决呢?我总结了三个条件,只要同时满足以下三个条件,就可以用递归来解决。

1. 一个问题的解可以分解为几个子问题的解

何为子问题?子问题就是数据规模更小的问题。比如,前面讲的电影院的例子,你要知道,“自己在哪一排”的问题,可以分解为“前一排的人在哪一排”这样一个子问题。

2. 这个问题与分解之后的子问题,除了数据规模不同,求解思路完全一样

比如电影院那个例子,你求解“自己在哪一排”的思路,和前面一排人求解“自己在哪一排”的思路,是一模一样的。

3. 存在递归终止条件

把问题分解为子问题,把子问题再分解为子子问题,一层一层分解下去,不能存在无限循环,这就需要有终止条件。

还是电影院的例子,第一排的人不需要再继续询问任何人,就知道自己在哪一排,也就是 f(1)=1,这就是递归的终止条件

文章标题: 如何理解“递归”?
文章地址: http://www.guoxiaolong.cn/article-2-47
文章标签: python入门教程
Top