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

目录
  • 什么是递归？
  • 递归的两个必要条件
  • 递归实例
    • 实例1（按照顺序打印一个数的整形值）
    • 画图讲解
    • 完整代码
    • 实例2 （使用函数在不创建变量的情况下求字符串长度）
    • 画图讲解
    • 程序运行结果
    • 完整代码
  • 递归与迭代
    • 实例1 （求n的阶乘）
      • 方法一（使用递归）
      • 方法二（使用迭代）
    • 实例2 （求解斐波那契数列）
      • 方法一 （递归求解）
      • 方法二（迭代求解）
  • 总结

什么是递归？

递归（recursion）：程序调用自身的一种编程技巧。

如何理解函数递归：

1.从调用自身层面：函数递归就是函数自己调用自己。

2.从编程技巧层面：一种方法（把一个大型复杂的程序转换为一个类似的小型简单的程序），这种方法的主要思想就是把大事化小。

递归的两个必要条件

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

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

递归实例

实例1（按照顺序打印一个数的整形值）

参考代码（可以先去尝试是否可以解决问题）

画图讲解

注意：在每次打印后都有一个空格。

程序运行结果

完整代码

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

实例2 （使用函数在不创建变量的情况下求字符串长度）

参考代码

画图讲解

程序运行结果

完整代码

#include &lt;stdio.h&gt;int Strlen(const char* str){if (*str == '\0')return 0;elsereturn 1 + Strlen(str + 1);}int main(){char* p = "abcd";int len = Strlen(p);printf("%d\n", len);return 0;}

递归与迭代

迭代是重复反馈过程的活动，其目的通常是为了逼近所需目标或结果。 每一次对过程的重复称为一次“迭代”，而每一次迭代得到的结果会作为下一次迭代的初始值。 目前对于c语言来说，迭代可以简单认为是循环结构。

对于递归与迭代，我们同样通过两个实例来理解：

实例1 （求n的阶乘）

方法一（使用递归）

参考代码

通过数学方法讲解

完整代码 

#include <stdio.h>
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;
}

方法二（使用迭代）

完整代码

#include <stdio.h>
int main()
{
	int n = 0;
	scanf("%d", &n);
	int i = 0;
	int ret = 1;
	for (i = 1; i <= n; i++)
	{
		ret *= i;
	}
	printf("%d\n", ret);
	return 0;
}

运行结果

实例2 （求解斐波那契数列）

斐波那契数列：指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波纳契数列以如下被以递归的方法定义：F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n>=2，n∈N*）

方法一 （递归求解）

参考代码

通过数学方法求解 

运行结果 

完整代码 

#include <stdio.h>
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);
	return 0;
}

注意：当求得的数字较大时，使用递归的方法计算机所要计算的量是相当大的，因为每次计算一个第n项时都需要计算第n-1项和第n-2项 ，这里我们通过求解第40项来观察fib(3)的计算次数来观察。

运行结果

计算第40项时已经计算第3项已经有三千多万次，那么如果计算第一百项，一千项...时程序就会崩溃...这是我们就要考虑使用迭代的方法进行求解。

方法二（迭代求解）

参考代码 （主函数不变）

画图讲解 

完整代码 

#include <stdio.h>
int fib(int n)
{
	int a = 1;
	int b = 1;
	int c = 1;
	while (n > 2)
	{
		c = a + b;
		a = b;
		b = c;
		n--;
	}
	return c;
}
int main()
{
	int n = 0;
	scanf("%d", &n);
	int ret = fib(n);
	printf("%d\n", ret);
	return 0;
}

运行结果 

这里我们可以看出递归和迭代的运行结果是一样的，但是迭代的运行速度要更快。

这时候我们会想：

为什么有时候用递归简便，而有时候用迭代简便呢？

注意：

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

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

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

总结

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

赞 (0)

相关推荐

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

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

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

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

  • C语言的递归函数详解

    C语言的递归函数详解

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

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

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

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

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

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

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

  • 一篇文章带你入门C语言:函数

    一篇文章带你入门C语言:函数

    目录 函数 定义 库函数 定义 介绍 Example 1 strcpy Example 2 memset 自定义函数 Example 1 Example 2 两数交换 链式访问 Example 1 函数声明 函数递归 Example 1 Example 2 函数迭代 Example 3 Example 4 总结 函数 定义 程序里的函数又被叫做子程序,他作为一个大型程序的部分代码,有一或多个语句项组成.函数负责完成某项特定任务,提供了对过程的封装和对细节的隐藏,这样的代码通常会被集成为软件库.

  • 一篇文章带你了解C语言函数的可重入性

    目录 一.不可重入函数. 二.可重入函数. 三.如何写出可重入的函数 四.函数的可重入性和线程安全的关系 五.malloc和printf为什么不可重入 总结 一.不可重入函数. 在函数中如果我们使用静态变量了,导致产生中断调用别的函数的 过程中可能还会调用这个函数,于是原来的 静态变量被在这里改变了,然后返回主体函数,用着的那个静态变量就被改变了,导致错误.这类函数我们称为不可重入函数. 在 嵌入式系统的设计中,经常会出现多个任务调用同一个函数的情况.如果这个函数不幸被设计成为不可重入的函数的话

  • 一篇文章带你了解C语言的一些重要字符串与内存函数

    目录 一.字符串函数 1. 求字符串长度的strlen 2.比较字符串大小的strcmp 3.复制字符串的strcpy 4.追加字符串的strcat 5.查找字符串函数的strstr 二.内存函数 1.复制 memcpy,memmove 2.比较 memcmp 总结 一.字符串函数 1. 求字符串长度的strlen size_t strlen ( const char * str ); 字符串以 '\0' 作为结束标志,strlen函数返回的是在字符串中 '\0' 前面出现的字符个数(不包含 '

  • 一篇文章带你了解C语言文件操作中的几个函数

    一篇文章带你了解C语言文件操作中的几个函数

    目录 总结 fopen:有两个参数,第一个是要被打开或者被创建的文件名,第二个是以什么方式打开.这两个参数要分别用双引号括起来 打开文件和关闭文件的基本流程,关闭文件之后要置空 fwrite:有四个参数,第一个是指向要被写入的数据的指针,这里是a的地址:第二个参数是被写入项的大小,单位是字节,这里是a的大小:第三个参数是要被写入的项的个数,这里是1,意思是写入一个a:最后一项是FILE结构的指针,这里是pf.这四个参数不需要双引号. 文件指针:. 每个被使用的文件都在内存中开辟了一个相应的文件信

  • 一篇文章带你入门C语言:操作符

    一篇文章带你入门C语言:操作符

    目录 操作符 分类 算术操作符 移位操作符 整数存储规则 左右移位规则 赋值操作符 单目操作符 取地址操作符& 解引用操作符* 类型长度操作符sizeof 按位取反操作符~ ++ -- 操作符 强制类型转换操作符(type) 关系操作符= 逻辑操作符 短路运算 条件操作符 逗号表达式 下标引用.函数调用和结构成员 下标引用操作符[] 函数调用操作符() 结构成员操作符. -> 结构体定义 结构体使用 结构体地址 表达式求值 隐式类型转换 整型提升 如何整型提升 有符号数 无符号数 算术转换

  • 一篇文章带你了解C语言:入门基础(2)

    一篇文章带你了解C语言:入门基础(2)

    目录 操作符 算术操作符 移位操作符 位操作符 单目操作符 逻辑反操作! 操作符++,-- 逻辑操作符 条件操作符 逗号表达式 常见关键字 typedef extern static 修饰局部变量 修饰全局变量和函数 其它 #define定义常量和宏 定义常量 定义宏 指针 内存单元 指针变量 &取地址操作符,*解引用操作符 类型所占空间 结构体 定义结构体 使用结构体变量 总结 本节将结束对初识C语言的概述,只追求大概,不求精细. 本节包括的内容有操作符,常见关键字,#define定义常量和宏

  • 一篇文章带你了解C语言--数据的储存

    一篇文章带你了解C语言--数据的储存

    目录 前言 数据类型介绍 类型的基本归类 整形在内存中的存储 原码.反码.补码 大小端介绍 浮点型在内存中的存储 前言 前面我们学习了C语言的一些基本知识和基础的语法,想必大家对C语言都有了自己的认识. 当然只是学习这些知识还是不够的,我们需要进行更加深入的学习. 从本章开始,我们将进行C语言进阶阶段的学习,所以难度会有所增加. 数据类型介绍 前面我们已经学习了基本的内置类型: char //字符数据类型 short //短整型 int //整形 long //长整型 long long //更

  • 一篇文章带你了解C语言浮点数之间的比较规则

    一篇文章带你了解C语言浮点数之间的比较规则

    目录 你认为这段代码输出什么? 为什么不等于呢? 应该怎么解决? 那么怎么判断两个浮点数 f1 和 f2 相等呢. 伪代码 可以简化为 >> 怎么判断浮点数等于0? 还有一个问题 总结 你认为这段代码输出什么? int main() { float f1 = 1.1; float f2 = 2.2; if (f2 - 1.1 == f1) printf("等于"); else printf("不等于"); return 0; } 答案是不等于. 为什么不

  • 一篇文章带你了解C语言:入门基础

    一篇文章带你了解C语言:入门基础

    目录 C语言本身特点 数据类型 常量变量 变量分类 使用小建议 生命周期作用域 常量分类及其特点 字符串+转义字符+注释 字符串 转义字符 两种注释 选择循环语句 函数 数组 总结 闲话少说,先上思维导图. 如图所示,现在还是初识C语言的第一部分,本次只介绍了C语言本身特点,数据类型,常量变量,字符串转义字符注释,选择循环语句,函数,数组. 接下来请和我一起粗略地探讨其中内涵所在. C语言本身特点 这是C语言的定义: C语言是一门通用计算机编程语言,广泛应用于底层开发.C语言的设计目标是提供一种

随机推荐