头尾递归的区别

Question

我试图找出这两种递归策略之间的区别.

我被告知的定义如下:

尾递归:如果在调用返回后没有必要进行调用,则调用是尾递归的,即当调用返回时,返回的值立即从调用函数返回

Head Recursion:当函数的第一个语句是递归调用时,调用是头递归的.

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

如果递归调用发生在方法的末尾,则称为a tail recursion.尾递归是similar to a loop.的method executes all the statements before jumping into the next recursive call.

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