1. 概念
C语言中，函数直接或间接调用函数本身，则该函数称为递归函数。
递归做为一种算法在程序设计语言中广泛应用。一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。
递归的主要思考方式在于：把大事化小
2. 递归的两个必要条件
//例子：
void func()
{
//...
if(...)
func();//调用自身
else
//...
}
在上面的例子中能够看出，它必须满足以下两个条件：
🍥 在每一次调用自己时，必须是（在某种意义上）更接近于解；
🍥 必须有一个终止处理或计算的限制条件，当满足这个限制条件的时候，递归便不再继续。
🍤实例1：
接收一个整型值（无符号），按照顺序打印他的每一位。
例如：
输入123，输出1 2 3
非递归：
#include<stdio.h>
int main()
{
int n=123;
int a = n / 100;//取百位
int b = (n / 10)%10;//取十位
int c = n % 10;//取个位
//依次输出
printf("%d %d %d\n", a, b, c);
return 0;
}
递归：
#include<stdio.h>
void Fun_c(int x)
{
if (x >9)//限制条件
{
Fun_c(x/10);
}
printf("%d ", x%10);
}
int main()
{
int n;
scanf("%d", &n);
Fun_c(n);
return 0;
}
图解：
🍤实例2：
编写函数不允许创建临时变量，求字符串的长度。
int Length(char* s)
{
if (*s == '\0')//限制条件
return 0;
else
return 1 + Length(s + 1);
}
#include<stdio.h>
int main()
{
char* ch = "iloveC";//字符串结束标志:'\0'
int len = Length(ch);
printf("%d", len);
return 0;
}
第一次 s=“iloveC\0”------5+1
第二次 s=“loveC\0”-----4+1
第三次 s=“oveC\0”----3+1
第四次 s=“veC\0”----2+1 ( 回退)
第五次 s=“eC\0”----1+1
第六次 s=“C\0”----1+0
第七次 s=“\0”-----0
3. 递归与迭代
3.1 求n的阶乘
//递归
#include<stdio.h>
int Fac(int n)
{
if (n == 1)//限制条件
return 1;
else
return n * Fac(n - 1);
}
int main()
{
int n;
scanf("%d", &n);
int temp = Fac(n);
printf("%d\n", temp);
return 0;
}
//迭代
int Fac(int n)
{
int temp = 1;
for (int i = 1; i <= n; i++)
{
temp = temp * i;
}
return temp;
}
#include<stdio.h>
int main()
{
int n;
scanf("%d", &n);
printf("%d\n", Fac(n));
return 0;
}
3.2 求第n个斐波那契数
1 1 2 3 5 8 13 21…
从第三位开始，后一项等于前两项之和
//递归
#include<stdio.h>
int Fib(int n)
{
if (n == 1 || n == 2)//限制条件
return 1;
else
return Fib(n - 1) + Fib(n - 2);
}
int main()
{
int n;
scanf("%d", &n);
printf("%d\n", Fib(n));
return 0;
}
//迭代
#include<stdio.h>
int Fib(int n)
{
int a = 1;
int b = 1;
int c;
while (n >= 3)
{
c = a + b;
a = b;
b = c;
n--;
}
return c;
}
int main()
{
int n;
scanf("%d", &n);
printf("%d\n", Fib(n));
return 0;
}
注：
🍥 许多问题是以递归的形式进行解释的，这只是因为它比非递归的形式更为清晰。
🍥 但是这些问题的迭代实现往往比递归实现效率更高，虽然代码的可读性稍微差些。
🍥 当一个问题相当复杂，难以用迭代实现时，此时递归实现的简洁性便可以补偿它所带来的运行时开销。
结束语
递归是函数实现的一个很重要的环节，我们不但要理解，还要掌握，能够熟练使用递归，希望这篇文章能够帮助到你。
