C语言中函数递归调用,是指函数直接或间接的调用自身。
第四章 函数与程序结构 >> 4.10 递归
1. 将 int 型数以字符串形式打印
数字的生成是反序的,即先生成低位数字,后生成高位数字。但打印过程是反序的,先打印高位数字。
解决办法有两种:
- 将生成的各位数字依次存储到一个数组中,再以相反的顺序依次打印(可参考 从头学C(29)do-while循环 的 itoa 函数);
- 使用递归函数,调用它自身先打印高位的数字(见以下参考代码)。
#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. 关于递归的其他说明
虽然递归的代码看上去很紧凑,但是递归的执行速度并不快,也并不节省存储器的开销,因为递归调用过程中,必须在某个地方维护一个存储处理值的栈。