头和尾递归之间的区别

java difference recursion

2022-09-01 01:03:10

我试图弄清楚这两种递归策略之间的区别。

我被告知的定义如下：

尾部递归：如果调用返回后无需执行任何操作，即当调用返回时，返回值立即从调用函数返回，则调用是尾递归的

磁头递归：当函数的第一个语句是递归调用时，调用是头递归的。

答案 1

在中，递归调用（当它发生时）出现在函数中的其他处理之前（想想它发生在函数的顶部或头部）。head recursion

在中，情况恰恰相反 — 处理发生在递归调用之前。在两种递归样式之间进行选择可能看起来很武断，但选择可以决定一切。tail recursion

如果函数的路径在路径的开头具有单个递归调用，则该函数使用所谓的头递归。先前展览的阶乘函数使用头部递归。一旦确定需要递归，它做的第一件事就是使用递减的参数调用自身。在路径末尾具有单个递归调用的函数正在使用尾递归。请参阅此文章

示例递归：

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

如果递归调用发生在方法的末尾，则称为 .尾递归为。这。tail recursionsimilar to a loopmethod executes all the statements before jumping into the next recursive call

如果递归调用发生在 .这。beginning of a method, it is called a head recursionmethod saves the state before jumping into the next recursive call

答案 2