[学C日记]---递归

递归：自己调用自己，大事化小

必要条件：1.有限制条件，当满足限制条件时，递归便不继续
                  2.每次递归调用之后越来越接近这个限制条件
                  3.递归层次不能太深，太深容易栈溢出，每次递归调用都要给函数分栈区，次数过多容易空间不足

1.一串数字挨个输出

画图理解

void print(unsigned int n)
{
	if (n > 9)
	{
		print(n / 10);
	}
	printf("%d ", n%10);
}
int main()
{
	unsigned int num = 0;
	scanf("%d", &num);
	print(num);//print函数可以打印参数部分数字每一位
	return 0;
}

2.模拟实现一个strlen函数

int my_strlen(char* str)
{
	if (*str != '\0')
		return 1 + my_strlen(str + 1);//不能写str++，srt++先用后加
	else
		return 0;
}
int main()
{
	char arr[] = "bit";
	printf("%d、n", my_strlen(arr));
	return 0;
}

3.求n的阶乘1

int factorial(int n)
{
	if (n > 1)
		return n* factorial(n - 1);
	else
		return 1;
}
int main()
{
	int n = 0;
	scanf("%d", &n);
	printf("%d", factorial(n));
	return 0;
}

4.求第n个斐波那契数列

a.递归：次数多的时候，效率太低

int Fib(n)
{
	if (n > 2)
		return Fib(n - 1) + Fib(n - 2);
	else
		return 1;
}
int main()
{
	int n = 0;
	scanf("%d", &n);
	printf("%d", Fib(n));
	return 0;
}
int count = 0;

b.循环

int Fib(int n)
{
	int i = 0;
	int a = 1;
	int b = 1;
	int c = 1;
	for (i = 3; i <= n; i++)
	{
		c = a + b;
		a = b;
		b = c;
	}
	return c;
}
int main()
{
	int n = 0;
	scanf("%d", &n);
	printf("%d", Fib(n));
	return 0;