Day 09：递回(2)

上一回我们看到，同样的跨年倒数任务，可以用回圈或递回的方式完成。

用回圈通常可以看到某个变数(例如i)记录着重复执行的次数，可是递回的写法往往更简洁，好像我们只是丢给它问题，它就帮我们执行下去。让人不禁好奇简单背後发生了什麽事。

想要更清楚递回的运作，我们可以先了解堆叠(stack)这种资料结构。

堆叠是一种线性资料结构，也就是一种连续、有序的资料集合。它的名字就点出它跟现实生活中物体的堆叠一样，譬如一个厨房里有人负责洗盘子，他会将洗好的盘子不断往上叠，另一边厨师要拿盘子的时候，也会从最上层拿最後放上去的盘子，不可能从底下抽出第一个盘子。

同理，在堆叠中，加入(push)或移除(pop)元素也只会发生在同一端(通常称为堆叠的顶端，跟堆盘子的意象一样)，而因为後加入的元素会先被移除，堆叠也可以称作是一种後进先出(LIFO, Last In First Out)的资料结构。

讲到堆叠是因为每当我们执行函式，堆叠这种结构就会被用来储存函式的资讯。而当进行递回时，每次呼叫函式的资讯就被一层层加到堆叠顶上，最後被呼叫的函式会先执行完、从堆叠移除，最後才回到第一个呼叫的函式。

以上一回跨年倒数的例子来说，我们可以想像成当呼叫countDown(n)，电脑里有一个记忆体空间会被用来储存函式里的区域变数n。而当执行过程中又呼叫了一次countDown(n-1)，就会开始执行这个函式，并把它的资讯加到堆叠上面。

当然，执行堆叠也不是只用来储存区域变数，更重要的还有储存返回位址、传递变数等功能。例如当函式A中呼叫了子函式B时，主函式A会在堆叠上纪录返回位址，这样函式B执行完毕後，就可以把返回位址从堆叠上移除，并回到该位址继续执行主函式A。

执行堆叠的细节通常藏在我们看不到的後台，不过我们在撰写递回函式时，可以省去一些工作或步骤，就是因为每次呼叫函式都有执行堆叠来记录其中的值。

递回跟回圈除了写法还有什麽差别？递回效能比较高吗？

递回和回圈主要的差别在於，对於不能预先知道执行次数的问题，可以使用递回的解法。回圈则通常在撰写时就要先设定程序要重复几遍。

在效能方面，递回其实没有特别优势，往往效能还比回圈差。而且基於上面提到执行堆叠的特性，可以想像当有过多层的递回(或不小心无限递回)的时候，会出现占用太多记忆体的问题。

那递回和回圈该怎麽选？

Grokking Algorithms书中提到，Leigh Caldwell在stack overflow网站(对，查资料常用的程序问答网站的名字就是堆叠太多记忆体爆掉的意思)上提供了蛮有趣的回答，不妨可以作为参考，他说回圈可以增进程序的效能，而递回可以增进工程师的效能，应该视情况做出取舍。

也就是说，如果某个地方使用递回，能让程序变得对工程师来说更简单、直觉、好懂，那就是适合使用递回的情况。