计算机系统学习3:函数递归

一.函数递归（Function recursion）

递归算法具有很好的可读性和可维护性。所谓递归，是指利用分而治之的思想，将一个复杂的问题，不断简化成简单的易于处理的同类型的问题。

一个典型的递归包括以下2个部分：

Recursive case:将一个复杂问题不断简化为一个同类型的易于处理的简单问题
Base case:不断简化，一直简化到一个可以直接处理的问题

递归的步骤类似于数学证明中的数学归纳法，因此可以用数学归纳法证明递归的正确性。

我们以计算n的阶乘的例子来看看函数递归的基本情况：

示例：计算n!

int factorial(int n){
    if(n == 1) {
        return 1;//Base case
    }else{
        return n * factorial(n-1);//Recursive case
    }
}

从这个例子中，我们可以看到递归通过不断的调用自己（Recursive case），实现将一个复杂的问题，简化成一个计算量小的简单问题，直到可以直接得到结果的那步(Base case)。

那么，递归在内存中是如何执行的呢？

一个进程在内存中的布局如图所示：

在这个图中，阶乘函数编译后会被放在代码段，而其中的每个栈帧则代表被调用中的一个函数，具体的函数调用的过程，在计算机系统学习2:程序的机器级表示之函数调用这篇文章中进行了详细的介绍。递归在调用函数的过程中，始终调用的是同一函数，因此，代码段中，只需要放一段递归函数就可以了。

接下来，我们看看，递归的输入和返回的执行过程。以factorial(4)为例：

首先在计算factorial(4)的时候，形成一个函数栈帧，返回的是4*factorial(3),但是factorial(3)不知道是多少，因此，需要再形成新的函数栈帧，计算factorial(3)，即返回3*factorial(2)，接着以同样的方式计算factorial(2)，如此循环，一直到Base case:factorial(1),直接返回1，然后每个函数栈帧逐个出栈，最终得到factorial(4)的值。

如图所示：

递归虽然好用，但是，由于内存容量有限，因此，如果递归太深，或者递归的量很大的话，就会造成内存溢出。

那么如何解决这个问题呢？

首先我们分析一下，上面提出的这个阶乘的计算方式，我们会发现，n*factorial(4)在内存中执行的时候，每个函数栈帧都要记录下当前的n的值，同时还要记录其返回值，然后才能计算出当前栈帧的结果，记录不同的n值的时候，我们就需要不同的函数栈帧，因此，如果我们可以想办法设计一个方法，不再保存n的的值，而只保留输入参数和返回值，从而实现函数栈帧的复用。

代码如下：

int factorial(int n，int result){
    if(n == 1) {
        return result;//Base case
    }else{
        return factorial(int n, n*result);//Recursive case
    }
}

其计算过程如下：

我们注意到，在这种方法中，Recursive case中，不再是n*factorial(4)了，而是直接调用函数factorial(...)本身。

在内存执行的过程为：

由于不用再记录表达式n*factorial(4)中的不同的n，而是直接调用函数factorial(...)自身，这种方法可以在递归中，完全复用同一个栈帧，而不用开辟新的函数栈帧。

这种递归方法就是尾递归。所谓的尾递归，就是指在一个递归中，递归调用是函数体中最后执行的语句，并且它的返回值不属于这个表达式一部分时，那么这个递归就可以称为尾递归。尾递归函数的最后一个动作是调用函数本身，是递归的一种特殊情形。

尾递归具有2个主要的特征：

调用自身函数（Self-called）;
计算仅占用常量栈空间（Stack Space）.

现代的编译器会发现尾递归的这个特点，生成优化的代码，复用栈帧。第一个算法中因为有个n * factorial(n-1) , 虽然也是递归，但是递归的结果处于一个表达式中，还要做计算，所以就没法复用栈帧了，只能一层一层的调用下去。

二.函数递归的示例

1. Fibonacci numbers

#Fibonacci numbers
def fib(x):
    """assumes x an int >= 0 returns Fibonacci of x"""
    #assert type(x) == int and x >= 0 
    if x == 0 or x == 1:
        return 1
    else:
        return fib(x-1) + fib(x-2)

2. Towers of Hanoi

#Towers of Hanoi
def printMove(fr, to):
    print('move from ' + str(fr) + 'to' + str(to))

def Towers(n, fr, to, spare):
    if n==1:
        printMove(fr, to)

    else:
        Towers(n-1, fr, spare, to)
        Towers(1, fr, to, spare)
        Towers(n-1, spare, to, fr)

/*      
*Towers(1,'f', 't', 's')
*Towers(2,'f', 't', 's')
*Towers(5,'f', 't', 's')
*/