C语言学习NO.7-函数(二)函数递归

2023-12-28 20:28
文章标签 语言 函数 学习 递归 no.7

本文主要是介绍C语言学习NO.7-函数(二)函数递归,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

一、什么是递归?

程序调用自身的编程技巧称为递归( recursion),递归函数一定要有结束条件,否则会产生死递归,导致栈溢出(Stack overflow)。

#include <stdio.h>
int main()
{printf("Hello\n");main();	//main函数中用调用了main函数return 0; 
}			//程序会一直打印 Hello

递归作为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法,使用递归可以在解决一些复杂问题时将问题简单化,降低编程难度。

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

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

二、递归的两个必要条件

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

三、递归与迭代

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

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

输入:1234,输出 1 2 3 4.

参考代码:

#include <stdio.h>
//接受一个整型值(无符号),按照顺序打印它的每一位。
//输入:1234,输出 1 2 3 4.
//使用函数递归
void print(int n) 
{if(n>9)//当n逐渐为1234  123  12  1时,无法进入if语句中,转向下一语句{print(n/10);//进入if语句后进行函数调用}printf("%d ", n%10);//打印出1%10  12%10 123%10  1234%10  的值
}int main()
{int num = 1234;print(num);return 0; 
}
#include <stdio.h>
#include <math.h>
//将数字每一位打印出来
//无函数递归
int main()
{int n = 1234;int i = 0;int ret = n;for (i = 0; n != 0; i++){n = n/10;//123 12 1 0}while (ret != 0)//123 12 1   0{int m = pow(10, i);// 3 2 1 0    1000  100  10  1if(m<ret){printf("%d ", ret / m);//1  2  3  4  }ret = ret % m;//234 34 4i--;}return 0;
}

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

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

参考代码:

#include <stdio.h>
//编写函数不允许创建临时变量,求字符串的长度。
int Strlen(const char*str)
{if(*str == '\0')//字符串以\0为结尾return 0;elsereturn 1+Strlen(str+1);
}int main()
{char *p = "abcdef";int len = Strlen(p);printf("%d\n", len);return 0;
}

例3:求n的阶乘

求n的阶乘。(不考虑溢出)

参考代码:

int factorial(int n)
{//求n的阶乘。(不考虑溢出) if(n <= 1)return 1;elsereturn n * factorial(n-1);	//1*2*3*4*……*n-1*n
}int main()
{int n = 0;scanf("%d", &n);int ret = factorial(n);printf("%d\n", ret);return 0; 
}

在测试中,使用 factorial 函数求10000的阶乘(不考虑结果的正确性),程序会崩溃。

例4: 求第n个斐波那契数

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

参考代码:

int fib(int n)
{//求第n个斐波那契数。(不考虑溢出) if (n <= 2)return 1;elsereturn fib(n - 1) + fib(n - 2);
}

在测试中,如果使用 fib 这个函数的时候计算第50个斐波那契数字的时候特别耗费时间。

提问:为什么计算n的阶乘和斐波那契数存在问题?

我们发现 fib 函数在调用的过程中很多计算其实在一直重复。

把代码修改一下:

int count = 0;//全局变量int fib(int n)
{if(n == 3)count++;if (n <= 2)return 1;elsereturn fib(n - 1) + fib(n - 2);
}

最后我们输出看看count的值。

系统分配给程序的栈空间是有限的,如果调试 factorial 函数时参数较大,可能出现死递归情况,有可能导致一直开辟栈空间,最终产生栈空间耗尽的情况,这样的现象我们称为栈溢出(stack overflow)

解决上述的问题:

1. 将递归改写成非递归;

// //求n的阶乘
int factorial(int n) 
{int result = 1;while (n > 1){result *= n ;n -= 1;}return result; 
}int main()
{int n = 0;scanf("%d", &n);int ret = factorial(n);printf("%d\n", ret);return 0; 
}//求第n个斐波那契数
int fib(int n) 
{int result;int pre_result;int next_older_result;result = pre_result = 1;while (n > 2){n -= 1;next_older_result = pre_result;pre_result = result;result = pre_result + next_older_result;}return result; 
}

2. 使用 static 对象替代 nonstatic 局部对象。在递归函数设计中可以使用 static 对象替代 nonstatic 局部对象(即栈对象),这不仅可以减少每次递归调用和返回时产生和释放

nonstatic 对象的开销,而且 static 对象还可以保存递归调用的中间状态,并且可为各个调用层所访问。

提示

1. 许多问题是以递归的形式进行解释的,这只是因为它比非递归的形式更为清晰。

2. 但是这些问题的迭代实现往往比递归实现效率更高,虽然代码的可读性稍微差些。

3. 当一个问题相当复杂,难以用迭代实现时,此时递归实现的简洁性便可以补偿它所带来的运行时开销。

四、函数递归的练习题

练习1:走台阶

比如接下来的题目:假如有n个台阶,一次只能上1个台阶或2个台阶,请问走到第n个台阶有几种走法?

#include <stdio.h>
//递归
int step(int n)
{if(n <= 2)return n;return step(n-1)+step(n-2);
}
int main()
{int n = 0;scanf("%d",&n);int ret = step(n);printf("%d",ret);return 0;
}

练习2:编写一个函数 reverse_string(char * string)(递归实现)

实现:将参数字符串中的字符反向排列,不是逆序打印。

要求:不能使用C函数库中的字符串操作函数。

比如:

char arr[] = "abcdef";

逆序之后数组的内容变成:fedcba

#include <stdio.h>void reverse_string(char * string)
{if(*string != '\0')reverse_string(string+1);//字符串逐渐后移一位,直到'\0'if(*string != '\0')//为了不把'\0'打印出来printf("%c",*string);
}int main()
{char arr[] = {"abcdefg"};reverse_string(arr);return 0;
}

练习3:写一个递归函数DigitSum(n),输入一个非负整数,返回组成它的数字之和

例如,调用DigitSum(1729),则应该返回1+7+2+9,它的和是19

输入:1729,输出:19

#include <stdio.h>int DigitSum(int n)
{static int sum = 0;if(n>9)DigitSum(n/10);//172 17 1sum += n%10;//1+7+2+9return sum;
}int main()
{int n = 0;scanf("%d",&n);//输入一个非负整数int ret = DigitSum(n);printf("%d",ret);return 0;
}

练习4:编写一个函数实现n的k次方,使用递归实现。

#include <stdio.h>int my_pow(int n,int k)
{if(k == 0)return 1;elsereturn n*my_pow(n,k-1);
}int main()
{int n = 0;int k = 0;scanf("%d %d",&n,&k);int ret = my_pow(n,k);printf("%d",ret);return 0;
}

这篇关于C语言学习NO.7-函数(二)函数递归的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/547192

相关文章

postgresql使用UUID函数的方法

《postgresql使用UUID函数的方法》本文给大家介绍postgresql使用UUID函数的方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录PostgreSQL有两种生成uuid的方法。可以先通过sql查看是否已安装扩展函数,和可以安装的扩展函数

MySQL字符串常用函数详解

《MySQL字符串常用函数详解》本文给大家介绍MySQL字符串常用函数,本文结合实例代码给大家介绍的非常详细,对大家学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录mysql字符串常用函数一、获取二、大小写转换三、拼接四、截取五、比较、反转、替换六、去空白、填充MySQL字符串常用函数一、

C++中assign函数的使用

《C++中assign函数的使用》在C++标准模板库中,std::list等容器都提供了assign成员函数,它比操作符更灵活,支持多种初始化方式,下面就来介绍一下assign的用法,具有一定的参考价... 目录​1.assign的基本功能​​语法​2. 具体用法示例​​​(1) 填充n个相同值​​(2)

MySql基本查询之表的增删查改+聚合函数案例详解

《MySql基本查询之表的增删查改+聚合函数案例详解》本文详解SQL的CURD操作INSERT用于数据插入(单行/多行及冲突处理),SELECT实现数据检索(列选择、条件过滤、排序分页),UPDATE... 目录一、Create1.1 单行数据 + 全列插入1.2 多行数据 + 指定列插入1.3 插入否则更

PostgreSQL中rank()窗口函数实用指南与示例

《PostgreSQL中rank()窗口函数实用指南与示例》在数据分析和数据库管理中,经常需要对数据进行排名操作,PostgreSQL提供了强大的窗口函数rank(),可以方便地对结果集中的行进行排名... 目录一、rank()函数简介二、基础示例:部门内员工薪资排名示例数据排名查询三、高级应用示例1. 每

全面掌握 SQL 中的 DATEDIFF函数及用法最佳实践

《全面掌握SQL中的DATEDIFF函数及用法最佳实践》本文解析DATEDIFF在不同数据库中的差异,强调其边界计算原理,探讨应用场景及陷阱,推荐根据需求选择TIMESTAMPDIFF或inte... 目录1. 核心概念:DATEDIFF 究竟在计算什么?2. 主流数据库中的 DATEDIFF 实现2.1

深入理解Go语言中二维切片的使用

《深入理解Go语言中二维切片的使用》本文深入讲解了Go语言中二维切片的概念与应用,用于表示矩阵、表格等二维数据结构,文中通过示例代码介绍的非常详细,需要的朋友们下面随着小编来一起学习学习吧... 目录引言二维切片的基本概念定义创建二维切片二维切片的操作访问元素修改元素遍历二维切片二维切片的动态调整追加行动态

MySQL中的LENGTH()函数用法详解与实例分析

《MySQL中的LENGTH()函数用法详解与实例分析》MySQLLENGTH()函数用于计算字符串的字节长度,区别于CHAR_LENGTH()的字符长度,适用于多字节字符集(如UTF-8)的数据验证... 目录1. LENGTH()函数的基本语法2. LENGTH()函数的返回值2.1 示例1:计算字符串

Go语言中make和new的区别及说明

《Go语言中make和new的区别及说明》:本文主要介绍Go语言中make和new的区别及说明,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1 概述2 new 函数2.1 功能2.2 语法2.3 初始化案例3 make 函数3.1 功能3.2 语法3.3 初始化

MySQL 中的 CAST 函数详解及常见用法

《MySQL中的CAST函数详解及常见用法》CAST函数是MySQL中用于数据类型转换的重要函数,它允许你将一个值从一种数据类型转换为另一种数据类型,本文给大家介绍MySQL中的CAST... 目录mysql 中的 CAST 函数详解一、基本语法二、支持的数据类型三、常见用法示例1. 字符串转数字2. 数字