ઇଓ 欢迎来阅读子豪的博客（Java语法篇）
☾ ⋆有什么宝贵的意见或建议可以在留言区留言
ღღ欢迎 素质三连 点赞 关注 收藏
❣ฅ码云仓库：补集王子 (YZH_skr) - Gitee.com
生活中的递归
从前有坐山，山上有座庙，庙里有个老和尚给小和尚将故事，讲的就是： "从前有座山，山上有座庙，庙里有个老和尚给小和尚讲故事，讲的就是： "从前有座山，山上有座庙..." "从前有座山……"
递归要满足以下条件
1、方法内部，在执行过程中自己调用自己，每次执行到一部分的时候去执行另外一个
2、递归出口，要有趋近于终止的条件（归的起始条件）
方法是在栈上开辟，栈是有大小的，递归函数也要压栈，执行完了出栈，超出了栈大小会报栈溢出错，所以递归必须要设置尽头
递归相当于数学上的 "数学归纳法", 有一个起始条件, 然后有一个递推公式
递归 = 递+归
递归 = 递（算函数值）+归（返回准确值）
代码示例: 递归求 N 的阶乘
public static void main(String[] args) { int n = 5; int ret = factor(n); System.out.println("ret = " + ret); } public static int factor(int n) { if (n == 1) { return 1; } return n * factor(n - 1); // factor 调用函数自身 } // 执行结果 ret = 120
代码示例 求斐波那契数列的第 N 项
public static int fib(int n) { if (n == 1 || n == 2) { return 1; } return fib(n - 1) + fib(n - 2); }
当我们求 fib(40) 的时候发现, 程序执行速度极慢. 原因是进行了大量的重复运算
class Test { public static int count = 0; public static void main(String[] args) { System.out.println(fib(40)); System.out.println(count); } public static int fib(int n) { if (n == 1 || n == 2) { return 1; } if (n == 3) { count++; } return fib(n - 1) + fib(n - 2); } } // 执行结果 102334155 39088169 // fib(3) 重复执行了 3 千万次
可以使用循环的方式来求斐波那契数列问题, 避免出现冗余运算.
class Test { public static int count = 0; public static void main(String[] args) { System.out.println(fib(40)); System.out.println(count); } public static int fib(int n) { int last2 = 1; int last1 = 1; int cur = 0; for (int i = 3; i <= n; i++) { cur = last1 + last2; last2 = last1; last1 = cur; } return cur; } }
