函数递归以及趣味问题的解决

目录

函数递归

普通数字顺序打印

递归数字顺序打印

斐波那契数列问题

汉诺塔问题

---

函数递归

函数调用自身的行为就是递归。可以直接或间接的调用，本质是把复杂的问题转化为一个相似的，规模较小的问题。也就是我们常说的大事化小，小事化了，是一种把问题分而治之的思想。递归的一个最重要的价值就是可以减少代码量，确确实实能提高开发的效率，但它的缺点也是显而易见的，下面让我们用实例来讲解函数递归的优劣吧。

普通数字顺序打印

假设我们输入一个数,想按照顺序打印它的每一位.

比如输入:123

输出:1 2 3

我们先用迭代的方式来做，我们的基本思想是将输入的数123%10获得个位上的数字，打印，再把a/10的值赋给a。

代码如下

#include<stdio.h>

void print()
{
	int  a = 0;
	int  i = 0;
	scanf("%d", &a);
	do 
	{
		printf("%d ", a % 10);
		a = a / 10;
	} while (a !=0);

}


int  main()
{
	print();
	return  0;
}

输入：1234

但输出的结果却是：4 3 2 1

这显然不是我们想要的结果！

接下来我们修改一下函数

void print()
{
	int  a = 0;
	int  i = 0;
	int  arr[10] = { 0 };
	int  count = 0;
	scanf("%d", &a);
	do 
	{
		arr[count]=a % 10;
		a = a / 10;
		count++;
	} while (a !=0);
	for (i = 0;i < count;i++)
	{
		printf("%d ", arr[count-1-i]);
	}

}


int  main()
{
	print();
	return  0;
}

输入：1234

输出：1 2 3 4

结果符合预期，但是我们用了两个循环，新创建了一个数组，使得代码量大大增加，并且逻辑也变得复杂。

递归数字顺序打印

那有没有更好的解决办法呢，接下来我们就介绍数组的方法。

主要思路是拆分问题，我们不是要用函数打印1234吗？也就是说:

print(1234)  输出的结果是1 2 3 4  那我们拆分一下

拆成print（123）和4

再拆print（12）和3 4

print（1）和2 3 4

我们可以调整函数和printf的顺序来设置打印的顺序。

程序如下

void print(int x)
{
	if (x <= 9)
		printf("%d ", x);
	else
	{
		print(x / 10);
		printf("%d ", x % 10);
	}
}

int  main()
{
	int  a = 0;
	scanf("%d", &a);
	print(a);
	return  0;
}

递归过程的图解

 

代码非常紧凑，可以看出函数递归我们必须要有一个限制条件来限制递归的次数，并且每次调用递归都要更接近限制条件。代码中的x<=9就是递归的限制条件，调用递归函数时x/10使更加接近限制条件。

斐波那契数列问题

1 1 2 3 5 8 13 21 34 ...

这个数列从第3项开始，每一项都等于前两项之和。斐波那契数列可以帮助我们更好地了解递归的缺陷。

每一项等于前两项之和，也就是说Fibonacci（n）=Fibonacci（n-1）+Fibonacci（n-2）。

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

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

代码如图所示，但是当n达到一个较大的值，比如说50时，栈溢出了。这是为什么？

从代码中我们可以看到每进入一个函数就递归两次，这时调用函数的次数增加是几何倍数增加的，几乎想要使用2^n次函数，这是很可怕的。
这时候使用迭代，计算速度明显就提高了。

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

使用递归的时候还是要谨慎。

汉诺塔问题

相传在古印度圣庙中，有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上，有三根杆(编号A、B、C)，在A杆自下而上、由大到小按顺序放置64个金盘。游戏的目标：把A杆上的金盘全部移到C杆上，并仍保持原有顺序叠好。操作规则：每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下，小盘在上，操作过程中盘子可以置于A、B、C任一杆上。

 因为规则是大盘必须在下，我们要把A上的盘全部搬运至C，必须要做的就是把A最下面的一个盘保留，将上面的盘运至B，再把最大的盘搬运至C。

把A除了最下面的盘外的盘都搬运至B盘，与最初的问题是不是非常相似，就只是少搬运了最大的盘而已，那么我们就可以对问题进行拆分了。

比如说我们要搬运7个盘，想知道最少的搬运次数。搬七次不就等于搬两个六次加一次吗。

hanoi(n）=2*hanoi(n-1)+1;

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

知识分享到此结束，喜欢我的小伙伴，可以点赞、评论、加关注，我会努力更新的。