递归函数

小时候我与小伙伴没有故事可讲时会讲一个故事：从前有座山，山里有座庙，庙里住着一个老和尚和一个小和尚，老和尚给小老和尚讲了个故事...，从前有座山，山里有座庙，... 老和尚给小老和尚讲了个故事... 这种故事套故事的手法，在编程语言中称为递归，在C中表现为函数调用其自身。如果没有终止递归调用的条件，函数会持续递归下去，直到栈空间溢出。

认识递归

递归可以用迭代实现，但递归有时可能很简单的表达语义。阶乘运算是理解递归一个很好的例子：它可以用递归很好的表达语义；也很容易翻译成迭代版本。

#include <stdio.h>

int factorial(int n)
{
    // 终止条件
    if (n == 0 || n == 1)
    {
        return 1;
    }

    // 递归语义表达清晰：n!=n*(n-1)!
    return n * factorial(n - 1);
}

int main()
{
    printf("factorial(5): %d\n", factorial(5));
    return 0;
}

这里我们用图例描述一下factorial(3)的过程，其中红色表示调用过程及实参，绿色部分表示返回过程与值。

斐波那契数列

使用递归实现的斐波那契数列是一个双重递归，该数列的一个特点是，从第3项开始，当前项等于前两项之和。如：

0   1   1   2   3   5   8 ...

下面的程序输出了斐波那契数列的前10项。

#include <stdio.h>

int fibonacci(int i)
{
    if (i == 0)
        return 0;

    if (i == 1)
        return 1;

    return fibonacci(i - 1) + fibonacci(i - 2);
}

int main()
{
    printf("fibonacci(10): ");

    for (int i = 0; i < 10; i++)
    {
        printf("%d ", fibonacci2(i));
    }
}

下面是迭代方式实现的版本，语义上不如递归表达直接。

int fibonacci(int i)
{
    if (i == 0)
        return 0;

    if (i == 1)
        return 1;

    int i0 = 0;
    int i1 = 1;
    int i2 = 0;

    for (int k = 2; k <= i; k++)
    {
        i2 = i0 + i1;   // 当前项 = 前前项 + 前一项
        i0 = i1;        // 前前项 移动到 前一项
        i1 = i2;        // 前一项 现在是 当前项
    }

    return i2;
}

正如开头的故事那样，如果没有结束条件，故事将永远下去。在程序中，这显然不是我们所希望的。无限的函数嵌套调用，类似于程序限入死循环模式，最终因为嵌套太深，程序堆栈出错。因此，递归需要一个明确的结束条件，在斐波那契数列中，就是前两项不会再调用自身，而是返回一个明确值。

处理语句前后影响

在编写递归程序时，必须小心的处理将要执行的语句顺序，对于层次性结构，有广度优先与深度优先两种方式。广度优先就是：先处理本层数据，再递归处理下一层。

#include <stdio.h>

void print_info(int count, const char *info)
{
    if (count > 0)
    {
        printf("#%d %s\n", count, info);
        print_info(count - 1, info);
    }

    printf("#%d\n", count);
}

int main()
{
    print_info(3, "glimix.com");
    return 0;
}

而深度优先则是抵达底层并处理该层数据，然后回退处理上层。

#include <stdio.h>

void print_info(int count, const char *info)
{
    if (count > 0)
    {
        print_info(count - 1, info);
        printf("#%d %s\n", count, info);
    }

    printf("#%d\n", count);
}

int main()
{
    print_info(3, "cs.glimix.com");
    return 0;
}

递归与函数参数

函数被递归调用时，每一次的递归调用，都有属于本次函数堆栈的变量拷贝。

#include <stdio.h>

void n_tabs(int n)
{
    for (int i = 1; i < n; i++)
        printf("\t");
}

void up_down(int n)
{
    n_tabs(n);
    printf("Layer %d: n location %p\n", n, &n);

    if (n < 4)
        up_down(n + 1);

    n_tabs(n);
    printf("LAYER %d: n location %p\n", n, &n);
}

int main()
{
    up_down(1);
    return 0;
}

例子：通过递归求数组元素的最大值

#include <stdio.h>

int maximum(int *head, int *tail)
{
    if (head == tail)
    {
        return *head;
    }
    else
    {
        if (*head > *tail)
            return maximum(head, tail - 1);
        else
            return maximum(head + 1, tail);
    }
}

int main()
{
    int a[] = {  2, 4, 9, 6, 3, 5, 8 };
    int b[] = { 12, 4, 9, 6, 3, 5, 8 };
    int c[] = {  2, 4, 9, 6, 3, 5, 18};

    printf("%d\n", maximum(a, a + 6));
    printf("%d\n", maximum(b, b + 6));
    printf("%d\n", maximum(c, c + 6));

    return 0;
}

初始时，函数maximum()中的head指向数组的第一个元素，tail则指向最后一个，程序利用两两比较的方式if (head > tail)来选择下次的比较元素，最终选出最大值。当然，这不是求最大值的好方法，只是用于教学性质的递归演示。