实战PHP数据结构基础之递归

目录:

之前说到,递归是一种将大问题分解为小问题的解决方案。一般来说,递归被称为函数自身的调用。这么说可能听起来很奇怪,事实上在递归中,函数确实必须调用自己。

  一、递归是“神马”?

例如在数学中,我们都知道“阶乘”的概念。例如5的阶乘就是5*4*3*2*1

  二、写一个求阶乘的函数

  • 5!= 5 * 4!
  • 4!= 4 * 3!
  • 3!= 3 * 2!
  • 2!= 2 * 1!
  • 1!= 1 * 0!
  • 0!= 1

  三、课时22课后习题及答案

我们可以总结出求n的阶乘的规律,即 n! = n * !

 

这就体现了递归。你可以从中发现,我们把求5的阶乘一步一步转化成了另外一个个的小问题。

*********************

  • 每一个递归调用都必须基于一个小的子问题。例如5的阶乘就是5乘4的阶乘。
  • 递归必须有一个Base case。例如阶乘的Base case就是0,当条件是0的时候,就停止递归。
  • 递归中避免循环调用,否则最后计算机会显示栈溢出的错误。

一、递归是“神马”?

*********************

function factorial: int{ if  { return 1; } return $n * factorial;}

递归这个概念,是算法的范畴。那么递归算法在日常编程中有哪些例子呢?

看上面的代码,我们可以看到对于阶乘问题的解决方案我们有一个基础的条件就是当n为0的时候,我们返回1。如果不符合这个条件,我们返回nfactorial ,这符合递归特性的第一条和第三条。我们避免了循环调用,因为我们把每一次的递归调用都分解成了大问题的一个小的子问题。上面的算法思想可以表达成:

金沙官网线上 1

金沙官网线上 2clipboard.png

            图片一 汉诺塔游戏

上面的递归代码我们同样可以使用迭代的方法实现

金沙官网线上 3

function factorial: int{ $result = 1; for ($i = $n; $i > 0; $i--) { $result*= $n; } return $result;}

            图片二 树结构的定义

如果一个问题可以很容易的使用迭代来解决,我们为何要使用递归?

金沙官网线上 4

递归是用来处理更加复杂的问题的,不是所有的问题都可以简单的使用迭代来解决的。递归使用函数调用来管理调用栈,所以相比于迭代递归会使用更多和时间以及内存。此外,在迭代中,我们每一步都会有一个结果,但是在递归中我们必须等到base case执行结束才会有任何结果。看上面的例子,我们发现在递归算法中我们没有任何变量或者声明来保存结果,而在迭代算法中,我们每一次都用$result来保存了返回结果。

            图片三 谢尔宾斯基三角形

金沙官网线上,在数学中,斐波那契数列是一个特殊的整数数列,数列中的每一个数的是由另外两个数求和产生的。规则如下:

金沙官网线上 5

金沙官网线上 6clipboard.png

            图片四 女神自拍

function fibonacci{ if  { return 0; } if  { return 1; } return fibonacci + fibonacci;}

 

另外一个使用递归算法的常见问题是求两个数的最大公因数。

递归,从原理上来说就是函数调用自身的一个行为。你没听错,在函数内部,你可以调用所有可见的函数,当然包括自己。

金沙官网线上 7clipboard.png

举个例子:

function gcd(int $a, int $b){ if  { return $a; } return gcd($b, $a % $b);}
>>> def recursion():
    return recursion()

>>> recursion()
Traceback (most recent call last):
  File "<pyshell#3>", line 1, in <module>
    recursion()
  File "<pyshell#2>", line 2, in recursion
    return recursion()
  File "<pyshell#2>", line 2, in recursion
    return recursion()
  File "<pyshell#2>", line 2, in recursion
    return recursion()
  [Previous line repeated 990 more times]
RecursionError: maximum recursion depth exceeded
  • 线性递归

这个例子尝试了初学者玩递归最容易出现的错误。从理论上来讲,这个程序会一直执行下去,直到消耗完所有的内存资源。不过Python出于善意的保护,对递归的深度默认限制为100层,所以代码才会停下来。不过如果使用写网络爬虫的工具,可能会爬的很深,那你也可以自己设置递归的深度限制。方法如下:

在每一次递归调用中,函数只调用自己一次,这就叫做线性递归。

>>> import sys
>>> sys.setrecursionlimit(1000000)#将递归限制设置为100万层
  • 二分递归

可用ctrl + c 让程序停止。

在二分递归中,每一次递归调用函数调用自己两次。求解斐波那契数列的算法就是二分递归,除此之外还有二分查找、分治算法、归并排序等也使用了二分递归。

 

  • 尾递归

****************************

当一个递归返回的时候没有等待的操作的时候就称为尾递归。斐波那契算法中,返回值需要乘以前一个递归的返回值,因此他不是尾递归,而求解最大公因式的算法是尾递归。尾递归是线性递归的一种形式。

本文由金沙官网线上发布于编程,转载请注明出处:实战PHP数据结构基础之递归

您可能还会对下面的文章感兴趣: