大话数据结构-4.8 栈的应用——递归 100- 高飞网

4.8 栈的应用——递归 100

2016-12-21 15:21:48.0

4.8.1 斐波那契数列实现

    斐波那契数列满足:

即当前元素的值,等于前两个元素的和。如果用循环来打印前40位的斐波那契数列:

void fbi_iterator(int len)
{
	int a=0,b=1;	
	printf("%d,",a);
	printf("%d,",b);
	for(int i=2;i<len;i++)
	{
		int tmp = b;
		b = a+b;
		a = tmp;
		printf("%d,",b);
	}
	printf("\n");
}

    用递归实现:

int main(void)
{
	for(int i=0;i<10;i++)
	{
		printf("%d,",fbi_recur(i));			
	}
	return 0;
}

int fbi_recur(int index)
{
	if(index<2)
	{
		return index==0?0:1;
	}
	return fbi_recur(index-1)+fbi_recur(index-2);
}

4.8.2 递归定义

    把一个直接调用自己或通过一系列的调用语句间接地调用自己的函数,称做递归函数。

    每个递归定义必须至少有一个条件,满足递归不再进行,即不再引用自身而是返回值退出。

    使用循环和递归的比较

迭代递归
循环结构选择结构

好处:使程序的结构更清晰、简洁、容易理解。

坏处:大量的递归调用会建立函数的副本,会的耗费大量的时间和内存。

    递归过程退回的顺序是它前行顺序的逆序。在退回过程中,可能要执行某些动作,包括恢复前行过程中存储起来的某些数据。这种存储某些数据,并在后面又在存储的逆序恢复这些数据,以提供之后使用的需求,用栈来实现很合适。