算法系列 基础篇 栈 递归

详解递归算法执行的栈结构，简要介绍尾递归。

栈定义

堆栈（英语：stack）又称为栈或堆叠，是计算机科学中一种特殊的串列形式的抽象数据类型，其特殊之处在于只能允许在链表或数组的一端（称为堆栈顶端指针，英语：top）进行加入数据（英语：push）和输出数据（英语：pop）的运算。另外栈也可以用一维数组或链表的形式来完成。堆栈的另外一个相对的操作方式称为队列。

由于堆栈数据结构只允许在一端进行操作，因而按照后进先出（LIFO, Last In First Out）的原理运作。

维基百科：https://zh.wikipedia.org/wiki/%E5%A0%86%E6%A0%88

递归

简单说，递归就是调用自己，如下代码：

def countdown(i):
	print i 
	countdown( i- 1)

上面的代码打印 i 之后继续调用自己，但这个调用是无限循环的，无法停止。所以递归函数还有一个要素，基线条件，也就是调用边界，什么时候不调用自己，返回。如：

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

这样就设置了一个基线条件，避免无线循环。


调用栈

计算机在内部使用被称为调用栈的栈。

看一段 python 代码

def greet2(name):
    print("how are you, ", name, "?")

def bye():
    print("ok bye!")

def greet(name):
    print("hello, ", name, "!")
    greet2(name)
    print("getting ready to say bye...")
    bye()

greet("maggie")

出于简化考虑，赞不将 print 视为函数。调用 greet("maggie") 函数时，计算机将为函数调用分配一块内存，变量被设置为 maggie 并保存在内存中。两步图示如下：


分配内存


使用内存

每当你调用函数时，计算机都像这样将函数调用涉及的所有变量的值存储到内存中。接下来，你打印hello,maggie!，再调用greet2("maggie")。同样，计算机也为这个函数调用分配一块内存。


计算机使用一个栈来表示这些内存块，其中第二个内存块位于第一个内存块上面。你打印howareyou,maggie?，然后从函数调用返回。此时，栈顶的内存块被弹出。


现在栈顶的内存是函数 greet 的这意味着返回到了函数 greet 。当调用 greet2 时，greet 函数只执行了一部分。

调用另一个函数时，当前函数暂停并处于未完成状态。

该函数所有的变量的值都还在内存中。

调用 greet2 之后，打印 getting ready to say bye...，然后调用 bye()，此时 函数 bye 来到了栈顶：


打印 ok bye! 之后，函数返回。回到 greet，函数已经没有其他事情可做，直接返回。

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

递归调用栈

递归函数也是函数，所以使用的也是调用栈。下面是一段计算阶乘的递归函数：

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

其调用栈：


每个fact调用都有自己的x变量。在一个函数调用中不能访问另一个的x变量。

使用栈虽然很方便，但是也要付出代价：存储详尽的信息可能占用大量的内存。每个函数调用都要占用一定的内存，如果栈很高，就意味着计算机存储了大量函数调用的信息。在这种情况下，你有两种选择。

  • 重新编写代码，转而使用循环。
  • 使用尾递归。这是一个高级递归主题，不在本书的讨论范围内。另外，并非所有的语言都支持尾递归。


尾递归

尾递归，也叫尾调用：

在计算机科学里，尾调用是指一个函数里的最后一个动作是一个函数调用的情形：即这个调用的返回值直接被当前函数返回的情形。这种情形下称该调用位置为尾位置。若这个函数在尾位置调用本身（或是一个尾调用本身的其他函数等等），则称这种情况为尾递归，是递归的一种特殊情形。尾调用不一定是递归调用，但是尾递归特别有用，也比较容易实现。

尾调用的重要性在于它可以不在调用栈上面添加一个新的堆栈帧——而是更新它，如同迭代一般。尾递归因而具有两个特征：

  • 调用自身函数(Self-called)；
  • 计算仅占用常量栈空间(Stack Space)。

而形式上只要是最后一个return语句返回的是一个完整函数，它就是尾递归。

维基百科：https://zh.wikipedia.org/wiki/%E5%B0%BE%E8%B0%83%E7%94%A8

只看定义可能还是比较模糊，来看两段代码

def recsum(x):
  if x == 1:
    return x
  else:
    return x + recsum(x - 1)
普通递归
def tailrecsum(x, running_total=0):
  if x == 0:
    return running_total
  else:
    return tailrecsum(x - 1, running_total + x)
尾递归

两段代码不同的地方在于，尾递归函数传递了返回值，因此在每次 return 时原来的函数已经结束，栈退出，返回的是一个新的栈。两种递归方式的栈空间如下：

recsum(5)
5 + recsum(4)
5 + (4 + recsum(3))
5 + (4 + (3 + recsum(2)))
5 + (4 + (3 + (2 + recsum(1))))
5 + (4 + (3 + (2 + 1)))
5 + (4 + (3 + 3))
5 + (4 + 6)
5 + 10
15
tailrecsum(5, 0) 
tailrecsum(4, 5) 
tailrecsum(3, 9)
tailrecsum(2, 12) 
tailrecsum(1, 14) 
tailrecsum(0, 15) 
15

分别为普通递归和尾递归，使用尾递归不会出现栈溢出的现象。

以上！


算法示例代码：https://github.com/egonschiele/grokking_algorithms

引用内容来自：巴尔加瓦(AdityaBhargava).算法图解(图灵程序设计丛书)(Kindle位置194-196).人民邮电出版社.Kindle版本.