黑马程序员技术交流社区

标题: 递归问题 [打印本页]

---

作者: 段玉超    时间: 2012-3-4 13:19
标题: 递归问题
汉诺塔问题 是典型的递归问题 ，通过递归算法解决非常的直观 ，而且使代码开起来十分的简介： 以下是根据用户输入塔的层数，程序输出 移动步骤的算法。

1. import java.util.Scanner;
   
2. 
   
3. public class TowersOfHanoi
   
4. {
   
5.         public static void main(String[] args)
   
6.         {
   
7.                 System.out.println("汉诺塔问题 ，请输入汉诺塔的用数字表示的层数，我们将告诉你如何做");
   
8.                 Scanner input = new Scanner(System.in);
   
9.                 int n = input.nextInt();
   
10. 
    
11.                 moveDisks(n,'A','B','C');
    
12.         }
    
13. 
    
14.         private static void moveDisks(int n,char fromTower,char toTower,char auxTower){
    
15.                 if(n==1){
    
16.                         System.out.println("将盘子从"+fromTower+"移动到"+toTower);
    
17.                 } else {
    
18.                         moveDisks(n-1,fromTower,auxTower,toTower);
    
19.                         System.out.println("将盘子从"+fromTower+"移动到"+toTower);
    
20.                         moveDisks(n-1,auxTower,toTower,fromTower);
    
21.                 }
    
22.         }
    
23. }
    

复制代码

但是递归是否意味着高效呢？递归的时间复杂度和空间复杂度如何衡量？  一个函数递归输出10000边 ”我爱××××××××××××××××××ד 和使用循环输出一千遍 同样的字符串，他们的时间复杂度与空间复杂度是一样的么？效率是一样的么？求解！

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2