计算思维实践之路(五)

          7月31日，晴。“递归方便耗内存，来去自在汉诺塔“。

      递归与非递归哪个省内存？  

        递归更消耗内存，来说说一下递归的“可怕”程度吧，递归无非是程序调用自身，程序运行时代码和数据存到内存中，即要分配内存空间，递归程序每调用一次自身，操作系统都要为其分配相应的内存资源，这一过程是通过“栈”这种数据结构实现的，可查阅操作系统和编译原理方面的书籍，通俗地说一下，栈就像一个水桶，只有上面有口，进栈和出栈都只能通过上面的口，从而有先进后出的数据结构特性，好啦，现在再回到递归那里，递归程序的一次调用好比向桶里放一块砖，依次向上堆，调用不结束就会一直向里放“砖”，如果调用次数稍多或内存较小的话很容易溢出，你会发现每次调用有很多东西是重复的，而循环则不同，循环得每次执行是对已有变量的更新，一般不会产生大量重复的东西，从而节省内存，但为什么还要用递归呢，这是因为一些算法用递归写起来比较方便，当然不少递归算法都有他的循环版本，在嵌入式开发中，禁止写递归。

          我本是西海龙王敖闰之子，唤名龙马三太子，驮师父往西天拜佛。我来做一道简单的。

     例9 非负数n的阶乘，按以下公式

           

#include<stdio.h>
int fn(int n) {
	if(n==0)//递归终止条件
		return 1;
	else//递归通式
		return n*fn(n-1);
}
int main() {
	int n;
	printf("请输入1个整数：");
	scanf("%d",&n);
	printf("%d!的阶乘是%d\n",n,fn(n));
	return 0;
}

                     有一个梵塔-汉诺塔，塔内有三个座A、B、C，A座上有诺干个盘子，盘子大小不等，大的在下，小的在上。把这些个盘子从A座移到C座，中间可以借用B座但每次只能允许移动一个盘子，并且在移动过程中，3个座上的盘子始终保持大盘在下，小盘在上。

             分析：描述简化---把A柱上的n个盘子移动到C柱，其中可以借用B柱。

                             

            1、任务分析                  

        2、算法构思

   任务1、把A上的n-1个盘子移动到B：  Hanoi (n-1，a,c,b);       // 操作结束为状态1     

   任务2、把A上的大盘子移动到C              move(a,c)　　　　

   任务3、把B上的n-1移动到A　　　　　Hanoi (n-1,b,c,a);　　//操作结束位状态2(和状态1相比只是规模变小)

     3、代码实现

   有了神仙姐姐的分析，俺沙悟净写一下代码：

#include <iostream>
using namespace std;
void Hanoi(int n, char src,char mid,char dest)
//将src座上的n个盘子，以mid座为中转，移动到dest座
{
	if( n == 1) {  //只需移动一个盘子
		cout << src << "->" << dest << endl; //直接将盘子从src移动到dest即可
		return ;   //递归终止
	}
	Hanoi(n-1,src,dest,mid); //先将n-1个盘子从src移动到mid
	cout << src << "->" << dest << endl; //再将一个盘子从src移动到dest
	Hanoi(n-1,mid,src,dest); //最后将n-1个盘子从mid移动到dest
	return ;
}
int main() {
	int n;
	cin >> n; //输入盘子数目
	Hanoi(n,'A','B','C');
	return 0;
}