编程语言中,我们习惯将函数(方法)调用自身的过程称为递归,调用自身的函数称为递归函数,用递归方式解决问题的算法称为递归算法。
函数(方法)调用自身的实现方式有 2 种,分别是:
1) 直接调用自身,例如:
[C++] 纯文本查看 复制代码 int funciton(/*...*/) {
//......
//调用自身
function(/*...*/);
//......
}
2) 间接调用自身,例如:
[C++] 纯文本查看 复制代码 int funciton1(/*...*/) {
//......
//调用另一个函数
function2(/*...*/);
//......
}
int function2(/*...*/) {
//......
//调用function1()函数
funciton1(/*...*/);
//......
}
程序中,function1() 函数内部调用了 function2() 函数,而 function2() 函数内部又调用了 function1() 函数。也就是说,function1() 函数间接调用了自身。
设计递归函数时,我们必须为它设置一个结束递归的“出口”,否则函数会一直调用自身(死循环),直至运行崩溃。接下来我们以“用递归方式求 n! ”为例,给大家展示一个正确的递归函数。
n! 指的是求 1*2*3*...*n 的值,如下 C 语言程序中的 factorial() 就是实现求 n! 的递归函数:
[C++] 纯文本查看 复制代码 #include <stdio.h>
int factorial(int n) {
//递归的出口
if (n == 1 || n == 0) {
return 1;
}
//函数调用自身
return n * factorial(n - 1);
}
int main()
{
int n;
scanf("%d", &n);
printf("%d! = %d", n,factorial(n));
return 0;
}
|