1 
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）来提供值。

4

2 回答 2

5

递归函数通常遵循“分而治之”的策略。

查找列表的最大值

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
}
于 2013-05-07T16:26:00.950 回答
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] );
...
于 2013-05-07T15:47:03.240 回答