0

除了典型的递归函数设计方法之外，还有哪些其他与语言无关的方法：

if (counter < 1) 
    return output;
else
   callSelf();

是否存在其他方法？每当查看示例时，我总是会看到上面代码的一个版本。

谢谢！:)

4

8 回答 8

6

差不多就是这样。

递归函数设计非常简单，就像“我可以返回一个值还是需要做进一步的处理？” 和“处理返回一个值，在传递它之前我该怎么做？”

尾递归只是编译器/解释器可以用来提高性能的一种优化方法。本质上，如果您的递归函数遵循严格的格式（递归调用之后没有任何反应，通常意味着递归调用总是与 配对return），则可以优化递归函数并将其重写为 for 循环。

于 2009-10-06T18:52:54.133 回答
5

你的问题到底是什么？只是尝试一些答案;-)

递归有很多种：

  • “标准”递归

    let rec sum = function
    | [] -> 0
    | x::x' -> x + sum x'

  • 尾递归

    let rec sum acc = function
    | [] -> acc
    | x::x' -> sum (x + acc) x'

  • 相互递归

     let rec f() = g()
 and g() = f()

  • 定点递归

    let factorial n = fix(fun rec n -> if n < 1 then 1 else n * rec (n - 1)) n

并且递归的应用列表非常丰富。在函数式编程中，任何迭代代码（for循环等）都是通过递归来表达的！

另一个很好的例子：

let rec sumTree = function
| End -> 0
| Node(val, right, left) = val + sumTree right + sumTree left

递归的主要“最佳实践”是确保您的终止条件在某个时刻得到满足，因此您通常会使用比初始调用“更小”的数据自调用函数（只是树的一部分）。其他一切都可能导致无休止的递归。

于 2009-10-06T18:59:21.950 回答
3

好吧，您需要有一些方法来知道何时停止递归。这就是你counter < 1的，对吗？我经常在列表中删除/添加项目，遍历树，并在递归时执行数学函数。最终，您需要知道何时停止递归以及何时停止递归，因此我看不到任何其他不能归结为counter < 1.

function ProcessNode(node)
  //Do stuff
  while (node.Next != null)
    ProcessNode(node.Next);

function ManipulateList(list)
  //Do stuff, adding and removing items based on logic
  if (testCondition)
    return;
  else
    ManipulateList(list);
于 2009-10-06T18:52:34.257 回答
1

有很多变化，例如：

foreach (child in parameter.GetChildren()) {
   callself(child)
}

或者

switch (param.length) {
   case 1: return param[0];
   case 2: return param[0] + param[1];
   default: return callself(param.FirstHalf()) + callself(param.LastHalf());
}

它们的共同点是把任务分解成更小的任务，然后用自己来解决更小的任务，直到它们小到可以通过微不足道的操作来解决。

于 2009-10-06T19:05:43.353 回答
1

在惰性编程语言中，您可以使用不定义端点的递归。结果可能是一个无限的数据结构，但只要你不尝试使用它就可以了。例如，在 Haskell 中定义整个斐波那契数列的常用方法是：

fibS = 1:1: zipWith (+) fibS (tail fibS)

这翻译成以下英语：斐波那契数列是 1，然后是 1，然后是数列，该数列是斐波那契数列和没有第一个元素的斐波那契数列的元素之和。

这听起来像是一个递归定义，而不是递归函数调用，但在 Haskell 中并没有什么大的区别——上面只是一个“空函数”（不带参数的函数）。

通常要使用它，您只需使用 fibS 的前 N ​​个元素。实际上，您可以使用所有这些（例如全部打印），只要您对您的程序永远运行感到满意 :-)

对于使用无限递归的“全部”的更有用的示例，Web 服务器可能具有使用不终止的递归函数定义的永远运行的“主循环”。

编辑：如果存在某些“懒惰”元素，这些原则当然可以应用于其他语言。这是使用生成器移植到 Python 的上述 fibS 实现：

def zipWith(func, iter1, iter2):
    while True:
        yield func(iter1.next(), iter2.next())

def tail(iter):
    iter.next()
    for x in iter:
        yield x

def fibS():
    yield 1
    yield 1
    for x in zipWith(lambda x,y: x + y, fibS(), tail(fibS())):
        yield x

# Test it by printing out the first n elements.
def take(n, iter):
    while n > 0:
        yield iter.next()
        n = n - 1

print list(take(10, fibS()))

不要指望它和 Haskell 版本一样高效！您可以使用一些技巧和某种全局对象来提高效率。但请注意缺少明确的终止条件。

于 2009-10-06T19:38:36.333 回答
0

如果您希望递归停止，则必须进行测试。

但是你可以有一些不同的东西，比如 Hanoi Tower 算法（2 递归调用）：

河内塔

int Hanoi( source, mid, destination, height ) {

if ( height == 1 ) { print source '->' destination }
else
   Hanoi ( source, destination, mid, height - 1 ) ; # move all upper tower from source to mid
   print source '->' destination;
   Hanoi ( mid , source, destination, height -1 ) ; # move all the upper tower from mid to destination

}
Hanoi ( "0", "1", "2", 8 );

将打印将 8 个光盘从源移动到目标的解决方案。有关游戏规则，请参见http://en.wikipedia.org/wiki/Tower_of_Hanoi。

于 2009-10-06T19:01:28.293 回答
0

谷歌有很多关于递归的资料。:)

于 2009-10-06T19:03:16.560 回答
0

“最佳实践”是尝试使用结构归纳（粗略地说，是对数据结构的折叠）。如果失败，您可能需要考虑一般（无限制）递归。

例如，在处理列表时，习惯上使用折叠。许多功能，例如连接和附加，都可以用这种方式轻松描述。

于 2011-01-26T15:34:55.213 回答