再帰関数は通常、「分割統治」戦略に従います。
リストの最大値を見つけるには
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
}