做网站美工赚钱吗,英文网站建设口碑好,涉县手机网站建设,模板自助建站网站制作对于那些不知道递归是什么的人#xff08;并且像个笑声一样#xff09;#xff0c;请单击以下链接#xff1a;Google搜索#xff1a;递归#xff0c;然后单击“您的意思是……”项。 希望您终于弄清楚了递归是指其自身的任何内容#xff08;如果不是#xff0c;那么您可… 对于那些不知道递归是什么的人并且像个笑声一样请单击以下链接Google搜索递归然后单击“您的意思是……”项。 希望您终于弄清楚了递归是指其自身的任何内容如果不是那么您可能会永远浏览Google并试图找出递归是什么。 递归的一个相当常见的例子是斐波那契数。 斐波纳契数的模式是将前两个项与下一个项相加从一个和一个开始。 以下是斐波那契数的递归关系 F1 F2 1 Fn Fn-1 Fn-2 递归关系是原始函数引用自身的任何关系。 那么我们如何找到F5 F5 F4 F3 F5 [F3 F2] [F2 F1] F5 [F2 F1] 1 1 1 F5 1 1 1 1 1 F5 5 似乎需要很多工作 好吧对于计算机来说大多数时候都相当快。 稍后我将向您介绍动态编程因此当您要计算较大的斐波那契数时我们可以加快速度。 那么递归函数的所有部分是什么 首先什么是递归函数 递归函数是任何直接间接或间接调用自身的函数。 这是Java中的一个简单示例 public static void doIt()
{doIt();
} 当然这最终会导致堆栈溢出错误因此不建议您尝试使用此代码。 所有有用的递归函数都具有以下一般属性减少问题直到计算机可以轻松解决为止。 为此递归函数必须具有 定义了基本案例解决方案显而易见且无法进一步简化的案例 减少步骤简化给定问题的地方 递归调用自身基本上解决了更简单的情况 在上面的Fibonacci递归函数中您可以看到它一直在递归直到只加1。 这是因为在斐波那契数列中1是基本情况因此我们仅需将1加几次才能得到Fn。 从理论上讲所有递归函数都可以迭代编写并且所有迭代函数都可以递归编写。 但是在实践中您会发现根据情况的不同其中一种或两种理念会更好地发挥作用。 让我们递归地查看阶乘函数并将其与它的迭代亲戚进行比较。 阶乘N 1 * 2 * 3 * ... * N 基本上将1到N的所有整数相乘即可得到N的阶乘。 迭代实现您的代码将如下所示 public static int iterativeFactorial(int n)
{int answer 1;for (int i 1; i n; i){answer * i;}return answer;
} 我们还可以编写此函数的递归等效项F1 1 FN FN-1* N您能看到这如何产生与迭代阶乘相同的结果吗 这是递归计算阶乘的代码 public static int recursiveFactorial(int n)
{if (n 1){return 1;}else{return n * recursiveFactorial(n-1);}
} 那么就性能而言递归如何与此处的迭代解决方案相提并论 可悲的是答案很差。 此处的递归函数需要大量内存来存储方法堆栈并跟踪每个递归调用中的所有变量而迭代解决方案仅需跟踪当前状态。 那么为什么还要烦恼递归呢 因为很多时候正确使用递归其性能可能会超过迭代解决方案的性能并且递归函数也可能更易于编写有时。 动态编程 动态编程是递归的一种形式但是它是迭代实现的。 还记得我们上面的斐波那契计算机吗 F5 F2 F1 F2 F2 F1F5 3 * F2 2 * F1我们有这里有一些“过度计算”。 只需计算一次F2和一次F1。 在这种情况下计算这几个项并不需要太多的计算工作但是在某些情况下几乎不可能数百次重新计算解决方案。 因此我们无需重新计算而是将答案存储了下来。 public static int dynamicFibonacci(int n)
{int[] prevSolutions new int[n];if (n 1 || n 2){return 1;}prevSolutions[0] 1;prevSolutions[1] 1;for (int i 2; i prevSolutions.length; i){prevSolutions[i] prevSolutions[i-1] prevSolutions[i-2];}return prevSolutions[n-1];
} 因此再次取F5。 如果我们以递归的方式进行操作那么将有8次调用recursiveFibonacci。 但是这里我们只计算一次F1F2F3F4和F5。 减少3个电话获得的收益似乎并不多但是如果我们尝试计算F50怎么办 dynamicFibonacci仅会计算50个数字但递归Fibonacci可能会超过1000个当然我还没有计算所以我不知道它是否超过1000个。 关于动态编程的最后一点是它仅在有大量重叠的情况下才有用。 还记得recursiveFactorial函数吗 如果我们调用recursiveFactorial50和dynamicFactorial50则它们将花费大致相同的时间因为我们要进行相同数量的计算。 这是因为从来没有重叠。 这也是为什么排序算法不是通过动态编程实现的较差选择的原因如果您分析大多数排序算法则它们几乎没有重叠的解决方案因此对于动态编程来说是一个较差的选择。 这是有关递归和动态编程的一些问题 实现recursiveFactorial方法您以为我忘了把它放在那里 对于给定的递归关系编写一个递归方法将找到FN 这种递归关系在迭代方面意味着什么 为此问题写一个迭代的解决方案。 这种递归关系是否适合动态编程 为什么/为什么不呢 有比迭代或递归解决方案更好的方法来解决此问题吗 这是什么如果有 提示想想卡尔高斯 对于问题2-5请使用以下递归关系 F1 1 FN FN-1 N 答案来了…… 参考 Java编程论坛上 JCG合作伙伴的 递归 相关文章 Java Micro-Benchmarking如何编写正确的基准 首先记录异常的根本原因 编程反模式 您不想错过的十大Java书籍 Java日志混乱 做短但做对 翻译自: https://www.javacodegeeks.com/2011/12/java-recursion-basics.html
