递归函数最佳实践；这些是什么？

Question

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

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

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

谢谢！ :)

Answer 1

差不多就这样了。

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

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

Answer 2

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

递归有多种类型：

• “标准”递归

  让rec sum = 函数
      | []-> 0
      | x::x' -> x + 总和 x'
  

• 尾递归

  让rec sum acc = 函数
      | []-> ACC
      | x::x' ->总和 (x + acc) x'
  

• 互递归

   let rec f() = g()
   且 g() = f()
  

• 定点递归< /p>

  让阶乘 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

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

Answer 3

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

Answer 4

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

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

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

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

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

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

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

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 版本一样高效！您可以使用一些技巧和某种全局对象来提高它的效率。但请注意缺乏明确的终止条件。

Answer 5

有很多变体，例如：

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());
}

它们的共同点是，它们将任务分成更小的任务，然后使用自身来解决更小的任务，直到它们小到可以通过简单的操作来解决。

Answer 6

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

但你可以有一些不同的东西，比如河内塔算法（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 了解游戏规则。

Answer 7

Google 提供了大量有关递归的信息。 :)

Answer 8

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

例如，在处理列表时，通常使用折叠。许多函数，例如串联和附加，很容易用这种方式描述。