头递归和尾递归的区别

Question

头递归和尾递归的区别

javarecursiondifference

45

我正在尝试理解这两种递归策略的区别。

我被告知的定义如下：

- 尾递归：如果在调用返回后不需要进行任何操作，则此调用为尾递归，即当调用返回时，返回值会立即从调用函数返回。 - 头递归：当函数的第一个语句是递归调用时，此调用为头递归。

- Scarl

4

“Head recursion”这个概念我以前从未听说过。它似乎并不是一个有用的概念；因为递归调用很少作为函数执行的第一件事情。这就排除了任何条件来确定是否执行该调用以及需要在函数调用之前评估的任何参数。在某些语言中，这甚至是不可能的，因为函数必须在运行时评估表达式以确定要递归调用的函数。 - user2357112

我在谷歌上搜索了一下。看起来使用这个术语的来源对“head”的定义非常宽泛，大致意思是在“真正的工作”之前。我不确定为什么他们要定义“头递归”，因为他们似乎没有深入探讨这个概念。它绝对不像尾递归那样有用。 - user2357112

1

区分头递归和不是尾递归似乎是多余的。 - Sylwester

@user2357112：抱歉回复晚了，但头递归和尾递归的区别很重要，因为它可能会对内存产生影响。在递归调用之前计算的任何内容都必须存储在堆栈中，直到整个后续递归函数被计算完毕。某些系统需要更多的内存，因此无法进行深度递归并可能出现错误，而对于头递归，只需将函数的结果传递到下一个计算迭代中，因此每次只需要存储1个值。 - John Smith

1

@MichaelKupietz：你的理解是反过来了。尾递归可以被优化以消除无限调用栈增长，一些函数式编程语言要求这样做。而“头递归”需要维护调用栈信息，从而防止这种优化。 - user2357112

显示剩余2条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Java Curious ღ · Accepted Answer

在头递归中，递归调用发生时会在函数中的其他处理之前发生（可以将其想象为在函数顶部或头部进行）。

在尾递归中则相反——处理发生在递归调用之前。选择两种递归样式似乎是任意的，但选择可能会产生很大的区别。

具有路径上单个递归调用的函数在路径开头使用所谓的头递归。先前展示的阶乘函数使用了头递归。一旦它确定需要递归，它第一件要做的事情就是使用递减参数调用自己。

在路径末尾具有单个递归调用的函数使用尾递归。参考这篇文章

递归示例：

public void tail(int n)         |     public void head(int n)
{                               |     {
    if(n == 1)                  |         if(n == 0)
        return;                 |             return;
    else                        |         else
        System.out.println(n);  |             head(n-1);
                                |
    tail(n-1);                  |         System.out.println(n);
}                               |     }

如果递归调用发生在方法的结尾，它被称为尾递归。尾递归类似于循环。该方法在跳入下一个递归调用之前执行所有语句。

如果递归调用发生在方法的开头，它被称为头递归。该方法在跳入下一个递归调用之前保存状态。