从头学C（41）递归

C语言中函数递归调用，是指函数直接或间接的调用自身。

第四章 函数与程序结构 >> 4.10 递归

1. 将 int 型数以字符串形式打印

数字的生成是反序的，即先生成低位数字，后生成高位数字。但打印过程是反序的，先打印高位数字。

解决办法有两种：

1. 将生成的各位数字依次存储到一个数组中，再以相反的顺序依次打印（可参考 从头学C（29）do-while循环 的 itoa 函数）；
2. 使用递归函数，调用它自身先打印高位的数字（见以下参考代码）。

#include <stdio.h>

/* printd: print n in decimal */
void printd(int n)
{
        if (n < 0)
        {   
                putchar('-');
                n = -n; 
        }   
        if (n / 10) 
                printd(n / 10);
        putchar(n % 10 + '0');
}

int main()
{
        printd(123456);
        printf("\n");
        printd(-123456);
        printf("\n");
}

每次调用 printd 函数时，都会得到一个不同的参数。第一次调用 printd(123456) 把 参数 12345 传给第二次调用，紧接着参数 1234 传给第三次调用……，最后一次调用参数 1 传给 printd() 函数，然后打印 1，返回到倒数第二次调用，传给它的参数是 12，因此打印 2，依次返回……函数结束。

2. 快速排序算法

快速排序算法由  C.A.R. Hoare于1962年发明，也是利用了递归的方法。

给定一个数组，从中选择一个元素，以该元素为界将其他元素划分成两个子集，一个子集中所有元素都小于该元素，另一个子集中所有元素都大于或等于该元素。对这样的两个子集递归执行，当某个子集中的元素个数小于2时，这个子集就不再需要递归执行了。

实现起来的代码是：

#include <stdio.h>

/* swap: interchange v[i]and v[j]*/
void swap(int v[], int i, int j)
{
        int temp;

        temp = v[i];
        v[i]= v[j];
        v[j]= temp;
}

/* qsort: sort v[left]...v[right]into increasing order */
void qsort(int v[], int left, int right)
{
        int i, last;

        if (left >= right) /* do nothing if array contains */
                return;    /* fewer than two elements */
        swap(v, left, (left + right)/2); /* move partition elem*/
        last = left;                     /* to v[0] */
        for (i = left + 1; i <= right; i++) /* partition */
                if (v[i]< v[left])
                        swap(v, ++last, i); 
        swap(v, left, last);    /* restore partitioin elem*/
        qsort(v, left, last-1);
        qsort(v, last+1, right);
}

int main()
{
        int i;
        int a[10] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1,};

        printf("before:\t");
        for (i = 0; i < 10; i++)
                printf("%d ", a[i]);
        printf("\n");

        qsort(a, 0, 9);

        printf("after:\t");
        for (i = 0; i < 10; i++)
                printf("%d ", a[i]);
        printf("\n");

        return 0;
}

3. 关于递归的其他说明

虽然递归的代码看上去很紧凑，但是递归的执行速度并不快，也并不节省存储器的开销，因为递归调用过程中，必须在某个地方维护一个存储处理值的栈。