从头学C(41)递归

0

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. 关于递归的其他说明

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

Leave A Reply