递归四条基本法则：

《数据结构与算法分析-java语言描述》 P7

  1. <mark>基准情形</mark>。必须总要有某些基准情形，它无需递归就能解出。
  2. <mark>不断推进</mark>。对于那些需要递归求解的情形，每次递归调用都必须要使状况朝向一种基准情形推进。
  3. 设计法则。假设所有的递归调用都能运行。
  4. <mark>合成效益法则（compound interest rule）。在求解一个问题的同一实例时，切勿在不同的递归调用中取做重复性的工作</mark>。

用递归

减少运行时间

  1. 通过递归，缩小问题的范围。O（logN）

分析使用栈空间的量

像二叉查找树，的平均深度（栈空间的使用量）O(logN)，就没问题
（有待理解）

不用递归

  1. 递归调用之后，实际上没有必要知道存在的值
    比如：
    //(尾递归)
    <mark>尾递归可以通过将代码放到一个while循环中并用每个方法参数的一次赋值代替递归调用而被手工能消除。</mark> 
//(尾递归)
public static <T> void printList(Iterator<T> itr){
	if(!itr.hasNext()){
		return ;
	}
	System.out.println(itr.next());
	printList(itr);
}
  1. <mark>违反上面第四条法则</mark>

特别是： 在计算诸如“斐波那契数”之类简单数学函数的值得时候，用递归不是一个好注意。

例子如下：
https://blog.csdn.net/LawssssCat/article/details/103100980
大概的代码：↓↓↓

/** * 计算AVL树h高度时候，最小的节点数 * @param args */
	public static void main(String[] args) {
		int i = 50; 
		System.out.println(countHeight2(i));
		System.out.println(countHeight(i));
	}
	
	/** * O(logN*2^N) * 不适合用递归的例子 * @param h * @return */
	public static long countHeight(int h ) {
		switch(h) {
		case 0 :  return 1 ;
		case 1 : return 2 ; 
		default : return countHeight(h-1)+ countHeight(h-2) +1 ;
		} 
	}
	
	
	/** * O(n) * @param h * @return */
	public static long countHeight2(int h ) {
		switch(h) {
		case 0 :  return 1 ;
		case 1 : return 2 ; 
		default :
			long a0 = 1 ; 
			long a1 = 2 ;
			long result = 0 ; 
			for(int i=1 ; i<h ; i++) {
				result = a0 + a1 +1  ;
				a0 = a1 ; 
				a1 = result ;
			}
			return result ;
		}
	}

前辈们的心得：

《为什么你学不会递归？告别递归，谈谈我的经验》
https://blog.csdn.net/m0_37907797/article/details/102767860