c语言回顾-函数递归(上)

简介: c语言回顾-函数递归(上)

1.递归的介绍

1.1什么是递归

递归是指在一个函数的定义中调用自身的过程。简单来说,递归是一种通过重复调用自身来解决问题的方法。

递归包括两个关键要素:基本情况和递归情况。基本情况是指当问题达到某个特定条件时,不再需要递归调用,可以直接返回结果。递归情况是指在解决问题的过程中,通过调用自身来缩小问题规模,直到达到基本情况。

在c语言中,递归就是函数自己调用自己。

写一个史上最简单的C语言递归代码:


#include <stdio.h>
int main()
{
 printf("hehe\n");
 main();//main函数中⼜调⽤了main函数
 return 0;
}

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

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

1.2递归的思想

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

递归中的递就是递推的意思,归就是回归的意思。

1.3递归的限制条件

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

• 递归存在限制条件,当满足这个限制条件的时候,递归便不再继续。

• 每次递归调用之后越来越接近这个限制条件。

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

2.递归举例

2.1 举例1:求n的阶乘

一个正整数的阶乘(factorial)是所有小于及等于该数的正整数的积,并且0的阶乘为1。

自然数n的阶乘写作n!。

题目:计算n的阶乘(不考虑溢出),n的阶乘就是1~n的数字累积相乘。

2.1.1 分析和代码实现

我们知道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)就是求n的阶乘,那么Fact(n-1)就是求n-1的阶 乘,函数如下:


int Fact(int n)
{
if(n==0)
return 1;
else
return n*Fact(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太大存在溢出):

2.1.2 画图推演

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

输入一个整数m,打印这个按照顺序打印整数的每一位。

⽐如:

输⼊:1234 输出:1 2 3 4

输⼊:520 输出:5 2 0

2.2.1 分析和代码实现

这个题目,放在我们面前,首先想到的是,怎么得到这个数的每一位呢?

如果n是一位数,n的每一位就是n自己

n是超过1位数的话,就得拆分每一位

1234%10就能得到4,然后1234/10得到123,这就相当于去掉了4

然后继续对123%10,就得到了3,再除10去掉3,以此类推

不断的 %10 和 /10 操作,直到1234的每一位都得到;

但是这里有个问题就是得到的数字顺序是倒着的

但是我们有了灵感,我们发现其实一个数字的最低位是最容易得到的,通过%10就能得到

那我们假设想写一个函数Print来打印n的每一位,如下表示:

Print(n)

如果n是1234,那表示为

Print(1234) // 打印 1234 的每一位

其中1234中的4可以通过%10得到,那么

Print(1234)就可以拆分为两步:

1. Print(1234/10) // 打印 123 的每一位

2. printf(1234%10) // 打印 4

完成上述2步,那就完成了1234每一位的打印

那么Print(123)又可以拆分为Print(123/10) + printf(123%10)

以此类推下去,就有

Print(1234)

==>Print(123) + printf(4)

==>Print(12) + printf(3)

==>Print(1) + printf(2)

==>printf(1)

直到被打印的数字变成一位数的时候,就不需要再拆分,递归结束。

代码实现:

#include <stdio.h>
void Print(int n) {
  if (n > 9) {
    Print(n / 10);
    printf("%d ", n % 10);
  }
  else
    printf("%d ", n % 10);
}
int main()
{
  int n = 0;
  scanf("%d", &n);
  Print(n);
  return 0;
}

简化版本:

我们发现if 和else 语句中都有printf("%d ",n%10);故可以简化。

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

在这个解题的过程中,我们就是使用了大事化小的思路

把Print(1234) 打印1234每一位,拆解为首先Print(123)打印123的每一位,再打印得到的4

把Print(123) 打印123每一位,拆解为首先Print(12)打印12的每一位,再打印得到的3

直到Print打印的是一位数,直接打印就行。

2.2.2 画图推演

以1234每一位的打印来推演一下


c语言回顾-函数递归(下):https://developer.aliyun.com/article/1624396

目录
相关文章
|
1天前
|
存储 缓存 算法
【C语言】内存管理函数详细讲解
在C语言编程中,内存管理是至关重要的。动态内存分配函数允许程序在运行时请求和释放内存,这对于处理不确定大小的数据结构至关重要。以下是C语言内存管理函数的详细讲解,包括每个函数的功能、标准格式、示例代码、代码解释及其输出。
22 6
|
18天前
|
C语言
c语言调用的函数的声明
被调用的函数的声明: 一个函数调用另一个函数需具备的条件: 首先被调用的函数必须是已经存在的函数,即头文件中存在或已经定义过; 如果使用库函数,一般应该在本文件开头用#include命令将调用有关库函数时在所需要用到的信息“包含”到本文件中。.h文件是头文件所用的后缀。 如果使用用户自己定义的函数,而且该函数与使用它的函数在同一个文件中,一般还应该在主调函数中对被调用的函数做声明。 如果被调用的函数定义出现在主调函数之前可以不必声明。 如果已在所有函数定义之前,在函数的外部已做了函数声明,则在各个主调函数中不必多所调用的函数在做声明
31 6
|
2月前
|
存储 缓存 C语言
【c语言】简单的算术操作符、输入输出函数
本文介绍了C语言中的算术操作符、赋值操作符、单目操作符以及输入输出函数 `printf` 和 `scanf` 的基本用法。算术操作符包括加、减、乘、除和求余,其中除法和求余运算有特殊规则。赋值操作符用于给变量赋值,并支持复合赋值。单目操作符包括自增自减、正负号和强制类型转换。输入输出函数 `printf` 和 `scanf` 用于格式化输入和输出,支持多种占位符和格式控制。通过示例代码详细解释了这些操作符和函数的使用方法。
43 10
|
1月前
|
存储 算法 程序员
C语言:库函数
C语言的库函数是预定义的函数,用于执行常见的编程任务,如输入输出、字符串处理、数学运算等。使用库函数可以简化编程工作,提高开发效率。C标准库提供了丰富的函数,满足各种需求。
|
2月前
|
机器学习/深度学习 C语言
【c语言】一篇文章搞懂函数递归
本文详细介绍了函数递归的概念、思想及其限制条件,并通过求阶乘、打印整数每一位和求斐波那契数等实例,展示了递归的应用。递归的核心在于将大问题分解为小问题,但需注意递归可能导致效率低下和栈溢出的问题。文章最后总结了递归的优缺点,提醒读者在实际编程中合理使用递归。
64 7
|
2月前
|
存储 编译器 程序员
【c语言】函数
本文介绍了C语言中函数的基本概念,包括库函数和自定义函数的定义、使用及示例。库函数如`printf`和`scanf`,通过包含相应的头文件即可使用。自定义函数需指定返回类型、函数名、形式参数等。文中还探讨了函数的调用、形参与实参的区别、return语句的用法、函数嵌套调用、链式访问以及static关键字对变量和函数的影响,强调了static如何改变变量的生命周期和作用域,以及函数的可见性。
32 4
|
2月前
|
存储 编译器 C语言
C语言函数的定义与函数的声明的区别
C语言中,函数的定义包含函数的实现,即具体执行的代码块;而函数的声明仅描述函数的名称、返回类型和参数列表,用于告知编译器函数的存在,但不包含实现细节。声明通常放在头文件中,定义则在源文件中。
|
2月前
|
存储 C语言
【c语言】字符串函数和内存函数
本文介绍了C语言中常用的字符串函数和内存函数,包括`strlen`、`strcpy`、`strcat`、`strcmp`、`strstr`、`strncpy`、`strncat`、`strncmp`、`strtok`、`memcpy`、`memmove`和`memset`等函数的使用方法及模拟实现。文章详细讲解了每个函数的功能、参数、返回值,并提供了具体的代码示例,帮助读者更好地理解和掌握这些函数的应用。
27 0
|
2月前
|
C语言
【c语言】qsort函数及泛型冒泡排序的模拟实现
本文介绍了C语言中的`qsort`函数及其背后的回调函数概念。`qsort`函数用于对任意类型的数据进行排序,其核心在于通过函数指针调用用户自定义的比较函数。文章还详细讲解了如何实现一个泛型冒泡排序,包括比较函数、交换函数和排序函数的编写,并展示了完整的代码示例。最后,通过实际运行验证了排序的正确性,展示了泛型编程的优势。
23 0
|
2月前
|
算法 C语言
factorial函数c语言
C语言中实现阶乘函数提供了直接循环和递归两种思路,各有优劣。循环实现更适用于大规模数值,避免了栈溢出风险;而递归实现则在代码简洁度上占优,但需警惕深度递归带来的潜在问题。在实际开发中,根据具体需求与环境选择合适的实现方式至关重要。
31 0