C语言——函数递归

简介: C语言——函数递归

1.什么是递归

递归是学习C语⾔函数绕不开的⼀个话题,那什么是递归呢?

递归其实是⼀种解决问题的⽅法,在C语⾔中,递归就是函数⾃⼰调⽤⾃⼰。

写⼀个史上最简单的C语⾔递归代码:

#include<stdio.h>

int main() {

   printf("hollow,world");
   main();//在main函数调用main
   return 0;
}

上述就是⼀个简单的递归程序,只不过上⾯的递归只是为了演⽰递归的基本形式,不是为了解决问

题,代码最终也会陷⼊死递归,导致栈溢出(Stack overflow);

递归的思想:

把⼀个⼤型复杂问题层层转化为⼀个与原问题相似,但规模较小的⼦问题来求解;直到⼦问题不能再被拆分,递归就结束了。所以递归的思考⽅式就是把⼤事化小的过程。

递归中的递就是递推的意思,归就是回归的意思,接下来慢慢来体会。

2.递归的限制条件:

递归在书写的时候,有2个必要条件:

  • 递归存在限制条件,当满足这个限制条件的时候,递归便不再继续。
  • 每次递归调⽤之后越来越接近这个限制条件。

在下⾯的例⼦中,我们逐步体会这2个限制条件。

 

3.递归举例

例1:求n的阶乘

———————————————————————————————————————————

#include<stdio.h>

int fact(int x) {
   if (x <= 0) {
       return 1;
   }
   else
   {
       return x * fact(x - 1);
   }

}

int main() {
   int a=0;
   scanf("%d", &a);   //n的阶乘
   int ret = fact(a);        //函数将a的值传过去
   printf("%d", ret);
   return 0;
}

分析

我们知道n的阶乘的公式: n =   n ∗ ( n − 1)!

举例:

5! = 5*4*3*2*1

4! = 4*3*2*1

所以:5! = 5*4

n!—> n*(n-1)!                    (n-1)! —> (n-1)*(n-2)!

......直到n=1 or n=0,将不再分解

再稍微分析⼀下,当 n<=1 的时候,n的阶乘是1,其余n的阶乘都是可以通过上述公式计算。

n的阶乘的递归公式如下:

画图推演

为了理解递归的运行方式,我们画图推演一下吧

例2:顺序打印一个整数的每⼀位

 

void Print(int n)
{
   if (n > 9)
   {
       Print(n / 10);
   }
   printf("%d ", n % 10);
}

int main()
{
   int m = 0;
   scanf("%d", &m);
   Print(m);
   return 0;
}

输出结果 :

画图推演

迭代与递归

迭代法也称辗转法,是一种不断用变量的旧值递推新值的过程,跟迭代法相对应的是直接法(或者称为一次解法),即一次性解决问题。

int Fact(int n)

{

int i = 0;

int ret = 1;

for(i=1; i<=n; i++)

{

ret *= i;

}

return ret;

}

上述代码是能够完成任务,并且效率是⽐递归的⽅式更好的。

事实上,我们看到的许多问题是以递归的形式进行解释的,这只是因为它⽐⾮递归的形式更加清晰, 但是这些问题的迭代实现往往⽐递归实现效率更⾼。

当⼀个问题⾮常复杂,难以使⽤迭代的⽅式实现时,此时递归实现的简洁性便可以补偿它所带来的运 ⾏时开销。

 

注意:

有时候,递归虽好,但是也会引发⼀些问题,所以我们⼀定不要迷恋递归,适可而止就好

———————————————————————————————————————————


相关文章
|
1天前
|
算法 Java C语言
Java中的算法与C语言中的函数
Java中的算法与C语言中的函数
8 2
|
5天前
|
机器学习/深度学习 算法 C语言
详细介绍递归算法在 C 语言中的应用,包括递归的基本概念、特点、实现方法以及实际应用案例
【6月更文挑战第15天】递归算法在C语言中是强大力量的体现,通过函数调用自身解决复杂问题。递归涉及基本概念如自调用、终止条件及栈空间管理。在C中实现递归需定义递归函数,分解问题并设定停止条件。阶乘和斐波那契数列是经典应用示例,展示了递归的优雅与效率。然而,递归可能导致栈溢出,需注意优化。学习递归深化了对“分而治之”策略的理解。**
19 7
|
5天前
|
安全 C语言
【C语言基础】:内存操作函数
【C语言基础】:内存操作函数
|
5天前
|
编译器 C语言 C++
【C语言基础】:字符函数和字符串函数-2
【C语言基础】:字符函数和字符串函数
|
5天前
|
C语言
【C语言基础】:字符函数和字符串函数-1
【C语言基础】:字符函数和字符串函数
TU^
|
5天前
|
编译器 程序员 Serverless
C语言之函数
C语言之函数
TU^
4 0
TU^
|
5天前
|
机器学习/深度学习 C语言
C语言之函数递归
C语言之函数递归
TU^
10 1
|
5天前
|
C语言
C语言——字符串操作函数
C语言——字符串操作函数
6 0
|
6天前
|
机器学习/深度学习 算法 C语言
【C语言基础】:函数递归详解
【C语言基础】:函数递归详解
|
6天前
|
编译器 程序员 C语言
【C语言基础】:函数详解
【C语言基础】:函数详解