package example.test; /** * 尾递归 * * 2018-01-11 * */ public class TailRetrate { public static void main(String[] args) { int r = factorialRecursion(5); System.err.println(r); r = factorialTailRecursion(5, 4); System.err.println(r); // F(10) 从0, 1开始 第10位是几? r = fibonacciTailRecursion(10, 1, 1); System.err.println(r); r = fibonacciRecursion(10); System.err.println(r); r = fibonacci(10); System.err.println(r); } /** * 阶乘计算 -- 递归解决 * * @param number * 当前阶乘需要计算的数值 * @return number! */ public static int factorialRecursion(final int number) { if (number == 1) return number; else return number * factorialRecursion(number - 1); } public static int factorialTailRecursion(final int factorial, final int number) { return number == 1 ? factorial : factorialTailRecursion(factorial * number, number - 1); } /** * 斐波那契数列(Fibonacci sequence) * * 普通实现 * * @param n * @return */ public static int fibonacciRecursion(int n) { // return n < 2 ? n : fibonacciRecursion(n - 1) + fibonacciRecursion(n - 2); if (n < 2) { // StackTraceElement[] ts = Thread.currentThread().getStackTrace(); // System.err.println(ts.length); return n; } return fibonacciRecursion(n - 1) + fibonacciRecursion(n - 2); } /** * 斐波那契数列(Fibonacci sequence) * * 尾递归实现 * * @param n * 第几位 * @param a * 从第一位开始 * @param b * 从第二位开始 * @return */ public static int fibonacciTailRecursion(int n, int a, int b) { if (n <= 2) { // StackTraceElement[] ts = Thread.currentThread().getStackTrace(); // System.err.println(ts.length); return b; } return fibonacciTailRecursion(n - 1, b, a + b); // return n <= 2 ? b : fibonacciTailRecursion(n - 1, b, a + b); } /** * 斐波那契数列(Fibonacci sequence) * * 非递归实现 * * @param n * @return */ public static int fibonacci(int n) { int first = 0; int second = 1; int fn = 0; for (int i = 2; i < n + 1; i++) { fn = first + second; first = second; second = fn; } return fn; } }