对于这个题目，看看大家有什么效率更高的算法

本人比较注重本题的效率问题，如果谁有可以改进的方法，希望大家能互相学习一下。
题目：一个人能台阶，一次能登一级、二级或者三级台阶，假设有n级的台阶，请编写一个java的程序将各种的走法打印出来。

/*
* 总结：递归是解决一个问题的很好的方法，使问题的解决简单化，但是递归往往比较吃内存，当可以使用非递归的方式可以解决问题的时候，请
* 优先考虑非递归的方法；
* 以下的这个类只要添加一个main（）方法就可以运行了，不过由于是用递归的，台阶大的话（如果要用List返回结果集，最大只能是22，不改变java虚拟机的配置的情况下，即java虚拟机的默认的配置），会发生内存的溢出。还有就是关于程序时间性能的问题，谁有更好的方法，希望能互相交流一下
*/

import java.util.ArrayList;
import java.util.List;
public class WalkStep2 {
	private String excTime;
	//保存结果的List
	private List<List<Integer>> result=new ArrayList<List<Integer>>();
	public WalkStep2(int leftStep){
		long start=System.currentTimeMillis();
		this.walkStep(new Node(leftStep));
		long end=System.currentTimeMillis();
		this.setExcTime((end-start)+" 毫秒(ms)");
	}
	public WalkStep2(){
		this.walkStep(new Node(10));
	}
	public void add(List<Integer> aresult){
		result.add(aresult);
	}
	public long getResultCount() {
		
		return result.size();
	}
	public List<List<Integer>> getResult() {
		return result;
	}
	public void setResult(List<List<Integer>> result) {
		this.result = result;
	}
	public String getExcTime() {
		return excTime;
	}
	public void setExcTime(String excTime) {
		this.excTime = excTime;
	}
	//该类是一个节点的类
	class Node{
		private int leftStep;
		private Node parent;
		public Node(){}
		public Node(int leftStep){
			this.leftStep=leftStep;
		}
		public int getLeftStep() {
			return leftStep;
		}
		public void setLeftStep(int leftStep) {
			this.leftStep = leftStep;
		}
		public Node getParent() {
			return parent;
		}
		public void setParent(Node parent) {
			this.parent = parent;
		}
	}
	public void walkStep(Node aNode){
		//当剩余的台阶数为0的时候，就得到一种走法
		if(aNode.getLeftStep()==0){
			addKindOfResultToList(aNode);
		}
		walk(aNode);
	
	}
	//走台阶
	private void walk(Node aNode) {
		//只走一步的走法
		if(aNode.getLeftStep()-1>=0) aWalk(aNode,1);
		//只走两步的走法
		if(aNode.getLeftStep()-2>=0) aWalk(aNode,2);
		
		//只走三步的走法
		if(aNode.getLeftStep()-3>=0) aWalk(aNode,3);
	}
	//将结果加到List链表中
	private void addKindOfResultToList(Node aNode) {
		List<Integer> list=new ArrayList<Integer>();
		Node resultNode=aNode;
		while( resultNode.getParent()!=null){
			list.add(0,resultNode.getParent().getLeftStep()-resultNode.getLeftStep() );
		resultNode=resultNode.getParent();
		}
		this.result.add(list);
	}
	//走下一步的方法
	private void aWalk(Node aNode,int step) {
		Node stepNode=new Node(aNode.getLeftStep()-step);
		stepNode.setParent(aNode);
		 walkStep(stepNode);
	}
	
	
}

 

和彩票中奖率算法有得一拼。

递归就不一定吃内存，不递归就不一定省内存。  这个问题，我以前也想过，我最早的想法跟楼主是一样的。 但说这句话的人，很可能针对的不是 java 语言。我曾经做过某个东西，最早也用的是递归的方法，我本以为效率会很差，我就换成非递归的，结果是效率更差。 其实，如果要是做的多了的话，楼主应该能够感觉到，在用非递归做是时候，其实是在模仿递归的方式，变量也是。也就是说，非递归的方式在内存使用上，很可能是与递归是一样的。   但话又说回来，java 语言是跟其他语言不一样，因为 java 的内存释放是由虚似机来完成的，不像 其他语言，严格按照 什么 堆啊，栈啊。

谢谢你的回复，C、C++写的程序，当一个变量需要释放内存的时候，可以调用相应的方法，而对于java来说，内存的管理很大部分都是由GC来管理的，程序员很难去控制，总算调用JVM的gc（）方法，也不一定可以实现释放内存。所以只要一个对象的引用数不为0，一般都还存在内存中，假如递归的时候，所有的对象的引用都不为0，并且所有对象使用的内存和超过内存时，就会发生溢出。对于将递归转变为while等的循环，可以将一些变量的时间效用会大大减短。所以，我觉得对于java来说，递归比while等之类的循环要吃内存。

线性方程组而已，学点数学就成了

呵呵，线性方程组我都有考虑过，这在算出有多少种走法，效率确实是不错的，但是要枚举列出所用的走法，我用线性方程组目前还写不出比递归更好的方法，如果楼上的可以写出，能不能和我分享一下。谢谢

和引用没多大关系.
递归是一个栈嵌套的问题.由于嵌套所以无法回收栈调用链上的内存,所以就要求尽量减少单个栈循环所使用的内存.

而且,你的代码不能承受所谓22这个限制,不是因为递归这个过程,而是你要把所有的结果都保存.你把调用addKindOfResultToList方法的代码注释掉试一试.
因为Integer内部封装了是int,而int这些基本数据类型是存在栈中的,而默认情况下,jvm的栈并不是很大,所以很容易OutOfMemoryError: Java heap space

3阶斐波拉契数列

LZ去参加迅雷在广州的笔试了吧，结果如何？

母函数来解这来问题