黑马程序员技术交流社区
标题:
递归的效率问题
[打印本页]
作者:
段玉超
时间:
2012-3-4 01:26
标题:
递归的效率问题
本帖最后由 段玉超 于 2012-3-4 12:54 编辑
汉诺塔问题 是典型的递归问题 ,通过递归算法解决非常的直观 ,而且使代码开起来十分的简介: 以下是根据用户输入塔的层数,程序输出 移动步骤的算法。
import java.util.Scanner;
public class TowersOfHanoi
{
public static void main(String[] args)
{
System.out.println("汉诺塔问题 ,请输入汉诺塔的用数字表示的层数,我们将告诉你如何做");
Scanner input = new Scanner(System.in);
int n = input.nextInt();
moveDisks(n,'A','B','C');
}
private static void moveDisks(int n,char fromTower,char toTower,char auxTower){
if(n==1){
System.out.println("将盘子从"+fromTower+"移动到"+toTower);
} else {
moveDisks(n-1,fromTower,auxTower,toTower);
System.out.println("将盘子从"+fromTower+"移动到"+toTower);
moveDisks(n-1,auxTower,toTower,fromTower);
}
}
}
复制代码
但是递归是否意味着高效呢?递归的时间复杂度和空间复杂度如何衡量? 一个函数递归输出10000边 ”我爱××××××××××××××××××ד 和使用循环输出一千遍 同样的字符串,他们的时间复杂度与空间复杂度是一样的么?效率是一样的么?求解!
作者:
段玉超
时间:
2012-3-4 02:14
悲剧了 难道 这里面有敏感词?
欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)
黑马程序员IT技术论坛 X3.2