C语言的递归函数详解

目录
  • 函数递归
  • 什么是递归?
  • 递归的俩个必要条件
    • 代码引例1
    • 栈溢出(Stack Overflow)
  • 合理使用递归
    • 代码引例3
    • 代码引例4
    • 解释要合理使用递归
  • 总结

函数递归

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

函数自己调用自己就是递归

你也可以理解成是一种嵌套结构,但递归分为俩部分,第一是“递”,进入嵌套结构。第二是”归“,最终会一步一步返回。第一次接触递归都会很懵,慢慢理解这个过程就明白了。

什么是递归?

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

递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量。

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

递归的俩个必要条件

代码引例1

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

例如:

输入:123,输出 1 2 3

参考代码:

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

运行结果如下:

我们要怎么理解这个函数递归的实现呢

我们可以采用画图方式理解这个过程

所以我们可以看到,递归必须满足俩个必要条件:

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

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

题中的限制条件就是(n>9),当我们的n通过(n/10)越来越少,直至n=1,无法满足时,递归停止,并开始返回。

这里有一个重要点就是print(n/10),如果没有这个条件,换成print(n)的话,n一直无法减小,一直进行递归。最后会导致栈溢出(Stack Overflow)。

栈溢出(Stack Overflow)

关于栈溢出,我就先简单介绍一下栈

栈:栈是一种计算机系统中的数据结构,它按照先进后出的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹出数据(最后一个数据被第一个读出来),是一种特殊的线性表。栈的操作常用的有进栈(PUSH),出栈(POP),还有常用的标识栈顶和栈底。

可以把栈想象成一摞扑克牌一样,一张一张叠加起来。

而栈溢出呢是缓冲区溢出的一种,缓冲区溢出:简单的说,缓冲区溢出就是超长的数据向小缓冲区复制,导致数据超出了小缓冲区,导致缓冲区其他的数据遭到破坏,这就是缓冲区溢出。而栈溢出是缓冲区溢出的一种,也是最常见的。只不过栈溢出发生在栈,堆溢出发生在堆,其实都是一样的。

而在代码引例1中

系统分配给程序的栈空间是有限的,但是如果出现了死循环,或者(死递归),这样有可能导致一

直开辟栈空间,最终产生栈空间耗尽的情况,这样的现象我们称为栈溢出

合理使用递归

使用递归的宗旨是把大事化小

所以遇到问题时,我们应该明白是要把问题简单化,而不是习惯用递归,就一直用递归思考问题

我们应该清楚是不是用递归的思想会比较简单,或者换成递归的思想也可以实现,我们可以通过例题明白

代码引例3

求n的阶乘

用循环的方法,代码如下:

int main()
{
	int n = 0;
	int ret = 1;
	scanf("%d", &n);
	//循环产生1~n的数字
	int i = 0;
	for (i = 1; i <= n; i++)
	{
		ret = ret * i;
	}
	printf("ret = %d\n", ret);

	return 0;
}

而采用递归的话,代码如下:

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;
}

很多人刚学递归,都是懂了,但不知道怎么用。

而这道题可以先用公式来理解题目,再来用递归就容易多了

再来对比一下函数的代码,是不是清晰明了呢

代码引例4

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

代码如下:

int fib(int n) {
 if (n <= 2)
 return 1;
    else
    return fib(n - 1) + fib(n - 2);
}

这道题同样我们也可以利用公式构造一个函数实现递归

具体思路如下:

解释要合理使用递归

通过以上俩个例题,我们可以发现俩个问题

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

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

为什么呢?

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

如果我们把代码修改一下:

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

最后我们输出看看count,是一个很大很大的值。

那我们如何改进呢?

在调试 factorial 函数的时候,如果你的参数比较大,那就会报错: stack overflow(栈溢出)

这样的信息。

那如何解决上述的问题:

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

2.使用static对象替代 nonstatic 局部对象。在递归函数设计中,可以使用 static 对象替代

nonstatic 局部对象(即栈对象),这不仅可以减少每次递归调用和返回时产生和释放 nonstatic 对象的开销,而且 static 对象还可以保存递归调用的中间状态,并且可为各个调用层所访问

比如,下面代码就采用了,非递归的方式来实现:

//求n的阶乘
int factorial(int n) {
        int result = 1;
        while (n > 1)
       {
             result *= n ;
             n -= 1;
       }
        return result; }
//求第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;
     }

提示:

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

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

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

总结

本篇文章就到这里了,希望能够给你带来帮助,也希望您能够多多关注我们的更多内容!

(0)

相关推荐

  • C语言函数的基本使用和递归详解

    目录 本章目标 函数是什么 C语言中函数的分类 库函数 如何学会使用库函数? 自定义函数 函数的参数 函数的调用: 函数的嵌套调用和链式访问 嵌套调用 链式访问 函数的声明和定义 函数递归 什么是递归? 递归的两个必要条件 递归与迭代 总结 本章目标 秃头侠们好呀,今天我们一起学习函数! 目标: 本章主要掌握函数的基本使用和递归 函数是什么 数学中我们常见到函数的概念.但是你了解C语言中的函数吗? 维基百科中对函数的定义:子程序 在计算机科学中,子程序(英语:Subroutine, proced

  • 一篇文章带你了解C语言函数递归

    目录 什么是递归? 递归的两个必要条件 递归实例 实例1(按照顺序打印一个数的整形值) 画图讲解 完整代码 实例2 (使用函数在不创建变量的情况下求字符串长度) 画图讲解 程序运行结果 完整代码 递归与迭代 实例1 (求n的阶乘) 方法一(使用递归) 方法二(使用迭代) 实例2 (求解斐波那契数列) 方法一 (递归求解) 方法二(迭代求解) 总结 什么是递归? 递归(recursion):程序调用自身的一种编程技巧. 如何理解函数递归: 1.从调用自身层面:函数递归就是函数自己调用自己. 2.从

  • C语言函数的递归和调用实例分析

    一.基本内容: C语言中的函数可以递归调用,即:可以直接(简单递归)或间接(间接递归)地自己调自己. 要点: 1.C语言函数可以递归调用. 2.可以通过直接或间接两种方式调用.目前只讨论直接递归调用. 二.递归条件 采用递归方法来解决问题,必须符合以下三个条件: 1.可以把要解决的问题转化为一个新问题,而这个新的问题的解决方法仍与原来的解决方法相同,只是所处理的对象有规律地递增或递减. 说明:解决问题的方法相同,调用函数的参数每次不同(有规律的递增或递减),如果没有规律也就不能适用递归调用. 2

  • 使用C语言递归与非递归实现字符串反转函数char *reverse(char *str)的方法

    代码如下所示: 复制代码 代码如下: // 递归实现字符串反转   char *reverse(char *str)   {    if( !str )    {     return NULL; } int len = strlen(str);       if( len > 1 )       {           char ctemp =str[0];           str[0] = str[len-1];              str[len-1] = '/0';// 最后一

  • C语言函数的基本使用和递归小结

    本章目标 秃头侠们好呀,今天我们一起学习函数! 目标: 本章主要掌握函数的基本使用和递归 函数是什么 数学中我们常见到函数的概念.但是你了解C语言中的函数吗? 维基百科中对函数的定义:子程序 在计算机科学中,子程序(英语:Subroutine, procedure, function, routine, method,subprogram, callable unit),是一个大型程序中的某部分代码, 由一个或多个语句块组成.它负责完成某项特定任务,而且相较于其他代 码,具备相对的独立性. 一般

  • C语言的递归函数详解

    目录 函数递归 什么是递归? 递归的俩个必要条件 代码引例1 栈溢出(Stack Overflow) 合理使用递归 代码引例3 代码引例4 解释要合理使用递归 总结 函数递归 程序调用自身的编程技巧称为递归 recursion) 函数自己调用自己就是递归 你也可以理解成是一种嵌套结构,但递归分为俩部分,第一是“递”,进入嵌套结构.第二是”归“,最终会一步一步返回.第一次接触递归都会很懵,慢慢理解这个过程就明白了. 什么是递归? 递归做为一种算法在程序设计语言中广泛应用. 一个过程或函数在其定义或

  • 易语言子程序知识点详解

    将程序分割成较小的逻辑组件就可以简化程序设计任务,这些逻辑组件被称为子程序. 子程序可用于压缩重复任务或共享任务,例如,压缩频繁的计算处理等等. 用子程序编程有两大好处: 子程序可使程序划分成离散的逻辑组件,每个组件都比无子程序的整个程序容易调试及理解: 一个应用程序中的子程序,往往不必修改或只需稍作改动,便可以成为另一个程序的子程序. 每次调用子程序时,子程序中的所有语句都将被从第一条开始顺序执行,当执行到子程序尾部或者遇到"返回"命令时即返回到调用此子程序语句的下一条语句处. 子程

  • Spring表达式语言SpEL用法详解

    这篇文章主要介绍了spring表达式语言SpEL用法详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 (1)spring表达式语言是一个支持运行时查询和操作对象图得我强大表达式语言. (2)语言类似于EL:SpEL使用#{...}作为定界符.所有在大括号中的字符串均被认为是SpEL. (3)SpEL为bean的属性进行动态赋值提供了便利. (4)通过SpEL可以实现: 通过Bean的id对Bean进行引用 调用方法及引用对象的属性 计算表达式

  • R语言数据类型深入详解

    R语言用来存储数据的对象包括: 向量, 因子, 数组, 矩阵, 数据框, 时间序列(ts)以及列表 意义介绍 1. 向量(一维数据): 只能存放同一类型的数据 语法: c(data1, data2, ...),访问的时候下标从1开始(和Matlab相同);向量里面只能存放相同类型的数据. > x <- c(1,5,8,9,1,2,5) > x [1] 1 5 8 9 1 2 5 > y <- c(1,"zhao") # 这里面有integer和字符串, 整

  • R语言关联规则深入详解

    在用R语言做关联规则分析之前,我们先了解下关联规则的相关定义和解释. 关联规则的用途是从数据背后发现事物之间可能存在的关联或者联系,是无监督的机器学习方法,用于知识发现,而非预测. 关联规则挖掘过程主要包含两个阶段:第一阶段从资料集合中找出所有的高频项目组,第二阶段再由这些高频项目组中产生关联规则. 接下来,我们了解下关联规则的两个主要参数:支持度和置信度. 用简化的方式来理解这两个指标,支持度是两个关联物品同时出现的概率,而置信度是当一物品出现,则另一个物品也出现的概率. 假如有一条规则:牛肉

  • R语言“循环”知识点详解

    可能有一种情况,当你需要执行一段代码几次. 通常,顺序执行语句. 首先执行函数中的第一个语句,然后执行第二个语句,依此类推. 编程语言提供允许更复杂的执行路径的各种控制结构. 循环语句允许我们多次执行一个语句或一组语句,以下是大多数编程语言中循环语句的一般形式 - R编程语言提供以下种类的循环来处理循环需求. 单击以下链接以检查其详细信息. Sr.No. 循环类型和描述 1 repeat循环 多次执行一系列语句,并简化管理循环变量的代码. 2 while循环 在给定条件为真时,重复语句或语句组.

  • C语言字符串数组详解

    C语言字符串数组 字符串是连续的字符序列,最后以空字符'\0'作为终止符.一个字符串的长度指所有字符的数量,但不包括终止符.在 C 语言中,没有字符串类型,自然也就没有运算符以字符串为操作数. 字符串被存储在元素类型为 char 或宽字符类型数组中(宽字符类型指 wchar_t.char16_t 或 char32_t).宽字符组成的字符串也称为宽字符串(wide string). C 标准库提供了大量的函数,它们可以对字符串进行基本操作,例如字符串的比较.复制和连接等.在这些传统的字符串函数以外

  • C语言lseek()函数详解

     头文件: #include <sys/types.h> #include <unistd.h> 函数原型: off_t lseek(int fd, off_t offset, int whence);//打开一个文件的下一次读写的开始位置 参数: fd 表示要操作的文件描述符 offset是相对于whence(基准)的偏移量 whence 可以是SEEK_SET(文件指针开始),SEEK_CUR(文件指针当前位置) ,SEEK_END为文件指针尾 返回值: 文件读写指针距文件开头

  • 关于C语言qsort函数详解

    目录 C语言qsort函数详解 一.qsort函数是什么 二.使用qsort排序-以升序为例 1.整形数组排序 2.字符数组排序 3.字符指针数组排序 4.结构体数组排序 5.浮点型数组排序 三.使用冒泡排序思想模拟实现qsort函数 1.什么是冒泡排序 2.冒泡排序代码 3. 使用冒泡排序思想模拟实现qsort函数 C语言qsort函数详解 一.qsort函数是什么 我们可以使用  搜索库函数网址或者MSDN软件进行查找. qsort()函数:快速排序的函数  -引用stdlib.h头文件 参

  • Go语言--切片(Slice)详解

    目录 一.定义切片 1.声明一个未指定大小的数组来定义切片 2.使用make()函数来创建切片 二.切片是可索引的 1.len() 和 cap() 函数 三.切片截取 四.增加切片的容量 说明: Go 语言切片是对数组的抽象. Go 数组的长度不可改变,在特定场景中这样的集合就不太适用,Go中提供了一种灵活,功能强悍的内置类型切片("动态数组"),与数组相比切片的长度是不固定的,可以追加元素,在追加时可能使切片的容量增大. 一.定义切片 注意:切片不需要说明长度 1.声明一个未指定大小

随机推荐