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

これにより、再帰ソリューションと同じ順序で要素が比較されます。

最大値を見つけることは、折りたたみ操作 (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
}
于 2013-05-07T16:26:00.950 に答える