数据结构与算法-递归思想，及使用场景和优化思路

数据结构与算法-递归思想，及使用场景和优化思路

什么情况下可以使用递归 1，一个问题可以分解为几个子问题的解，我们可以通过分治思想将一个数据规模大的问题分解为很小的问题 2，这个问题和分解之后的子问题，求解思路一样。 3.一定有一个最后确认的答案，技递归的终止条件 斐波那契数列 1 1 2 3 5 8 求解公式 fn(n)=fn(n-1)+fn(n-2) package edu.rec; /** * 什么情况下可以使用递归 * 1，一个问题可以分解为几个子问题的解，我们可以通过分治思想将一个数据规模大的问题分解为很小的问题 * 2，这个问题和分解之后的子问题，求解思路一样。 * 3.一定有一个最后确认的答案，技递归的终止条件 *

* 递归优化 * 1，使用非递归：理论上所有的递归都可以转换为非递归 * 2，加入缓存：就是把中间结果存储下来，避免重复计算将算法复杂度降低O(n) * 3，尾递归：使用的过程中尽量把上一次结果传递到下一个结果 * * @author: LHT * @date: 2020/12/14 10:51 */ public class Fibonacci { public static void main(String[] args) { /*for (int i = 1; i < 45; i++) { long current = System.currentTimeMillis(); System.out.println(fab(i) + "----时间：" + (System.currentTimeMillis() - current) + "ms"); }*/ /** * 转for循环 */ /* for (int i = 1; i < 45; i++) { long current = System.currentTimeMillis(); System.out.println(noFib(i) + "----时间：" + (System.currentTimeMillis() - current) + "ms"); } for (int i = 1; i < 45; i++) { long current = System.currentTimeMillis(); data = new int[i + 1]; System.out.println(fib2(i) + "----时间：" + (System.currentTimeMillis() - current) + "ms"); }*/ /** * 尾递归 */ for (int i = 1; i < 45; i++) { long current = System.currentTimeMillis(); data = new int[i + 1]; System.out.println(i + "：#####" + tailFab(1, 1, i) + "----时间：" + (System.currentTimeMillis() - current) + "ms"); } } /** * 斐波那契数列 * * 1 1 2 3 5 8 * * 求解公式 * * fn(n)=fn(n-1)+fn(n-2) * 算法复杂度 O(n^2) * 有待优化 ↓↓↓↓↓↓↓↓↓ * * @param n * @return */ public static int fab(int n) { if (n <= 2) { return 1; } else { return fab(n - 1) + fab(n - 2); } } /** * 尾递归 * ↓↓↓↓↓↓↓↓↓ * * @param pre 上次结果 * @param res 上上次结果 * @param n 当前值 * @return */ public static int tailFab(int pre, int res, int n) { if (n <= 2) { return res; } else { return tailFab(res, pre + res, n - 1); } } /** * 时间复杂度 * O(n) * 空间复杂度 * T(n) * 2(n-1) * * @param n * @return */ public static int addN(int n) { if (n == 1) { return 1; } else { return 2 * addN(n - 1) + 1; } } /** * 优化方案一，将递归转换为数组 */ public static int noFib(int n) { if (n <= 2) { return 1; } int a = 1, b = 1, c = 0; for (int i = 3; i <= n; i++) { c = a + b; a = b; b = c; } return c; } /** * 方案2 * 加入缓存 */ static int data[]; public static int fib2(int n) { if (n <= 2) { return 1; } if (data[n] > 0) { return data[n]; } else { data[n - 1] = fib2(n - 1); data[n - 2] = fib2(n - 2); return data[n - 1] + data[n - 2]; } } /** * 阶乘 */ public static int fac(int n) { if (n <= 1) { return 1; } else { return n * fab(n - 1); } } /** * 尾递归 传递结果 * res就是每次保存的结果 */ public static int fac(int n, int res) { if (n <= 1) { return 1; } else { return n * fac(n - 1, res * n); } } }

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。