数据结构-C语言代码 day7-递归的应用

简单来说，就是一个函数直接或间接调用自身的一种方法。通常递归可以将一个复杂的大型问题层层转化为一个与原问题相似的规模较小的问题来求解。它的核心思想是把大事化小。

(1)、递

将问题分解为若干个规模较小并与原问题形式相同的子问题，这些问题可以用相同的方法来解决。

(2)、归

当问题不断缩小规模的时候，一定有一个明确的结束递归的临界点，一旦达到这个临界点就从该点一路返回，最终到原点，问题得以解决！

(1)、递归出口：即存在限制条件当满足这个条件时，递归不再继续。

(2)、问题规模不断缩小：即每次调用完递归后越来越接近这个限制条件。 

#include

int addto(int n)
{
	if(n<=0)
	return 0;

	else
	return addto(n-1)+n;
}

void addtoTest()
{
	int n;
	printf("rn--test starts!--rn");

	n=5;
	printf("nAdd from 0 to %d to get %dn",n,addto(n));
	
	n=1;
	printf("Add from 0 to %d to get %dn",n,addto(n));
	
	n=-2;
	printf("Add from 0 to %d to get %dn",n,addto(n));
	
	printf("rn--end of test!--rn");
}

int main()
{
	addtoTest();
}

--test starts!--

Add from 0 to 5 to get 15
Add from 0 to 1 to get 1
Add from 0 to -2 to get 0

--end of test!--

(1)、 汉诺塔打印步数 O()

原理：
1.将n-1个碟子从A杆经C杆移动到B杆
2.将A杆上的第n个碟子移动到C杆
3.将n-1个碟子从B杆经A杆移动到C杆

代码实现 

#include
int Hanio_twice(int n)
{
	if(1 == n)
		return 1;
	else
		return 2 * Hanio_twice(n - 1) + 1;
}
int main()
{
	int n = 0;	
	scanf("%d", &n);//塔数
	int ret = Hanio_twice(n);
	printf("完成%d层的汉诺塔需要%d步n", n, ret);
	return 0;
}

(2)、 汉诺塔打印步骤 

原理：封装1个函数Hanio(n, ‘A’, ‘B’, ‘C’)。
其中n是塔数；A、B、C，3个字符为抽象成的3个柱子。
如果只有1层那么输出A；
否则就有2种情况，其1是将n-1个碟子从A经C到B。其2是将n-1个碟子从B经A到C

代码实现 

#include
void Hanio_Step(int n, char A, char B, char C)
{
	if (1 == n)
		printf("%c->%cn", A, C);
	else if(n <= 0)
	    return;
	else
	{
		Hanio_Step(n-1, A, C, B);
		printf("%c->%cn", A, C);
		Hanio_Step(n-1, B, A, C);
	}
}
int Hanio_twice(int n)
{
	if(1 == n)
		return 1;
	else
		return 2 * Hanio_twice(n - 1) + 1;
}
void Hanio_Test()
{
	printf("rn--begin!--rn");
	
	printf("n2 platesrn");
	printf("完成要%d步n",Hanio_twice(2));
	Hanio_Step(2, 'A', 'B', 'C');
	
	printf("nnextn");
	
	printf("n3 platesrn");
	printf("完成要%d步n",Hanio_twice(3));
	Hanio_Step(3, 'A', 'B', 'C');
	
	printf("rn--end!--rn");
}
int main()
{
	Hanio_Test();
}

测试结果

--begin!--

2 plates
完成要3步
A->B
A->C
B->C

next

3 plates
完成要7步
A->C
A->B
C->B
A->C
B->A
B->C
A->C

--end!--