递归与迭代_如何判断递归和迭代[通俗易懂]

作者介绍：友友们好我是沐曦希，可以叫我小沐💕
作者主页：沐曦希的个人博客主页.🎉
作者的gitee：https://gitee.com/muxi-c-language
C语言系列文章：
🎈 1. 函数零基础使用大全，助你了解函数（二）
🎈2. 函数零基础使用大全，助你了解函数（一）
🎉小沐和友友们一样喜欢编辑，天天敲代码🤭，沉迷学习，日渐消瘦。很荣幸能向大家分享我的所学，和大家一起进步，成为合格的卷王。✨如果文章有错误，欢迎在评论区✏️指正。那么开始今天的学习吧！😘

1.函数递归

编程语言中，函数Func(Type a,……)直接或间接调用函数本身，则该函数称为递归函数。递归函数不能定义为内联函数。
在数学上，关于递归函数的定义如下：对于某一函数f(x)，其定义域是集合A，那么若对于A集合中的某一个值X0，其函数值f(x0)由f(f(x0))决定，那么就称f(x)为递归函数。

1.1.函数递归的定义和条件

一种计算过程，如果其中每一步都要用到前一步或前几步的结果，称为递归的。用递归过程定义的函数，称为递归函数。
程序调用自身的编程技巧称为递归（ recursion）。
递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。
递归策略：
只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。即递归的主要思想：大化小。

当然递归是有两个必要条件的，只有满足这两个条件递归才能正常运行起来。

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

1.2.练习一

接受一个整型值（无符号），按照顺序打印它的每一位。

#include<stdio.h>
int print(int n)
{ 
   
	if (n > 9)//递归的限制条件
	{ 
   
		print(n / 10);//调整变量，使变量逼近限制条件
	}
	printf("%d ", n % 10);
}
int main()
{ 
   
	int n = 0;
	scanf("%d", &n);
	int sum = print(n);
	return 0;
}

1.3练习二

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

#include<stdio.h>
int strlen(char* p)
{ 
   
	if (*p != '\0')
	{ 
   
		return 1 + strlen(p + 1);
	}
	else
		return 0;
}
int main()
{ 
   
	char* p = "abcdef";
	int len = strlen(p);
	printf("%d\n", len);
	return 0;
}

2.递归与迭代

2.1.练习一

求n的阶乘。（不考虑溢出）

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

2.2.练习二

求第n个斐波那契数。（不考虑溢出）

#include<stdio.h>
int Fib(n)
{ 
   
	if (n > 2)
	{ 
   
		return Fib(n - 1) + Fib(n - 2);
	}
	else
		return 1;
}
int main()
{ 
   
	int n = 0;
	scanf("%d", &n);
	int sum = Fib(n);
	printf("%d", sum);
	return 0;
}

但是我们发现有问题；
在使用fib 这个函数的时候如果我们要计算第50个斐波那契数字的时候特别耗费时间。
使用factorial 函数求10000的阶乘（不考虑结果的正确性），程序会崩溃。
这是因为：
我们发现fib 函数在调用的过程中很多计算其实在一直重复。
如果我们把代码修改一下：

#include<stdio.h>
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 sum = Fib(n);
	printf("%d\n", sum);
	printf("count=%d", count);
	return 0;
}

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. 当一个问题相当复杂，难以用迭代实现时，此时递归实现的简洁性便可以补偿它所带来的运行时开 销。

3.写在最后

那么今天的学习就到这里了。友友们觉得不错的可以给个关注，点赞或者收藏哦！😘感谢各位友友们的支持。以下的代码希望各位大佬们自行检验哦，毕竟亲手操作让记忆更加深刻。

你的❤️点赞是我创作的动力的源泉
你的✨收藏是我奋斗的方向
你的🙌关注是对我最大的支持
你的✏️评论是我前进的明灯
创作不易，希望大佬你支持一下小沐吧😘

下一期见了！

今天的文章递归与迭代_如何判断递归和迭代[通俗易懂]分享到此就结束了，感谢您的阅读。