10.递归尾调用

递归转非递归算法
用栈来存取数据

public class Transformation {
    public static void main(String[] args) {
        log(10);
    }
    public static void log(int n) {
        Stack<Frame> stack = new Stack<>();
        while (n > 0) {
            stack.push(new Frame(n, n * stack.hashCode()));
            n--;
        }
        while (!stack.isEmpty()) {
            Frame frame = stack.pop();
            System.out.println(frame.v);
        }
    }
}
class Frame {
    int n;
    int v;
    Frame(int n, int v) {
        this.n = n;
        this.v = v;
    }
}

尾调用：
尾调用：一个函数的最后一个动作是调用函数
如果最后一个动作是调用自身，称为尾递归（Tail Recursion），是尾调用的特殊情况
**
一些编译器能对尾调用进行优化，以达到节省栈空间的目的

尾调用优化（Tail Call Optimization）
尾调用优化也叫作尾调用消除（Tail Call Elimination）
如果当前栈帧上的局部变量等内容不需要用了，当前栈帧经过适当的改变后可以直接当做被尾调用的函数的栈帧使用，然后程序可以jump到被尾调用的函数代码。
生成栈帧改变代码与jump的过程称作尾调用消除或尾调用优化
尾调用优化让位于尾位置的函数调用跟goto语句性能一样高

消除尾递归里的尾调用比消除一般的尾调用容易很多
比如Java虚拟机（JVM）会消除尾递归里的尾调用，但不会消除一般的尾调用（因为改变不了栈帧）
因此尾递归优化相对比较普遍，平时的递归代码可以考虑尽量使用尾递归的形式**

尾递归例子——阶乘

public static int fib(int n) {
        if (n <= 2) {
            return n;
        }
        return fib(n, 1);
    }
    public static int fib(int n, int result) {
        if (n <= 1) {
            return result;
        }
        return fib(n - 1, n * result);
    }

尾递归例子——斐波拉契数列

public static int fib1(int n) {
        return fib1(n, 1, 1);
    }
    public static int fib1(int n, int first, int second) {
        if (n <= 1) {
            return first;
        }
        return fib1(n - 1, second, first + second);
    }

10.递归 尾调用