递归如何在第一次运行时获得该值

Question

sub maxNum { 
if (@_ == 1) { 
    return $_[0]; # terminal clause - return immediately 
} 
my ($first, @rest) = @_; 
my $remainingMax = maxNum(@rest); 
    if ($first > $remainingMax) { 
    return $first; 
    } 
return $remainingMax; 
} 

我无法消化这段使用递归的代码。基本上我很困惑my $remainingMax = maxNum(@rest);部分。

我只是想知道如何为$remainingMax值存在时，脚本运行的非常第一次之后，据我所知，功能maxNum(@rest)通过返回ANS（即无论是return $first或return $remainingMax）提供的值。

Answer 1

我不明白你的困惑。

第一次maxNum完成它返回列表的最后一项。

现在，如果您想到最后两个项目的列表，那么当您通过这些项目时，一个将变为$first另一个是分配给@rest的唯一元素。当您仅将@rest作为一个元素传递时，您将达到终端条件并将该元素返回并存储在$remainingMax中。然后比较最后两个元素，并返回最大值。

从那里，如果您最初称为maxNum的列表大于两个项目，则考虑返回的最大值并将其与列表末尾的第三项（Perl下标-3）进行比较。如果那是你的总榜单，那么你有你的最大值。如果不是，则返回该值并将其与最后一个（Perl下标-4）中的第四项进行比较。

在准 “Perl符号”

maxNum($_[-1])  ==> $_[-1]; 
maxNum($_[-2..-1]) ==> $_[-2] > maxNum($_[-1])  ? $_[-2] : maxNum($_[-1]); 
maxNum($_[-3..-1]) ==> $_[-3] > maxNum(@_[-2..-1]) ? $_[-3] : maxNum(@_[-2..-1]); 
maxNum($_[-4..-1]) ==> $_[-4] > maxNum(@_[-3..-1]) ? $_[-4] : maxNum(@_[-3..-1]); 
... 

Answer 2

递归函数通常遵循“分而治之” -strategy。

要查找的最大列表

max(a, b, c, d) 

我们可以分区列表随意，然后找到最大的所有局部最大值：

<=> max(max(a, b), max(c, d)) 

你的算法选择以下分区：

<=> max(a, max(b, c, d)) 

对max(b, c, d)也是如此，导致以下呼叫图：

max(a, b, c, d) 
    max(b, c, d) 
     max(c, d) 
     max(d) 

在max(d)，该算法不会进一步递归。相反，这是基本情况（相当于一个循环的终止条件）。 max(d)返回d。现在，我们可以通过最大列表的其余部分的对比给我们的第一价值，通过调用堆栈工作回来的路上

---

还有很多其他的方法这种想法可以被编码找到总最大。它可以转换为非递归形式

sub maxNum { 
    my $current_max = pop; 
    while(@_) { 
    my $compare = pop; 
    $current_max = $compare if $compare > $current_max; 
    } 
    return $current_max; 
} 

这比较了与递归解决方案相同顺序的元素。

查找最大值也可以认为是折叠操作（又名reduce）。我们可以写一个递归函数，它下面的分区：

max(a, b, c, d) 
<=> max(max(a, b), c, d) 
<=> max(max(max(a, b), c), d) 

这看起来相当复杂，但导致一个优雅的解决方案：

sub maxNum { 
    return $_[0] unless $#_;  # return if less than two elems 
    my ($x, $y) = splice 0, 2, @_; # shift first two elems from @_ 
    my $max = $x > $y ? $x : $y; # select larger 
    return maxNum($max, @_);  # recurse 
} 

函数调用，其价值立即返回被称为一个尾呼。我们可以通过使用特殊的goto &subroutine表达式来提高效率。但是，我们必须手动设置参数列表：

sub maxNum { 
    return shift unless $#_;  # base case: return on one argument 
    my ($x, $y) = splice 0, 2, @_; # take the first two elems from start 
    unshift @_, $x > $y ? $x : $y; # put the larger one back there 
    goto &maxNum;     # recurse with tail call 
}