菜鸟笔记
提升您的技术认知

函数的递归

函数递归

什么是递归?

程序调用自身的编程技巧称为递归。
递归的主要思考方式在与:把大事化小

练习1:

接受一个整型值(无符号),按照顺序打印它的每一位。 例如: 输入:1234,输出 1 2 3 4.

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

练习2:

编写函数不允许创建临时变量

#include<stdio.h>
#include<stdlib.h>
int Strlen(const char* str)
{
	if (*str == '\0')
		return 0;
	else
		return 1 + Strlen(str + 1);//这一定要给str+1,让它由a移向b
}
int main()
{
	char *p = "abcdef";
	int tmp = Strlen(p);
	printf("%d\n", tmp);
	system("pause");
	return 0;
}

递归与迭代:

练习3:

求n的阶乘(不考虑溢出)


int fact(int n)
{
	if (n <= 1)
		return 1;
	else
		return n*fact(n - 1);
}

练习4:

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

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

但是我们发现有问题:

  • 在使用fib这个函数的时候如果我们要计算第50个斐波那契数字的时候会特别耗时。
  • 使用 factorial 函数求10000的阶乘(不考虑结果的正确性),程序会崩溃。

为什么呢?

那我们应该如何改进呢?

在调试 fact 函数的时候,如果你的参数比较大,,那就会报错: `stack overflow(栈溢出)这样的信息。系统分配给程序的栈空间是有限的,但是 如果出现了死循环,或者(死递归),这样有可能导致一直开辟栈空间,最终栈空间耗尽的情况,这样的现象我们称为栈溢出。

那如何解决上述问题呢?

  1. 将递归改为非递归
  2. 使用static对象替代nonstatic局部对象。在递归函数设计中,可以使用static对象代替nonstatic局部对象(即栈对象),这不仅可以减少每次递归调用和返回时产生和释放nonstatic对象的开销,而且static对象还可以保存递归调用的中间的状态,并且可为各个调用层所访问。

那如何解决上述问题呢?

//求n的阶乘
int fact(int n)
{
	int result = 1;
	while (n > 1)
	{
		result *= n;
		n -= 1;
	}
	return result;
}
//求第n个斐波那契数
int fib(int n)
{
	int n1 = 1;
	int n2 = 1;
	int n3 = 0;
	if (n <= 2)
		return 1;
	for (int i = 3; i < n; i++)
	{
		n3 = n1 + n2;
		n1 = n2;
		n2 = n3;
	}
	return n3;
}

提示:

  1. 许多问题是以递归的形式进行解释的,这是因为它比非递归的形式更为清晰。
  2. 但是这些问题的迭代实现往往比递归实现效率更高,虽然代码的可读性稍微差些。
  3. 当一个问题相当复杂,难以用迭代实现时,此时递归实现的简洁性便可以补偿它所带来的运行时开销。