你会使用函数的递归和迭代吗?----------C语言函数学习(4)详解

简介: 你会使用函数的递归和迭代吗?----------C语言函数学习(4)详解

前言


一、函数递归

1.什么是递归?

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

(2)递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调用自身的

(3)一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解,递归策略

递归的主要思想方式是:把大事化小

2.递归的两个必要条件

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

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

3.最简单的递归例子

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
//函数递归
int main() {
  printf("hehe\n");
  main();
  return 0;
}

屏幕上会无限循环打印hehe:

并且出现报错:

Stack overflow:栈溢出

原因:

main函数中无限调用main()函数,又因为每次函数调用都得向栈区申请空间,这样的话一直在栈区申请空间,迟早栈区的空间会被耗干,当被耗干的那一刻,就会报错Stack overflow

结论:递归虽然是自己调用自己,但是绝不是无节制的自己调用自己,

内存的划分:栈区,堆区,静态区

注意:那么函数在调用过程中是如何向栈区申请空间的?参数是如何传参的?传过去函数是如何使用的?

内容较多,请小伙伴们持续关注我的博客,后面会出相关内容哦~💕

4.递归练习:

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

例如:
输入:1234,输出 1 2 3 4

a.代码讲解

//思路: 观察数字

// 1234

// 1234%10=4

// 1234/10=123 123%10=3

// 123/10=12 12%10=2

// 12/10=1 1%10=1

//%u—无符号的整数

//%d—有符号的整数

//1.首先列出框架int main(){}

//2.控制不同的类型%u

//3.将题目封装成一个函数Print()

//4.通过观察可以发现Print()函数最容易打印出来的是4

//5.分析:

// Print(1234)拆解为:一层一层往下拆数字

// Print(123) 4 先把123打印在屏幕上,再把4打印出来

// Print(12) 3 4 先把12打印在屏幕上,再把3打印在屏幕上

// Print(1) 2 3 4 先把1打印在屏幕上,再把2打印在屏幕上

void Print(unsigned int n) {
  if (n > 9)          //n>9:说明是两位数以上的数字.
            //如果是一位数,就不用拆分.两位数以上的数字才要拆分,递归的条件很重要
  {
    Print(n / 10);   //Print是自定义函数,1234传进来之后>9,接着调用Print(123),123>9,调用Print(12),12>9,调用Print(1),1<9,不执行if语句,打印出(1%10)结果1,
                     //逐层返回,回到Print(12),接下来打印(12%10)结果2
             //逐层返回,回到Print(123),接下来打印(123%10)结果3
             //逐层返回,回到Print(1234).接下来打印Print(1234%10)结果4
            //Print(n / 10);   /10的操作很重要,如果没有/10的操作,一直传入的n不断进入递归
  }
  printf("%d ", n % 10);
}
int main() {
  unsigned int num = 0;   //unsigned类型的变量
  scanf("%u", &num);      //%u---无符号的整数 (说明不能输入负数,即使输入负数也把它当做正数来看待)
  Print(num);             //Print()函数负责把num的每一位打印在屏幕上
  return 0;
}

b画图讲解

递归: 递推, 回归

拆分概况:

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

a.如果单一的求字符串的长度
#include<stdio.h>
#include<string.h>          //strlen头文件
int main() {
  char arr[10] = "abcdef";
  int len = strlen(arr);
  printf("%d\n", len);
  return 0;
}

b.如果单一的写一个函数求字符串的长度
//先写一个函数求字符串长度
//但是该方法创建了临时变量
#include<stdio.h>
#include<string.h>    
int my_strlen(char* str) {  //str接收a的地址
  int count = 0;            //为了统计字符串的个数创建一个临时变量count
  while (*str != '\0') {    //strlen统计的是字符串中\0前字符的个数
    count++;              //计数器++
    str++;                //地址++,看当前的下一个字符是不是\0
  }
  return count;
}
int main() {  
  char arr[10] = "abcdef";     //数组内容:[a b c d e f \0 - - -]
  int len = my_strlen(arr);  //数组名是数组首元素的地址,所以把a的地址传给函数
  printf("%d\n",len);
  return 0;
}

c.题目正解:编写函数不允许创建临时变量,求字符串的长度

//不创建临时变量的思路:

// 当发现字符串第一个字符不是\0的时候,字符串的长度应该为1 总长度=1+后面字符串的长度

// my_strlen(“abcdef”);拆分过程

// 1+my_strlen(“bcdef”);

// my_strlen(“bcdef”);拆分为: 1+my_strlen(“cdef”);

// my_strlen(“cdef”); 拆分为: 1+my_strlen(“def”);

// my_strlen(“def”); 拆分为: 1+my_strlen(“ef”);

// my_strlen(“ef”); 拆分为: 1+my_strlen(“f”);

// my_strlen(“f”); 拆分为: 1+my_strlen(" ");

#include<stdio.h>
int my_strlen(char* str) {  
  if (*str != '\0')                   //递归的条件   让它不断逼近跳出递归的条件
    return 1 + my_strlen(str + 1);  //不能写成return 1 + my_strlen(str + +);    str后置++:(先使用后++)先是把str的地址传出去之后,str再++. 传出去的str没有变化,,和原来一样,没用,是错的死递归
                                      //但是也不要写成++str,因为这样的话在原来函数中的str被修改了
  else
    return 0;
}
int main() {
  char arr[10] = "abcdef";             //[a b c d e f \0 - - -]
  int len = my_strlen(arr);
  printf("%d\n", len);
  return 0;
}

画图讲解:(比如"abc\0")

**注意:**在递归的使用中尽量不要使用前置++或者后置++,会有副作用导致出错的.

int my_strlen(char* str) {  
  if (*str != '\0')                   //递归的条件   让它不断逼近跳出递归的条件
    return 1 + my_strlen(str + 1);  //不能写成return 1 + my_strlen(str + +);    str后置++:(先使用后++)先是把str的地址传出去之后,str再++. 传出去的str没有变化,,和原来一样,没用,是错的死递归
                                      //但是也不要写成++str,因为这样的话在原来函数中的str被修改了
  else
    return 0;
}

通过窗口监视观察:

二、函数迭代

循环是迭代的一种.循环法也叫迭代法.

下面我们通过例子来学习:

1.计算n的阶乘

(1)解法一:循环的方法(迭代法)

int fac(int n){
  int i = 0;
  int ret = 1;
  for (i = 1; i <= n; i++) {
    ret = ret * i;
  }
  return ret;
}
int main() {
  int n = 0;
  scanf("%d", &n);
  int ret = fac(n);
  printf("%d\n", ret);
  return 0;
}

(2)解法二:递归法

//fac(n) n<=1;fac=1

// n>1;fac=n*fac(n-1)

int fac(int n) {
  if (n <= 1)
    return 1;
  else
    return n * fac(n - 1);
}
int main() {
  int n = 0;
  scanf("%d", &n);
  int ret = fac(n);
  printf("%d\n", ret);
  return 0;
}

2.求第n个斐波那契数。(不考虑溢出)

什么是斐波那契数列?

//1 1 2 3 5 8 13 …

//特点是一个数是前两个数之和

求第n个斐波那契数,前提是给出前两个数

//设第n个斐波那契数Fib(n)

n<=2, Fib=1

n>2, Fib=Fib(n-1)+Fic(n-2)

(1)解法一:递归的方法(效率低)

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\n",ret);
}

当输入5时,结果如下:

当输入一些较小的数字,结果快速算出且正确

但是当输入50时:

发现一直没有返回结果,但是程序在运行,说明程序计算繁忙,这是为什么呢?

比如:在求第40个斐波那契数时,要计算第39个和第38个斐波那契数;计算第39个斐波那契数时,要先计算第38个和第37个斐波那契数;计算第38个斐波那契数时,要先计算第37个和第36个斐波那契数…

发现会计算大量重复的数据,我们可以通过代码计算一下在求第40个斐波那契数时,第三个斐波那契数被重复计算了多少次?

int count = 0;
int Fib(int n) {
  if (n == 3)
    count++;
  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\n", ret);
  printf("count=%d\n", count);
}

由此可见,仅仅是计算第三个斐波那契数的次数就达到3900多万次.

说明在这个问题上用递归的方法解决效率较低

注意:使用递归时出现栈溢出的问题:

我们要去看一下是不是死递归了或者是不是在栈里面开辟的空间过多了.

系统分配给程序的栈空间是有限的,但是如果出现了死循环,或者(死递归),这样有可能导致一直开辟栈空间,最终产生栈空间耗尽的情况,这样的现象我们称为栈溢出。

(2)解法二:迭代法(最佳)

不断用前两个数相加得到第三个的方法求

//迭代的方式----把一件事情反复去做:不断用前两个数相加得到第三个的方法求

//当求第三个斐波那契数时,将a,b赋值1,求出c 共进行一次循环

//当求第四个斐波那契数时,向上一次b的值赋值给a,将上一次c的值赋值给b,求出c 共进行两次循环

//…

int Fib(int n) {
  int a = 1;
  int b = 1;
  int c = 1;         //c的初始值设为0时候会有漏洞,因为当n=1或者n=2时传进来不进入while循环,return c的话c=0,不符合斐波那契数列
                     //所以c的初始值设为1
  while (n>=3) {     //当n=1或者n=2时不需要进来
    c = a + b;
    a = b;
    b = c;         //n--很重要,如果没有n--,n就会进入while的死循环
    n--;           //n=3时,n--变为2,不再进入循环
  }
  return c;          //当while循环停下来的时候要返回结果c,c就是要求的第n个斐波那契数
}
int main() {
  int n = 0;
  scanf("%d", &n);
  int ret = Fib(n);
  printf("%d\n", ret); 
  return 0;
}

代码的效率大大提高,只不过结果是错的,因为范围有限,放不下太大的数字,如果一直算下去,计算的结果溢出了,溢出之后,而恰好符号位是1的话,那我们看到的就是负数.

但是在不溢出的情况下,计算结果是非常快的,同时这道题目也声明了不考虑溢出的情况,这样写是完全没问题的啦~.🤞

3.汉诺塔问题

4.青蛙跳台阶问题

递归经典题目3.4请小伙伴们关注后续博客,将详细讲解.


总结

今天的内容你学会了吗小伙伴们?💕💕

如果哪里写的有问题,欢迎大家帮我指正.

最后,如果对您有所帮助的话,可以留下关注点赞收藏哦~🥰💕❤️

相关文章
|
安全 C语言
C语言中的字符、字符串及内存操作函数详细讲解
通过这些函数的正确使用,可以有效管理字符串和内存操作,它们是C语言编程中不可或缺的工具。
687 15
|
存储 C语言
`scanf`是C语言中用于按格式读取标准输入的函数
`scanf`是C语言中用于按格式读取标准输入的函数,通过格式字符串解析输入并存入指定变量。需注意输入格式严格匹配,并建议检查返回值以确保读取成功,提升程序健壮性。
1752 0
|
人工智能 Java 程序员
一文彻底搞清楚C语言的函数
本文介绍C语言函数:函数是程序模块化的工具,由函数头和函数体组成,涵盖定义、调用、参数传递及声明等内容。值传递确保实参不受影响,函数声明增强代码可读性。君志所向,一往无前!
823 1
一文彻底搞清楚C语言的函数
|
存储 编译器 C语言
【C语言程序设计——函数】分数数列求和2(头歌实践教学平台习题)【合集】
函数首部:按照 C 语言语法,函数的定义首部表明这是一个自定义函数,函数名为fun,它接收一个整型参数n,用于指定要求阶乘的那个数,并且函数的返回值类型为float(在实际中如果阶乘结果数值较大,用float可能会有精度损失,也可以考虑使用double等更合适的数据类型,这里以float为例)。例如:// 函数体代码将放在这里函数体内部变量定义:在函数体中,首先需要定义一些变量来辅助完成阶乘的计算。比如需要定义一个变量(通常为float或double类型,这里假设用float。
912 3
|
存储 算法 安全
【C语言程序设计——函数】分数数列求和1(头歌实践教学平台习题)【合集】
if 语句是最基础的形式,当条件为真时执行其内部的语句块;switch 语句则适用于针对一个表达式的多个固定值进行判断,根据表达式的值与各个 case 后的常量值匹配情况,执行相应 case 分支下的语句,直到遇到 break 语句跳出 switch 结构,若没有匹配值则执行 default 分支(可选)。例如,在判断一个数是否大于 10 的场景中,条件表达式为 “num> 10”,这里的 “num” 是程序中的变量,通过比较其值与 10 的大小关系来确定条件的真假。常量的值必须是唯一的,且在同一个。
1170 2
|
C# C语言 C++
从头开始学习c语言
以前的时候学习C语言时候认为C语言不过是一个学习的工具,学习一些理论知识就达到目的了,谁会用这么傻的语言啊,连个界面也没有,不像vb一下子就做出一个窗体来,放上几个按钮就可以了 后来学习C++的时候,认为C++与C是一种完全不同的语言,两者基本没有什么兼容性,当时在学校里看书的时候,一直比较纳闷为会c++的书上会写C++/C语言教程,到了现在才明白,我去C++与C本来就是一体是一脉相承的
1201 0
|
存储 算法 C语言
【C语言程序设计——函数】素数判定(头歌实践教学平台习题)【合集】
本内容介绍了编写一个判断素数的子函数的任务,涵盖循环控制与跳转语句、算术运算符(%)、以及素数的概念。任务要求在主函数中输入整数并输出是否为素数的信息。相关知识包括 `for` 和 `while` 循环、`break` 和 `continue` 语句、取余运算符 `%` 的使用及素数定义、分布规律和应用场景。编程要求根据提示补充代码,测试说明提供了输入输出示例,最后给出通关代码和测试结果。 任务核心:编写判断素数的子函数并在主函数中调用,涉及循环结构和条件判断。
1111 23
|
算法 C语言
【C语言程序设计——函数】利用函数求解最大公约数和最小公倍数(头歌实践教学平台习题)【合集】
本文档介绍了如何编写两个子函数,分别求任意两个整数的最大公约数和最小公倍数。内容涵盖循环控制与跳转语句的使用、最大公约数的求法(包括辗转相除法和更相减损术),以及基于最大公约数求最小公倍数的方法。通过示例代码和测试说明,帮助读者理解和实现相关算法。最终提供了完整的通关代码及测试结果,确保编程任务的成功完成。
1067 15
【C语言程序设计——函数】利用函数求解最大公约数和最小公倍数(头歌实践教学平台习题)【合集】
|
C语言
【C语言程序设计——函数】亲密数判定(头歌实践教学平台习题)【合集】
本文介绍了通过编程实现打印3000以内的全部亲密数的任务。主要内容包括: 1. **任务描述**:实现函数打印3000以内的全部亲密数。 2. **相关知识**: - 循环控制和跳转语句(for、while循环,break、continue语句)的使用。 - 亲密数的概念及历史背景。 - 判断亲密数的方法:计算数A的因子和存于B,再计算B的因子和存于sum,最后比较sum与A是否相等。 3. **编程要求**:根据提示在指定区域内补充代码。 4. **测试说明**:平台对代码进行测试,预期输出如220和284是一组亲密数。 5. **通关代码**:提供了完整的C语言代码实现
568 24
|
存储 C语言
【C语言程序设计——函数】递归求斐波那契数列的前n项(头歌实践教学平台习题)【合集】
本关任务是编写递归函数求斐波那契数列的前n项。主要内容包括: 1. **递归的概念**:递归是一种函数直接或间接调用自身的编程技巧,通过“俄罗斯套娃”的方式解决问题。 2. **边界条件的确定**:边界条件是递归停止的条件,确保递归不会无限进行。例如,计算阶乘时,当n为0或1时返回1。 3. **循环控制与跳转语句**:介绍`for`、`while`循环及`break`、`continue`语句的使用方法。 编程要求是在右侧编辑器Begin--End之间补充代码,测试输入分别为3和5,预期输出为斐波那契数列的前几项。通关代码已给出,需确保正确实现递归逻辑并处理好边界条件,以避免栈溢出或结果
1032 16