识别可转换为递归方法的方法
我一直在搜索以练习我的递归，但是我在codingBat和其他几个方面的练习问题已经用完了。如果你有更多的建议，欢迎评论！
我的问题是，您如何识别什么时候可以简单地将方法转换为递归方法，即使您必须或可以更改参数？
所需的递归方法的元素将是认为递归结束的所需的基本情况，以及循环或不循环的理由(这将恢复为大小写条件)。我是否遗漏了递归方法的其他重要方面？
下面是我找到的一个递归方法的例子(但还没有被递归解决)。它来自codingBat，我没有要求任何人更正我的代码。这只是我找到的一个可以转换的方法的例子。我会想办法的。
当答案进来时编辑。由于混淆而删除示例。编写递归方法时需要注意的要求：
- StackOverFlow误差
- 所有包含循环的方法都可以递归，但它可能不是实现的最佳选择。
- 对于正在解决的问题，递归方法应该是自然的。
回答 3
Stack Overflow用户
发布于 2015-06-16 11:08:21
基本上，递归可以模拟每个循环，因此您可以为几乎每个包含一个循环的方法创建一个递归方法--但是不能保证递归版本将完成(因为您的循环版本可能使用状态来缓存结果，而您的递归版本则不会)，甚至运行(因为您可能得到一个StackOverflowError --多么合适)。
编辑:注意，即使使用直接递归可能导致堆栈溢出，也有一种技术可以解决这个问题，即蹦床 (本文针对python，但也适用于Java8的lambdas)。
编辑2:还请注意，迭代和递归解决之间的关系是由图灵教堂-conjecture造成的。
Stack Overflow用户
发布于 2015-06-16 11:11:21
将循环转换为递归总是可能的(但不是相反的)：
// this is a general loop
for ( init(); loopCondition(); step() )
body();
// this is the general recursion of such a loop
function rec(recursionCondition, body, step) {
if(recursionCondition()) {
body();
step();
rec(recursionCondition, body, step);
}
}
// and don't forget to initialise at the calling level:
init();
rec(loopCondition, body, step);例如
for(int i = 0; i < length; ++i)
doStuffOn(i);
function doStuffRec(int i, int length) {
if(i < length) { // recursionCondition
doStuffOn(i); // body
int nextI = i + 1; // step
doStuffRec(nextI, length);
}
}
// calling level (initialisation of i)
doStuffRec(0, length);Stack Overflow用户
发布于 2015-06-16 11:25:01
基本上，您可以编写以递归或迭代方式循环的每个方法。你只需要一个条件来停止循环。
有时，一个方法比迭代更容易实现递归。但是需要注意的是运行时。
long fibonacci(long Parameter) {
if(Parameter <=1)
return 1;
else
return fibonacci(Parameter-1)+fibonacci(Parameter-2);
}现在试着为n=40找到这个，需要很长时间。为什么？因为运行时间的复杂性是指数级的。这意味着计算需要的时间是指数级的。
将其与iterativ实现进行比较：
long fibonacciIterativ(long Parameter) {
int a=1, b=1;
for(int i=1; i<Parameter;i++) {
a = a+b;
b = a-b;
}
return a;
}在这里，运行时复杂度是线性的，意味着运行时随输入线性增长。(IIRC甚至有一个公式的解决方案，所以运行时是O(1)，几乎是即时的)。
因此，在某些情况下，与迭代函数相比，递归函数编写起来更自然，有时相反。但是，通过使用递归函数，您必须小心运行时！
https://stackoverflow.com/questions/30865765
复制相似问题
腾讯云开发者
