区分简单递归和多递归

Question

我们的教授要求我们去Distinguish between simple and multiple recursion，我不确定我是否理解正确。

从我所知，多次递归是当一个方法在他的生命周期中被调用多次（例如斐波那契），但是简单的递归呢？是否仅仅调用一次方法？如果你能举个例子吗？

这是教授。问题

Answer 1

单呼叫递归的典型例子是阶乘函数：

f(n) = n * (n-1) * (n-2) ... * 3 * 2 * 1 

这将被实现为伪代码：

def factorial (int n, assert n > 0): 
    if n == 1: 
     return 1 
    return n * factorial (n - 1)   # one call 

对比度与天真斐波那契发生器：

def fib (int n, assert n >= 0): 
    if n < 2: 
     return 1 
    return fib (n - 1) + fib (n - 2)  # two calls 

---

维基百科从而定义了这些术语，虽然使用single而非simple，这使得在对比multiple更有意义：

单递归和多个递归

递归只包含单个自引用称为单递归，而包含多个自引用的递归是kno作为多次递归。

单递归的标准示例包括列表遍历，例如在线性搜索中，或者计算阶乘函数，而多次递归的标准示例包括树遍历，比如在深度优先搜索中，或者计算斐波那契数列。

---

不真的一个很好的使用情况递归因为有大量的在每个呼叫的反复努力。迭代求解好得多在这种情况下（代码是长一点，但工作量最小化）：

def fib (int n, assert n >= 0): 
    if n < 2: 
     return 1 
    n = n - 2 

    grandparent = 1 
    parent = 1 
    me = grandparent + parent 
    while n > 0: 
     n = n - 1 
     grandparent = parent 
     parent = me 
     me = grandparent + parent 
    return me