【C语言】带你玩转递归,迭代算法1

简介: 【C语言】带你玩转递归,迭代算法

前言

不像加减乘除,我们求学期间就已经见识过多次了,而大多数初学者在此之前可能都从未了解接触过递归思想,这使得很难上手递归算法,今天我希望能尽我所能结合画图已经例题的方法把递归算法讲解的通俗易懂,帮助大家入门


废话不多说了,我们开始今天的内容

一.什么是递归?

程序调用自身的编程技巧称为递归( recursion)。

递归做为一种算法在程序设计语言中广泛应用。 递归算法通常指一个过程或函数在其定义或说明中直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。

递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量。(也就是说我们现在学的需要使用递归的场景大多数通过循环也能解决,在下面介绍的例子中会用循环也实现一遍)

递归的主要思考方式在于:把大事化小

当你在使用递归时遇到思考瓶颈,请牢记大事化小的思想!!

二.递归的两个必要条件

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

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

当你不满足这两个条件的任意一条时,程序会陷入死循环

当你的递归写出bug时,往往是没考虑上面这两个条件或者条件设置有误,调试时多想想递归条件最好能够画下图帮助自己理解。


三.配合实例讲解

打印整型数据的每一位

实例一:

接受一个整型值(无符号),按照顺序打印它的每一位。

例如:

输入:1234,输出 1 2 3 4


代码如下:

#include <stdio.h>
void print(int n)
{
if(n>9)//如果不大于9直接打印当前n的值即可
{
print(n/10);
}
printf("%d ", n%10);
}
int main()
{
int num = 1234;
print(num);
return 0;
}

我们想要把一个四位数甚至更多位的数每一位给剥离出来,首先要想到的是怎么得到每一位

我们知道,对10取余%就可以得到这个数的个位的数,而除以10就可以把这一位给消去,此时我们就可以这样实现(以下把n当作一个四位数举例)

先让n对10%得到此时这一位的数,然后将n/10来到下一位,再让n对10%得到这位数继续朝下进行直至n对10%等于0,说明此时n是个小于10的数只剩下它需要取了,取下它结束递归即可

画图解释

递归的递就是传递的意思,而归的意思是回归

fa73e68a67144951899245cbd43bb120.png

这就是递归!

解释完了递归在这段代码的应用,我们来讲讲这个代码中出现的问题

当我们中用户某天突发奇想输入了一个负数进去会发生什么呢?

61418d7a5d954fd185449c1edf39bda0.png

我们这个程序设定的条件是只针对正数的,要想输入一个负数也能打印就得这样修改代码

void print(int n)
{
  if (n > 9)//如果不大于9直接打印当前n的值即可
  {
    print(n / 10);
  }
  else if (n < -9)
  {
    print(n / 10);
  }
  printf("%d ", n % 10);
}
int main()
{
  int num = -1234;
  print(num);
  return 0;
}

或者把我们传入的int改为一个无符号整型

void print(unsigned int n)
{
  if (n > 9)//如果不大于9直接打印当前n的值即可
  {
    print(n / 10);
  }
  /*else if (n < -9)
  {
    print(n / 10);
  }*/
  printf("%d ", n % 10);
}

这里虽然都是非常简单的地方,但我想提醒大家的是,无论在递归或者任何其他程序的编写中我们都得尽可能考虑各方面的情况,在以后的程序猿工作中,我们要知道用户是不总是照着你的指示来使用程序的,我们得尽可能保证程序的避免上面这种bug。

循环实现

//判断输入数字位数
#include<math.h>
int Strlen(unsigned int n)
{
  int count = 0;
  while (n / 10)
  {
    count++;
    n /= 10;
  }
  return count;
}
void print(unsigned int n)
{
  int i = 0;
  int ret = Strlen(n);
  if (n > 9)
  {
    for (i = ret; i > 0; i--)
    {
      int m = pow(10, i);
      printf("%d ", n / m);
      n %= m;
    }
  }
  printf("%d", n);
}
int main()
{
  int num = 123456789;
  print(num);
  return 0;
}

我们先来看看效果

a9d18c96e5df4d0aa5d31f050d5d31e4.png


说实话,同样实现一个功能递归比循环简单多了,从代码的行数就能看出来。这就是我们使用递归算法的意义


求字符串长度

实例二

编写函数不允许创建临时变量,求字符串的长度。

#include <stdio.h>
int Strlen(const char*str)
{
if(*str == '\0')//是个空字符串
return 0;
else
    return 1+Strlen(str+1);//每次递归让Strlen朝后移动一位直至遇到"\0"不满足递归条件
}
int main()
{
char *p = "abcde";
int len = Strlen(p);
printf("%d\n", len);
return 0;
}

咱们还是画个图理解吧

3de357571fd4427f9d93f5aadea699fa.png


结合咱们这个图理解起来就比较简单啦,我希望以后你自己写的时候在有弄不清逻辑时也能画一个类似的图来理解。

循环实现

int Strlen(char* s)

int Strlen(char* s)
{
  int count = 0;
  while (*s != '\0')
  {
    count++;
    s++;
  }
  return count;
}
int main()
{
  char* p = "abcde";
  int len = Strlen(p);
  printf("%d\n", len);
  return 0;
}

结合咱们这个图理解起来就比较简单啦,我希望以后你自己写的时候在有弄不清逻辑时也能画一个类似的图来理解。

目录
相关文章
|
12天前
|
算法 数据处理 C语言
C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合
本文深入解析了C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合,旨在帮助读者掌握这一高效的数据处理方法。
23 1
|
11天前
|
存储 算法 程序员
C 语言递归算法:以简洁代码驾驭复杂逻辑
C语言递归算法简介:通过简洁的代码实现复杂的逻辑处理,递归函数自我调用解决分层问题,高效而优雅。适用于树形结构遍历、数学计算等领域。
|
12天前
|
存储 缓存 算法
C语言在实现高效算法方面的特点与优势,包括高效性、灵活性、可移植性和底层访问能力
本文探讨了C语言在实现高效算法方面的特点与优势,包括高效性、灵活性、可移植性和底层访问能力。文章还分析了数据结构的选择与优化、算法设计的优化策略、内存管理和代码优化技巧,并通过实际案例展示了C语言在排序和图遍历算法中的高效实现。
33 2
|
12天前
|
机器学习/深度学习 算法 数据挖掘
C语言在机器学习中的应用及其重要性。C语言以其高效性、灵活性和可移植性,适合开发高性能的机器学习算法,尤其在底层算法实现、嵌入式系统和高性能计算中表现突出
本文探讨了C语言在机器学习中的应用及其重要性。C语言以其高效性、灵活性和可移植性,适合开发高性能的机器学习算法,尤其在底层算法实现、嵌入式系统和高性能计算中表现突出。文章还介绍了C语言在知名机器学习库中的作用,以及与Python等语言结合使用的案例,展望了其未来发展的挑战与机遇。
30 1
|
12天前
|
并行计算 算法 测试技术
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
37 1
|
1月前
|
存储 算法 数据管理
C语言算法复杂度
【10月更文挑战第20天】
C语言算法复杂度
|
29天前
|
算法 Python
在Python编程中,分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题,递归解决后合并结果
在Python编程中,分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题,递归解决后合并结果;贪心算法在每一步选择局部最优解,追求全局最优;动态规划通过保存子问题的解,避免重复计算,确保全局最优。这三种算法各具特色,适用于不同类型的问题,合理选择能显著提升编程效率。
41 2
|
2月前
|
机器学习/深度学习 C语言
【c语言】一篇文章搞懂函数递归
本文详细介绍了函数递归的概念、思想及其限制条件,并通过求阶乘、打印整数每一位和求斐波那契数等实例,展示了递归的应用。递归的核心在于将大问题分解为小问题,但需注意递归可能导致效率低下和栈溢出的问题。文章最后总结了递归的优缺点,提醒读者在实际编程中合理使用递归。
68 7
|
2月前
|
C语言
c语言回顾-函数递归(上)
c语言回顾-函数递归(上)
35 2
|
2月前
|
算法 搜索推荐 Shell
数据结构与算法学习十二:希尔排序、快速排序(递归、好理解)、归并排序(递归、难理解)
这篇文章介绍了希尔排序、快速排序和归并排序三种排序算法的基本概念、实现思路、代码实现及其测试结果。
27 1