函数（2）递归

一、函数递归

什么是递归

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

递归常见出现的问题就是栈溢出。

递归的两个必要条件

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

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

e.g.1 打印一个数各个位上的数值

void print(int n)
{
	if (n > 9)
		print(n / 10);
	printf("%d ", n % 10);
}

int main()
{
	unsigned int num = 0;
	scanf("%d", &num);//1234
	print(num);
	return 0;
}

e.g.2.1 模拟实现strlen函数（用循环）

int my_strlen(char* str)
{
	int count = 0;
	while (*str != '\0')
	{
		count++;
		str++;
	}
	return count;
}

int main()
{
	char arr[] = "bit";
	printf("len=%d\n", my_strlen(arr));
}

e.g.2.2 模拟实现strlen函数（用递归）

int my_strlen(char* str)
{
	if (*str != '\0')
		return 1+my_strlen(str + 1);
	else
		return 0;
}

int main()
{
	char arr[] = "bit";
	printf("len=%d\n", my_strlen(arr));
}

e.g.3.1 输入一个数，求其阶乘的值（用循环）

int fac1(int n)
{
	int i = 0;
	int ret = 1;
	for (i = 1; i <= n; i++)
	{
		ret *= i;
	}
	return ret;
}

int main()
{
	int n = 0;
	scanf("%d", &n);
	printf("%d\n", fac1(n));
	return 0;
}

e.g.3.2 输入一个数，求其阶乘的值（用递归）

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

int main()
{
	int n = 0;
	scanf("%d", &n);
	printf("%d\n", fac2(n));
	return 0;
}

e.g.4.1  求第n个斐波那契数的值（用递归）

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);
	printf("%d\n", fib(n));
}

e.g.4.2 求第n个斐波那契数的值（用循环）

这里之所以不用递归是因为递归会重复计算n之前的所有斐波那契数，造成极大的算力的浪费，当n>44后效率极低。

int fib2(int n)
{
	int count = 0;
	int a = 1;
	int b = 1;
	int ret = 1;
	while (n>2)
	{
			n--;
			ret = a + b;
			a = b;
			b = ret;
	}
	return ret;
}

int main()
{
	int n = 0;
	scanf("%d", &n);
	printf("%d\n", fib2(n));
}