递归定义

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

递归的两个必要条件

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

递归相关练习

例一、接受一个整型值（无符号），按顺序打印它的每一位。例如：输入 1234，输出 1 2 3 4

void print(int n)
{
	if (n > 9) {           //1234
		print(n / 10);     //123
	}
	printf("%d ", n % 10);
}
int main()
{
	unsigned int num;
	scanf("%d", &num);
	print(num);
	return 0;
}

在这里插入图片描述

递归调用过程演示：

在这里插入图片描述

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

（1）正常打印法----调用库函数 strlen

#include<stdio.h>
#include<string.h>
int main()
{
	char arr[] = "abcdef";
	printf("%d\n", strlen(arr));

	return 0;
}

在这里插入图片描述
但是注意，使用库函数时需引用头文件：

（2）模拟实现 strlen 函数求长度

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

int main()
{
	char arr[] = "abcdef";
	int len = my_strlen(arr);

	printf("%d\n", len);

	return 0;
}

在这里插入图片描述

调用过程：
在这里插入图片描述

例三、求 n 的阶乘（不考虑溢出问题）

（1）递归形式

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

int main()
{
	int num = 0;
	scanf("%d", &num);

	int ret = Fib(num);
	printf("%d\n", ret);

	return 0;
}

在这里插入图片描述
调用过程：

在这里插入图片描述

（2）非递归形式

int fic(int n)
{
	int i = 1;
	while (n > 1) {
		i *= n;
		n -= 1;
	}
	return i;
}

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

	return 0;
}

在这里插入图片描述

例四、求 n 个斐波那契数列（不考虑溢出问题）

1、1、2、3、5、8、13、21、34、……

第 n 个数字等于前两个数字之和

在这里插入图片描述

（1）递归调用

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

int main()
{
	int num = 0;
	scanf("%d", &num);

	int n = fib(num);
	printf("%d\n", n);
	return 0;
}

在这里插入图片描述

大家可以看到在求 n 的阶乘和第 n 个斐波那契数列都提示不考虑溢出问题，倘若调用次数十分大会导致程序崩溃

（2）非递归形式

分析斐波那契数字形式，1、1、2、3、5、8、13、21、34、……

从第 3 个数字开始，第 n 个数字等于第 n-1 个数与第 n-2 个数字之和

int fib(int n)
{
	int a = 1;
	int b = 1;
	int c = 1;

	while (n > 2) {
		c = a + b;
		a = b;
		b = c;
		n--;
	}
	return c;
}


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

	return 0;
}