递归函数(recursive function),说到底就是自己调用自己:
void recurse() { recurse(); //递归 }
该recurse函数的函数体中调用了自己,因此如果在main函数中调用该函数,该程序将会一直循环下去(有点类似于Loop),直到栈溢出(StackOverflow)。学过数据结构的同学都知道栈(Stack)是一种后进先出(LIFO)的数据结构,对栈的操作都是在栈顶上进行。当程序在运行时,如果调用一个函数,则将该函数压栈(Push),调用完一个函数则出栈(Pop)。而对于上面定义的recurse函数,在递归过程中,不断的压栈(因为该函数并没有执行完毕,因为还没有执行到函数的最后一个大括号
} )。因为内存是有限的,因此程序最终会崩溃(Crash)。
为何不测试下程序的极限栈大小呢?
#include <stdio.h> void recurse(int count) { printf("%d \n",count); return recurse(count + 1); //递归 } int main() { recurse(1); }
输出:
为了防止栈溢出,通常我们的递归函数都有if-else语句来判断何时终止递归。
下面来实现一个简单的阶乘函数factorial():
#include <stdio.h> int factorial(int n) { if(n == 0) return 1; //终止递归 else return n*factorial(n-1); //递归 } int main() { printf("%d",factorial(3)); //在这里n最大取16,否则会溢出(变成负数了)。主要取决于数据类型的范围。有符号整形最大值大约是21亿。就算是最长的整数类型 long long (64位) ,n最大只能取到20。 }
主要是利用了递归表达式 factorial(n) = n*factorial(n-1)
递归函数的另外一种用途是针对链表的遍历(traverse)。
下面再利用递归函数来输出一个对称数: 1 2 3 4 5 6 7 8 9 9 8 7 6 5 4 3 2 1
#include <stdio.h> void symmetric(int n) { printf("%d ",n); if( n < 9) symmetric(n + 1); printf("%d ",n); } int main() { symmetric(1); }
: