函数递归指的是在函数内部调用自身的过程。 具体而言,递归函数通过将一个问题分解为更小的、类似的子问题来解决问题。
递归函数的定义通常包括以下几个要素:
优点:
缺点:
#include<stdio.h>
int main()
{
printf("Hello World!\n");
main(); // main函数中再次调用main函数
return 0;
}
运行结果:
调试运行:
从运行结果来看,程序最终会崩溃。经过调试会显示一个Stack overflo这就是栈溢出,也就是递归的缺点之一。
题目需求:输入一个整数m,按照顺序打印整数的每一位。
例如: 输入:1234 输出:1 2 3 4 输入:520 输出:5 2 0
题目分析 这种输入输出数字的题,我们一定要想到取模和取余的方法,并且要有限制条件,每次函数递归后,都会越来越接近这个值。所以先函数递推1234%10=4, 123%10=3, 12%10=2, 1%10=1,给定限制条件n>9,直到n=1,打印出1,最后函数回归打印出1234。
代码实现
#include<stdio.h>
void Print(int n)
{
if (n > 9) // 限定条件
{
Print(n / 10); // 取模
}
printf("%d ", n % 10); // 取余
}
int main()
{
int n = 0;
scanf("%d", &n);
Print(n);
return 0;
}
画图推演
一个正整数的阶乘(factorial)是所有小于及等于该数的正整数的积,并且0的阶乘为1。⾃然数n的阶乘写作n!。
题目:计算n的阶乘(不考虑溢出),n的阶乘就是1~n的数字累积相乘。
题目分析 我们知道n的阶乘的公式: n! = n ∗ (n − 1)!
举例:
5! = 5*4*3*2*1
4! = 4*3*2*1
所以:5! = 5*4!
当 n==0 的时候,n的阶乘是1,其余n的阶乘都是可以通过公式计算。 n的阶乘的递归公式如下:
我们就可以写出函数Fact求n的阶乘,假设Fact(n)就是求n的阶乘,那么Fact(n-1)就是求n-1的阶乘。
代码实现
#include<stdio.h>
int Fact(int n)
{
if (n == 0)
{
return 1;
}
else
{
return n * Fact(n - 1);
}
}
int main()
{
int n = 0;
scanf("%d", &n);
int ret = Fact(n);
printf("%d\n", ret);
return 0;
}
运行结果如下(这里不考虑n太大的情况,n太大存在溢出):
画图推演
题目:编写一个函数实现n的k次方,使用递归实现。
题目分析
以k>0和k=0为限制条件,每一次递推就乘以n,并且k都减一次1,直到不满足限定条件,然后回归。
代码实现
#include<stdio.h>
int Power(int n, int k)
{
if (k == 1)
return n;
else
return n * Power(n, k - 1);
}
int main()
{
int ret = Power(2, 3);
printf("%d\n", ret);
return 0;
}
运行结果
画图推演
题目:
写一个递归函数DigitSum(n),输入一个非负整数,返回组成它的数字之和 例如,调用DigitSum(1729),则应该返回1+7+2+9,它的和是19 输入:1729,输出:19
题目分析
代码实现
#include<stdio.h>
int DigitSum(int n)
{
if (n < 10)
{
return n;
}
return n % 10 + DigitSum(n / 10);
}
int main()
{
int n = 0;
scanf("%d", &n);
int ret = DigitSum(n);
printf("%d\n", ret);
return 0;
}
运行结果
画图推演
斐波那契数:斐波那契数列的第1项是1,第2项也是1。从第3项开始,每一项都等于前两项之和。
题目: 计算斐波那契数递归实现求第n个斐波那契数 例如: 输入:5 输出:5 输入:10, 输出:55 输入:2, 输出:1
题目分析: 斐波那系数是前两项加起来等于后一项:1,1,2,3,5,8,13…,所以我们可以以n<=2为限制条件,当n=1或2时,返回1,然后到n=3项时就是n=1项和n=2项之和,然后依次往后推,即Fib(n)=Fib(n-1)和Fib(n-2)之和。
代码实现
#include<stdio.h>
int Fib(int n)
{
if (n <= 2)
return 1;
else
return Fib(n - 1) + Fib(n - 2);
}
int main()
{
int n = 0;
scanf("%d", &n);
int ret = Fib(n);
printf("%d", ret);
return 0;
}
运行结果
画图推演
由图可以看出,当n越大,在递归的过程中会有重复计算,而且递归层次越深,冗余计算就会越多,效率越低。
题目分析: 也可以参考上面递归实现的思路,我们可以用三个变量相互替换来解决,n1为第一项,n2为第二项,c为第三项,运用while()循环,每一次循环n就减1,直到n=2,最后输出c。
代码实现
#include<stdio.h>
int Fib(int n)
{
int a = 1;
int b = 1;
int c = 1;
while (n >= 3)
{
c = a + b;
a = b;
b = c;
n--;
}
return c;
}
int main()
{
int n = 0;
scanf("%d", &n);
int ret = Fib(n);
printf("%d\n", ret);
return 0;
}
运行结果
改进之后发现求斐波那契数用非递归的方式效率明显高于递归的方式,原因:
用迭代的方式去实现这个代码,效率就要高出很多了。