问题描述 给定一个存有整形数的堆栈，你能使用的操作有，peek 获得堆栈顶部元素的值但不把元素弹出堆栈，pop 把堆栈顶部的元素出栈，push 压入一个堆栈，empty 判断堆栈是否为空，要求你只能使用这几种操作，同时在不分配新内存的情况下，将堆栈中的元素从大到小排列，假定堆栈中，元素由栈底到栈顶如下： stack: 1 3 5 4 2 排序后为： stack: 5 4 3 2 1
public class StackSorter { public Stack<Integer> sortByRecursion(Stack<Integer> s) { if (s.empty() == true) { return s; } int v = s.pop(); s = sortByRecursion(s); s = insert(s, v); return s; } private Stack<Integer> insert(Stack<Integer> s, int v) { if (s.empty() == true || v <= s.peek()) { s.push(v); return s; } int t = s.pop(); insert(s, v); s.push(t); return s; } }思路 写递归程序重要的四点是：输入参数、输出结果、函数的功能、终止条件。**递归本身就是完成一种功能的形式化描述。**递归的思维方式是将复杂的问题简单化。 第一个函数sortByRecursion(Stack<Integer> s)对栈中的元素进行排序，但是根据题目要求，不能分配新的内存，采用递归，将所有元素出栈，保存在调用堆栈上，当栈空时，这时栈里面的元素已经排好序了（没有任何元素），向栈中插入元素。 不要去解析程序执行的每一个步骤来理解递归，递归并不是算法，是一种思想。 第二个函数insert(Stack<Integer> s, int v)在排好序的栈中插入元素，也是采用递归，当栈空时或当插入元素小于等于栈顶元素的值时，将元素压入栈中，否则将栈顶元素弹出，将元素插入，在将刚才的元素压栈。 总结 递归程序没有想的那么难，只是我们总要从每一步去理解递归，我一开始也是如此，这让我很没有头绪。递归是一种思想，请好好理解这些话。
