【算法】算法图解笔记_递归

tomlingtm 发布于2019-07-31 10:12 / 727人阅读

递归是个有意思的概念，正如在前面所说，递归能让算法的可读性大大提高，而且通常要比使用循环结构更能写出准确的算法。这本书形象引入了递归，并没有太深入，所以我进行了一点“添油加醋”。

递归概念

递归其实就是自己调用自己。可以从多种维度对递归分类，我见过的最常见的分类：

直接递归

自己直接调用自己。如：

--haskell
length" :: [a] -> Int
length" [] = 0
length" (_:xs) = 1 + length" xs

上面定义的length"就是通过直接递调用自身完成列表长度的计算。

间接递归

可以认为只要不是直接调用自己的递归都是间接递归，其表现形式较多，如A->（调用）B，B->（调用）A，如奇偶谓词函数：

--haskell
odd" :: Int -> Bool
odd" 0 = False
odd" n = even" (n - 1)

even" :: Int -> Bool
even" 0 = True
even" n = odd" (n - 1)

也可以有A->B，B->C，... Z->A。这里就不举例子了。

书中的例子

有一个盒子，盒子里套着一个或多个盒子，盒子里的盒子又有盒子，依次类推。而钥匙就在某个盒子里，我们怎么找到钥匙呢。

策略一

伪代码如下：[伪代码是对手头问题的简要描述,看着像代码,但其实更接近自然语言。]

def look_for_key(main_box):
  pile = main_box.make_a_pile_to_look_through()
  while pile is not empty:
    box = pile.grab_a_box()
    for item in box:
      if item.is_a_box():
        pile.append(item)
      elif item.is_a_key():
        print "found the key!"

如果学习过树的遍历，是不是发现这就是广度优先遍历啊

策略二

伪代码如下：

def look_for_key(box):
  for item in box:
    if item.is_a_box():
      look_for_key(item)
    elif item.is_a_key():
      print "found the key!"

对应的就是深度优先遍历啊

这两种方法的作用相同,但第二种方法更清晰。递归只是让解决方案更清晰,并没有性能上的优势。实际上,在有些情况下,使用循环的性能更好。Leigh Caldwell在Stack Overflow上说的一句话:“如果使用循环,程序的性能可能更高;如果使用递归,程序可能更容易理解。如何选择要看什么对你来说更重要。”

基线条件和递归条件

每个递归函数都有两部分:基线条件(base case)和递归条件(recursive case)。递归条件指的是函数调用自己,而基线条件则指的是函数不再调用自己,从而避免形成无限循环。递归条件一定是向基线条件靠拢的，否则，只能无限递归下去。如

#python
def countdown(i):
  print i
  if i <= 0:
    return
  else:
    countdown(i-1)

上述函数中i的值收敛于0，即达到基线条件，从而不会无限递归下去。

栈

主要讲了与递归相关的一种数据结构--栈（stack）。栈是一种支持FILO（First In Last Out）的数据结构。
为什么要提这种数据结构呢？

调用栈

这是因为现代计算机对函数的实现用到了调用栈（call stack）的栈。调用函数时，计算机将首先为该函数调用分配一块内存。每当你调用函数时,计算机都将函数调用涉及的所有变量的值存储到内存中。

假设A函数调用B函数，此时计算机为两个函数分配了内存，暂且称之为A函数内存和B函数内存，它们的位置关系如下：
----栈顶----
B函数内存
—————
A函数内存
—————

若B函数执行完，计算机就可以回收B函数内存了，即从栈顶弹出B函数内存，此时只有A函数内存了。
----栈顶----
A函数内存
—————

以上操作符合FILO的定义，调用栈是栈的一种具体应用。

那如果调用栈数量太多，会有什么后果呢？

递归调用栈

#python
def fact(x):
  if x == 1:
    return 1
  else:
    return x * fact(x-1)

对于较小的正整数，这个程序没有问题；而如果x较大，在fact执行的时会发现内存量会飙升，甚至会出现程序无法正常执行下去。这是因为此时递归调用栈的情况类似：
----栈顶----
fact(1)函数内存
———————
...
———————
fact(n-2)函数内存
———————
fact(n-1)函数内存
———————
fact(n)函数内存
———————

fact(n)依赖fact(n-1)，依次类推，导致计算机存储了大量函数调用的信息。这类问题大体有两种解决方式：

重新编写代码,转而使用循环。

使用尾递归。现在已经有很多编译器支持尾递归优化了。

我的公众号地址

GPU云服务器云服务器排序算法图解最大值算法递归 java递归算法树 java 树递归算法

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/43432.html

【算法】算法图解笔记_快速排序

摘要：再谈大表示法快速排序的独特之处在于其速度取决于选择的基准值。在平均情况下快速排序的运行时间为在最糟情况下退化为。快速排序和合并排序的算法速度分别表示为和，是算法所需的固定时间量被称为常量。分而治之分而治之(divide and conquer,D&C)是一种著名的递归式问题解决方法。只能解决一种问题的算法毕竟用处有限,而D&C提供了解决问题的思路,是另一个可供你使用的工具。 D&C...

YanceyOfficial 2019-07-31 10:14 评论0 收藏0
【算法】算法图解笔记_算法简介

摘要：在本书中你将学习比较不同算法的优缺点该使用合并排序算法还是快速排序算法或者该使用数组还是链表。这样的算法包括快速排序一种速度较快的排序算法。在读《算法图解》这本书，这本书有两个优点：手绘风格的图，看着很让人入戏；算法采用Python语言描述，能更好的表达算法思想。关于算法的学习有两点心得：算法思想最重要，理解了思想，算法是很容易写出来的，所以尽量不要把过多精力放在细节上...

tomlingtm 2019-07-31 10:10 评论0 收藏0
【算法】算法图解笔记_选择排序

摘要：选择排序是下一章将介绍的快速排序的基石。需要存储多项数据时有两种基本方式数组和链表。但它们并非都适用于所有的情形因此知道它们的差别很重要。选择排序是一种灵巧的算法但其速度不是很快。选择排序是下一章将介绍的快速排序的基石。内存的工作原理计算机就像是很多抽屉的集合体,每个抽屉都有地址。showImg(https://segmentfault.com/img/bVbpWvv?w=413...

mylxsw 2019-07-31 10:12 评论0 收藏0
【算法】算法图解笔记_广度优先搜索

摘要：解决最短路径问题的算法被称为广度优先搜索。广度优先搜索算法最早由年在如何从迷宫中寻找出路这一问题中提出。广度优先搜索让你能够找出两样东西之间的最短距离。使用广度优先搜索解决问题。你经常需要解决最短路径问题(shorterst-path problem)。解决最短路径问题的算法被称为广度优先搜索。广度优先搜索算法最早由Edward F. Moore 1959年在如何从迷宫中寻找出路这一...

sanyang 2019-07-31 10:18 评论0 收藏0