本文共 3508 字,大约阅读时间需要 11 分钟。
3.1 递归
假设你在祖母的阁楼中翻箱倒柜,发现了一个上锁的神秘手提箱。
祖母告诉你,钥匙很可以在下面这个盒子里。
这个盒子里有盒子,而盒子里的盒子又有盒子。钥匙就在某个盒子中。为找到钥匙,你将使用什么算法?用什么算法?先想候这个问题,再接着往下看。
下面是一种方法。
(1) 创建一个要查找的盒子堆。
(2)从盒子堆取出一个盒子,在里面找。
(3)如果找到的是盒子,就将其加入盒子堆中,以便以后再查找。
(4)如果找到钥匙,则大功告成!
(5)回到第二步。
下面是另一种方法。
3.2 基线条件和递归条件
(1)检查盒子中的每样东西。
(2)如果是盒子,就回到第一步。
(3)如果是钥匙,就大功告成!
在你看来,哪种方法更容易呢?每一种方法使用的是while循环:只要盒子堆不空,就从中取一个盒子,并在其中仔细查找。
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_bos: pile.append(item) elif item.is_a_key(): print "found the key!"
第二种方法使用递归-----函数调用自己,这种方法的伪代码如下:
def look_for_keb(box): for(item i box): if item.is_a_box(): look_for_key(item) #递归 elif item.is_a_key(): pirnt "found the key!"
这两咱方法的作用相同,但在我看来,第二种方法更清晰。递归只是让解决方案清晰,并没有恒通上的优势。实际上,在有些情况下,使用循环的性能更好。我委喜欢Leigh Cakdwell在Stack Overflow上说的一句话:“如果使用循环,程序的性能可以更高;如果使用递归,程序可以更容易理解。如何选择要看什么对你来说更重要。”
很多算法都使用了递归,因此理解这咱概念很重要。
、3.2 基线条件和递归条件
由于递归函数调用自己,因此编写这样的函数时很容易出错,进而导致无限循环。例如,假设你要编写一个像下面这样倒计时的函数。
3....2...1
为此,你可以用递归的方式编写,如下所示。
def countdown(i):
print i
countdonw(i-1)
如果你运行上述代码,将发现一个问题:这个函数运行起来没完没了!
如果你运行上述代码,将发现一个问题;这个函数运行起来没完没了!
编写递归函数时,必须告诉它何时停止递归。正因为如此,每个递归函数都 有两部分:基线条件(base case)和递归条件(recursive case)。递归条件批的是函数调用自己,而基线条件则指的是函数不再调用自己,从而避免形成无限循环。
我们来给函数countdown添加基线条件。
# coding=utf-8def countdown(i): print i, if i <= 0: #基线条件 return else: #递归条件 countdown(i-1)countdown(3)
现在,这个函数将像预期的那样运行,如下所示。
3.3 栈
本节将介绍一个重要的编程概念----调用栈(call stack)。调用栈不仅对编程来说很重要,使用递归时也必须理解这个概念。
假设你去野外烧烤,并为此创建了一个待办事项清单-------一叠便条。
在本书之前讨论数组和链表时,也有一个待办事项清单。你可将待办事项添加到该清单的任何地方,还可删除任何一个待办事项。一叠便条要简单得多:插入的待办事项放在清单的最前面;读取待办事项时,你只读取最上面的那个,并将其删除。因此这个待办事项清单只在两种操作:压入(插入)和弹出(删除并读取)。
下面来看看如何使用这个待办事项清单。
这种数据结构称为栈。棰是一种简单的数据结构,刚才我们一直在使用它,却没有意识到!
3.3.1 调用栈
计算机在内部使用被称为调用栈的栈。我们来看看计算机是如何使用调用栈的。下面是一个简单的函数。
def greet(name): print "hello, " + name + "!" greet2(name) print "getting ready to say bey..." bye()def greet2(name): print "how are you. " + name + "?"def bye(): print "ok bye!"greet("maggie")
下面详细介绍调用函数时发生的情况。
假设你调用greet("maggie"),计算机将首先为该函数调用分配一块内存。
我们来使用这些内存。变量name被设置为maggie,这需要存储到内存中。
每当你调用函数时,计算机都像这样将函数调用涉及的所有变量的值存储到内存中。接下来,你打印hello,maggie!,再调用greet2(maggie)。同样,计算机也为这个函数调用分配一块内存。
计算机使用一个栈来表示这些内存块,其中第二个内存块位于第一个内存块上面。你打印how are you,maggie>,然后从函数调用返回。此是地,栈顶的内存块被弹出。
现在,栈顶的内存块是函数 greet的,这意味着你返回到了函数greet。当你调用函数greet2时,函数greet只执行了一部分。这是本节的一个重要概念:调用另一个函数时,当前函数暂停并处于未完成状态。该函数的所有变量的值都还在内存中。执行完函数greet2后,你回到函数greet,并从离开的地方开始接着往下执行:首先打印getting ready to say bye...,再调用函数bye。
在栈顶添加了函数bye的内存块。然后,你打印ok bye!,并从这个函数返回。
现在你又回到了函数greet.由于没有别的事情做,你就从函数greet返回。这个栈用于存储多个函数的变量,被称为调用栈。
3.3.2 递归调用栈
递归函数也使用调用栈!来看看递归函数factorial的调用栈。factorial(5)写作5!,其定义如下:5! = 5 * 4 * 3 * 2 *1 。 同理,factorial(3)为3 * 2 * 1。下面是计算阶乘的递归函数。
def fact(x): if x==1: return 1 else: return x * fact(x-1)print fact(3)
下面来详细分析调用fact(3)时调用栈是如何变化的。别忘了,栈顶的方框指出了当前执行到了什么地方。
注意,每个fact调用都有自己的x变量。在一个函数调用中不能访问另一个函数中的x变量。
栈在递归中扮演着重要角色。在本章开头的示例中,有两处寻找钥匙的方法。下面再次列出了第一种方法。
使用这种方法时,你创建一个待查找的盒子堆,因此你始终知道还有哪些盒子需要查找。
但使用递归方法时,没有盒子堆。
既然没有盒子堆,那算法怎么知道还有哪些盒子需要查找呢?下面是一个例子。
此时,调用 栈类似于下面这样。
原来“盒子堆”存储在了栈中!这个栈包含未完成的函数调用,每个函数调用都包含未检查完的盒子。使用栈很方便,因为你无需自己跟踪盒子堆----栈替你这样做了。
使用栈虽然很方便,但是也要付出代价:存储详细的信息可能占用大量的内存。每个函数调用都要占用一定的内存,如果栈很高,就意味着计算机存储了大量函数调用的信息。在这种情况下,你有两种选择。
重新编写代码,转而使用循环。
使用尾递归。这是一个高级递归主题,不在本书的讨论范围内。另外,并非所有的语言都支持尾递归。
3.4 小结
递归指的是调用自己的函数。
每个递归函数都有两个条件:基线条件和递归条件。
栈有两种操作:压入和弹出。
所有函数调用都进入调用栈。
调用栈可能很长。这装饰占用大量的内存。
转载地址:http://xzgmi.baihongyu.com/