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

相关文章

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. 数字

Python内置函数之classmethod函数使用详解

《Python内置函数之classmethod函数使用详解》:本文主要介绍Python内置函数之classmethod函数使用方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地... 目录1. 类方法定义与基本语法2. 类方法 vs 实例方法 vs 静态方法3. 核心特性与用法(1编程客

Python函数作用域示例详解

《Python函数作用域示例详解》本文介绍了Python中的LEGB作用域规则,详细解析了变量查找的四个层级,通过具体代码示例,展示了各层级的变量访问规则和特性,对python函数作用域相关知识感兴趣... 目录一、LEGB 规则二、作用域实例2.1 局部作用域(Local)2.2 闭包作用域(Enclos

MySQL count()聚合函数详解

《MySQLcount()聚合函数详解》MySQL中的COUNT()函数,它是SQL中最常用的聚合函数之一,用于计算表中符合特定条件的行数,本文给大家介绍MySQLcount()聚合函数,感兴趣的朋... 目录核心功能语法形式重要特性与行为如何选择使用哪种形式?总结深入剖析一下 mysql 中的 COUNT

Go语言中nil判断的注意事项(最新推荐)

《Go语言中nil判断的注意事项(最新推荐)》本文给大家介绍Go语言中nil判断的注意事项,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录1.接口变量的特殊行为2.nil的合法类型3.nil值的实用行为4.自定义类型与nil5.反射判断nil6.函数返回的

Go语言数据库编程GORM 的基本使用详解

《Go语言数据库编程GORM的基本使用详解》GORM是Go语言流行的ORM框架,封装database/sql,支持自动迁移、关联、事务等,提供CRUD、条件查询、钩子函数、日志等功能,简化数据库操作... 目录一、安装与初始化1. 安装 GORM 及数据库驱动2. 建立数据库连接二、定义模型结构体三、自动迁

MySQL 中 ROW_NUMBER() 函数最佳实践

《MySQL中ROW_NUMBER()函数最佳实践》MySQL中ROW_NUMBER()函数,作为窗口函数为每行分配唯一连续序号,区别于RANK()和DENSE_RANK(),特别适合分页、去重... 目录mysql 中 ROW_NUMBER() 函数详解一、基础语法二、核心特点三、典型应用场景1. 数据分

MySQL数据库的内嵌函数和联合查询实例代码

《MySQL数据库的内嵌函数和联合查询实例代码》联合查询是一种将多个查询结果组合在一起的方法,通常使用UNION、UNIONALL、INTERSECT和EXCEPT关键字,下面:本文主要介绍MyS... 目录一.数据库的内嵌函数1.1聚合函数COUNT([DISTINCT] expr)SUM([DISTIN

Python get()函数用法案例详解

《Pythonget()函数用法案例详解》在Python中,get()是字典(dict)类型的内置方法,用于安全地获取字典中指定键对应的值,它的核心作用是避免因访问不存在的键而引发KeyError错... 目录简介基本语法一、用法二、案例:安全访问未知键三、案例:配置参数默认值简介python是一种高级编