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

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

递归函数通常遵循"分而治之" - 策略.

查找列表的最大值

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

这会将元素与递归解决方案的顺序进行比较.

找到最大值也可以被认为是折叠操作(aka 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
}