每周学点大数据 | No.9递归——以阶乘为例

No.9期

递归——以阶乘为例

Mr. 王:我们介绍一个在计算机算法设计和程序设计中都非常常见的概念——递归。

小可:什么是递归呢?

Mr. 王:从程序设计的角度来说,递归就是一个函数,在它的定义中调用了它本身。从算法的角度来说,递归就是一个算法对于一个输入的求解需要对这个算法在更小输入上求解的情况。

小可:这个说法听起来有点复杂啊。

Mr. 王:我们举个例子来说明吧。你一定听说过有一个数学概念叫作阶乘。

小可:我知道,阶乘就是把一个正整数一直乘以它的值减1,直到乘数为1,比如5!=5×4×3×2×1。推广到n的情况就是n!=n×(n−1)×(n−2)×…×3×2×1(特殊的,0!=1)。

Mr. 王:在计算机中求解一个数的阶乘,就可以利用递归。因为阶乘具有一个很有意思的特征,就是:n!=n×(n−1)!。假如我们把阶乘定义为f(n)的话(也就是f(n)=n!),就有f(n)=n×f(n−1)。

小可:哦,从阶乘的定义来看,就是我们想知道f(n),就要知道f(n−1)是多少,推广下去,想知道f(n−1)就要知道f(n−2),一直到f(1)。

Mr. 王:从递归的定义来看,求阶乘这个算法是不是正好符合求对于一个输入n的解,需要求取这个算法在一个更小的输入n−1上的解,而对于n−1的解需要知道去求取n−2的解。

小可:嗯,从这个角度来看,这种求递归的算法确实是一个递归算法。

Mr. 王:如果要设计一个程序,我们也可以书写一个求递归的函数的伪代码:

int f(int n)
{
  if (n==1 || n==0)
    {
      return 1;
    }
   else
return f(n-1);
}

小可:原来函数还可以这样定义啊。

Mr. 王:是的,C/C++语言是非常典型的支持递归的语言。一些早期的语言不支持递归,不过现在很多程序设计语言都支持递归算法的设计。虽然所有的递归算法都可以设计成非递归的版本,比如阶乘,我们可以用一个循环来实现:

int f(int n)
{
  if (n==1 || n==0)
    {
      return 1;
    }
  else
  {
     for (int i=1;i <= n;i++)
     {
        ans *=1;
     }
     return ans;
  }
}

但是递归往往可以更加直观地表达算法的思路,这是非常有利于算法实现和程序设计的。不过有一点需要注意,设计不好的递归算法是非常容易出现无限循环的,在设计递归算法时,一定要设计递归的终点。比如在阶乘中,我们必须指定递归最终会达到的结果f(1)=1 ;否则程序就会一直执行下去,直到内存溢出。

小可:嗯,我懂什么是递归了,但是这和栈有什么关系呢?在递归算法中也没有发现栈的存在啊?

Mr. 王:递归算法和栈的联系非常紧密,虽然在递归程序中我们并没有直接定义出一个栈,但程序运行的内部却会帮我们生成一个栈,这对于递归算法的运行是必要的。现在我们就以阶乘为例来剖析递归算法是如何运行的。

比如我们要求5的阶乘,也就是f(5)。这时程序内的一个栈空间会开始工作,这个空间叫作函数调用栈。程序会将f(5)压栈:

Call stack :[top= f(5)]

求解f(5)时,程序发现需要知道f(4),就把f(4)压栈:

Call stack :[top= f(4)][f(5)]

求解f(4)时,程序发现需要知道f(3),就把f(3)压栈:

Call stack :[top= f(3)][f(4)][f(5)]

依此类推,最后栈中会形成这样一种情况:

Call stack :[top= f(1)][f(2)][f(3)][f(4)][f(5)]

此时,程序发现f(1)的值我们知道了,f(1)=1。所以我们得到了f(1)的解,f(1)这个函数返回1,已经解决的问题或者说已经返回的函数就会弹出调用栈:

Call stack :[top=f(2)][f(3)][f(4)][f(5)]

然后,程序发现f(1)我们知道了,f(2)也就知道了,f(2)=2×f(1)。f(2)返回了值2,f(2)得到解决之后再将f(2)移出栈:

Call stack :[top=f(3)][f(4)][f(5)]

依此类推,程序发现f(2)我们知道了,f(3)也就知道了,f(3)=3×f(2)。f(3)返回了值6,相应地,f(3)得到解决之后再将f(3)移出栈:

Call stack :[top=f(4)][f(5)]

不断地执行下去,就能够得出f(5)的值为120,此时栈空,程序结束。

不难看出,在运行递归程序时,栈一直在工作。因为我们调用函数的嵌套关系恰好满足先到的问题后得到结果、先调用的函数最后返回这样的关系,所以语言的设计者们就利用这一点,用栈结构来表示函数的调用关系。

小可:原来是这样,虽然看不见,但栈一直存在于我们设计的递归和函数调用程序之中。

Mr. 王:是的,栈这种看似简单的数据结构,其实应用是非常广泛的。

这里再谈谈以递归实现算法的缺点。递归程序虽然能够非常有效地表达程序的思路,使得程序的书写变得非常简洁,易于理解,但它的运行速度和执行同样工作的非递归版本相比往往是比较慢的,如果对程序的执行效率有要求,则可以将递归版本重写为非递归的。另外,递归程序在实际的执行过程中执行了多少层递归是不容易预测的。我们知道,前面提到的调用栈也是在计算机的内存空间中,如果递归的层次非常深,就会导致调用栈占用的内存空间被占满,无法继续下一层递归的运行,这就是很多人说的栈溢出或者说“爆栈”,栈溢出会导致程序运行崩溃,所以递归也并不是十全十美的。还是一定要对程序的运行环境进行评估,选择设计递归或者非递归版本的程序。

内容来源:灯塔大数据

原文发布于微信公众号 - 灯塔大数据(DTbigdata)

原文发表时间:2016-10-14

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏蜉蝣禅修之道

Leetcode之Longest Valid Parentheses

1442
来自专栏机器学习算法与Python学习

Python中的实用小技巧

关键字全网搜索最新排名 【机器学习算法】:排名第一 【机器学习】:排名第二 【Python】:排名第三 【算法】:排名第四 话说python是一个大杂会,既可以...

3375
来自专栏小詹同学

Leetcode打卡 | No.012 整数转罗马数字

欢迎和小詹一起定期刷leetcode,每周一和周五更新一题,每一题都吃透,欢迎一题多解,寻找最优解!这个记录帖哪怕只有一个读者,小詹也会坚持刷下去的!

1191
来自专栏C语言及其他语言

[VIP算法训练]大数阶乘的源码分享

问题 1604: [蓝桥杯][算法训练VIP]阶乘 时间限制: 1Sec 内存限制: 128MB 提交: 15 解决: 5 题目描述 一个整数n的阶乘可以写成n...

4237
来自专栏C/C++基础

基数排序简介及其并行化

  基数排序号称线性时间排序算法中性能最好,速度最快的排序算法。本文将简要概括其算法思想,串行代码及其并行化。

1301
来自专栏aoho求索

由散列表到BitMap的概念与应用(一)

散列表是种数据结构,它可以提供快速的插入操作和查找操作。第一次接触散列表时,它的优点多得让人难以置信。不论散列表中有多少数据,插入和删除只需要接近常量的时间即O...

1012
来自专栏编程理解

动态规划(一):爬楼梯

时,处于原地,因为步长为 1 ~ 2 阶,不能有前进之后再后退的情况,所以只能有当前一种方式,所以

1262
来自专栏WD学习记录

牛客网 合唱团

有 n 个学生站成一排,每个学生有一个能力值,牛牛想从这 n 个学生中按照顺序选取 k 名学生,要求相邻两个学生的位置编号的差不超过 d,使得这 k 个学生的能...

1612
来自专栏C/C++基础

统计无符号整数二进制中1的个数(Hamming weight)

之所以来记录这个问题的解法,是因为在在线编程中经常遇到,比如编程之美和京东的校招笔试以及很多其他公司都累此不疲的出这个考题。看似简单的问题,背后却隐藏着很多精妙...

1452
来自专栏ATYUN订阅号

PyTorch 4.0版本迁移指南

欢迎阅读PyTorch 0.4.0的迁移指南。在此版本中,我们引入了许多振奋人心的新功能和重要的bug修复,旨在为用户提供更好,更清晰的接口。在这个指南中,我们...

1592

扫码关注云+社区

领取腾讯云代金券