数据结构--栈应用----递归

文章目录

• 1.递归的定义
• 2.迭代和递归的区别
• 3.斐波那契数列的实现

1.递归的定义

递归函数：我们通常把一个直接调用自己或通过一系列的调用语句间接地调用自己的函数叫作递归函数。
使用规范：每个递归定义必须有一个条件，但条件满足时不再进行，即不再调用自己而是返回值退出。

2.迭代和递归的区别

(1)、迭代 使用的是循环结构，而 递归 使用的是分支结构。
(2)、递归 能使程序结构更清晰、更简洁、更容易让人理解，从而减少读懂代码的时间。但是大量的进行递归调用会建立函数副本，会消耗大量的时间和内存。迭代 则不需要反复调用函数和占用额外的内存。

• 那么 递归 和 栈 有什么联系呢？
  我们都知道栈的原理是 ：先进后出，后进先出。
  而递归是：先调用的函数最后得出答案，最后调用的函数先得出答案。
  这和栈的原理就非常的契合。

3.斐波那契数列的实现

什么是斐波那契数列？先看一组数：
0 - 1 - 1 - 2 - 3 - 5 - 8 - 13 - 21 - 34 - 55 - 89 - 144 ······
这组数有什么特点呢？
从第三个数开始，每个数都是前两个数的和。

那我们要如何实现这个程序呢？
先用最常规的方法来实现：

#include
using std::cout;

int main()
{
	int i;
	int arr[40];
	arr[0] = 0;
	arr[1] = 1;
	cout << arr[0] << '\t';
	cout << ar[1] << 't';
	for(i = 2; i < 40; i++)
	{
		arr[i] = arr[i -1] + arr[i - 2];//加上它前面的两个数
		cout << arr[i];//输出每个数
	}
	return 0;
}

结果：

用递归 的方法：

#include
using std::cout;

int Fbi(int a)
{
	if(a < 2)
		return a == 0 ? 0 : 1;
	else
		return Fbi(a - 1) + Fbi(a - 2);//递归的调用 
}

int main()
{
	int i;
	for(i = 0; i < 40; i++)
	{
		cout << Fbi(i) << '\t';
	}
	return 0;
}

输出结果和上面一样。这样看起来是不是很简洁呢。

关于这个问题就分享到这了，有帮助的话给个赞呗！