線形再帰と線形反復 - hiroya itoの雑記

消えちゃったので再ポスト

線形再帰なサブルーチンスタックが山状にふくれあがる
- ステップはO(n) スペースはnに比例する
線形反復なサブルーチンスタックのスペースは一定
- ステップはO(n) スペースは1

#!/usr/bin/perl
#Time-stamp: <07/03/03 19:12:03 hiroya>

#use strict;
#use warnings;

sub factorial_recursive {
    my $n = shift;
    
    $n == 1 ? $n : $n * factorial_recursive($n - 1); # 10
}

sub factorial_liner {
    my $n = shift;
    fact_ite(1,1,$n); 
}

sub fact_ite {
    my($product,$counter,$maxcount) = @_;
    
    $counter > $maxcount ? $product  :
        fact_ite(($counter * $product) , ++$counter , $maxcount); 
}

print factorial_recursive(5);         
print factorial_liner(5);

結果は下記の通り。線形再帰な方はスタックが山なりにふくれあがる

#デバッグオプションをつけてコンパイルしたPerlで実行させる
$ /usr/local/bin/perl -D2 iterator.pl >& iterator.out.D2
$ less iterator.out.D2
(省略)
EXECUTING...
=>
=>
=>
=> *
=> **
=> ** IV(5)
=> ** IV(5) GV()
=> * IV(5)
=> *
=> * GV()
=> * AV()
=> * IV(5)
=> * IV(5) UNDEF
=> * IV(5)
=> *
=> * IV(5)
=> * IV(5) IV(1)
=> * SV_NO
=> *
=> * IV(5)
=> * IV(5) *
=> * IV(5) * IV(5)
=> * IV(5) * IV(5) IV(1)
=> * IV(5) * IV(4)
=> * IV(5) * IV(4) GV()
=> * IV(5) IV(4)
=> * IV(5)
=> * IV(5) GV()
=> * IV(5) AV()
=> * IV(5) IV(4)
=> * IV(5) IV(4) UNDEF
=> * IV(5) IV(4)
=> * IV(5)
=> * IV(5) IV(4)
=> * IV(5) IV(4) IV(1)
=> * IV(5) SV_NO
=> * IV(5)
=> * IV(5) IV(4)
=> * IV(5) IV(4) *
=> * IV(5) IV(4) * IV(4)
=> * IV(5) IV(4) * IV(4) IV(1)
=> * IV(5) IV(4) * IV(3)
=> * IV(5) IV(4) * IV(3) GV()
=> * IV(5) IV(4) IV(3)
=> * IV(5) IV(4)
=> * IV(5) IV(4) GV()
=> * IV(5) IV(4) AV()
=> * IV(5) IV(4) IV(3)
=> * IV(5) IV(4) IV(3) UNDEF
=> * IV(5) IV(4) IV(3)
=> * IV(5) IV(4)
=> * IV(5) IV(4) IV(3)
=> * IV(5) IV(4) IV(3) IV(1)
=> * IV(5) IV(4) SV_NO
=> * IV(5) IV(4)
=> * IV(5) IV(4) IV(3)
=> * IV(5) IV(4) IV(3) *
=> * IV(5) IV(4) IV(3) * IV(3)
=> * IV(5) IV(4) IV(3) * IV(3) IV(1)
=> * IV(5) IV(4) IV(3) * IV(2)
=> * IV(5) IV(4) IV(3) * IV(2) GV()
=> * IV(5) IV(4) IV(3) IV(2)
=> * IV(5) IV(4) IV(3)
=> * IV(5) IV(4) IV(3) GV()
=> * IV(5) IV(4) IV(3) AV()
=> * IV(5) IV(4) IV(3) IV(2)
=> * IV(5) IV(4) IV(3) IV(2) UNDEF
=> * IV(5) IV(4) IV(3) IV(2)
=> * IV(5) IV(4) IV(3)
=> * IV(5) IV(4) IV(3) IV(2)
=> * IV(5) IV(4) IV(3) IV(2) IV(1)
=> * IV(5) IV(4) IV(3) SV_NO
=> * IV(5) IV(4) IV(3)
=> * IV(5) IV(4) IV(3) IV(2)
=> * IV(5) IV(4) IV(3) IV(2) *
=> * IV(5) IV(4) IV(3) IV(2) * IV(2)
=> * IV(5) IV(4) IV(3) IV(2) * IV(2) IV(1)
=> * IV(5) IV(4) IV(3) IV(2) * IV(1)
=> * IV(5) IV(4) IV(3) IV(2) * IV(1) GV()
=> * IV(5) IV(4) IV(3) IV(2) IV(1)
=> * IV(5) IV(4) IV(3) IV(2)
=> * IV(5) IV(4) IV(3) IV(2) GV()
=> * IV(5) IV(4) IV(3) IV(2) AV()
=> * IV(5) IV(4) IV(3) IV(2) IV(1)
=> * IV(5) IV(4) IV(3) IV(2) IV(1) UNDEF
=> * IV(5) IV(4) IV(3) IV(2) IV(1)
=> * IV(5) IV(4) IV(3) IV(2)
=> * IV(5) IV(4) IV(3) IV(2) IV(1)
=> * IV(5) IV(4) IV(3) IV(2) IV(1) IV(1)
=> * IV(5) IV(4) IV(3) IV(2) SV_YES
=> * IV(5) IV(4) IV(3) IV(2)
=> * IV(5) IV(4) IV(3) IV(2) IV(1)
=> * IV(5) IV(4) IV(3) IV(2) IV(1)
=> * IV(5) IV(4) IV(3) IV(2)
=> * IV(5) IV(4) IV(3) IV(2)
=> * IV(5) IV(4) IV(6)
=> * IV(5) IV(4) IV(6)
=> * IV(5) IV(24)
=> * IV(5) IV(24)
=> * IV(120)
=> * IV(120)
=> SV_YES
=>
=> *
=> **
=> ** IV(5)
=> ** IV(5) GV()
=> * IV(5)
=> *
=> * GV()
=> * AV()
=> * IV(5)
=> * IV(5) UNDEF
=> * IV(5)
=> *
=> **
=> ** IV(1)
=> ** IV(1) IV(1)
=> ** IV(1) IV(1) IV(5)
=> ** IV(1) IV(1) IV(5) GV()
=> * IV(1) IV(1) IV(5)
=> *
=> **
=> ** GV()
=> ** IV(1) IV(1) IV(5)
=> ** IV(1) IV(1) IV(5) *
=> ** IV(1) IV(1) IV(5) * UNDEF
=> ** IV(1) IV(1) IV(5) * UNDEF UNDEF
=> ** IV(1) IV(1) IV(5) * UNDEF UNDEF UNDEF
=> *
=> *
=> * IV(1)
=> * IV(1) IV(5)
=> * SV_NO
=> *
=> **
=> ** IV(1)
=> ** IV(1) IV(1)
=> ** IV(1)
=> ** IV(1) IV(1)
=> ** IV(1) IV(2)
=> ** IV(1) IV(2) IV(5)
=> ** IV(1) IV(2) IV(5) GV()
=> * IV(1) IV(2) IV(5)
=> *
=> **
=> ** GV()
=> ** IV(1) IV(2) IV(5)
=> ** IV(1) IV(2) IV(5) *
=> ** IV(1) IV(2) IV(5) * UNDEF
=> ** IV(1) IV(2) IV(5) * UNDEF UNDEF
=> ** IV(1) IV(2) IV(5) * UNDEF UNDEF UNDEF
=> *
=> *
=> * IV(2)
=> * IV(2) IV(5)
=> * SV_NO
=> *
=> **
=> ** IV(2)
=> ** IV(2) IV(1)
=> ** IV(2)
=> ** IV(2) IV(2)
=> ** IV(2) IV(3)
=> ** IV(2) IV(3) IV(5)
=> ** IV(2) IV(3) IV(5) GV()
=> * IV(2) IV(3) IV(5)
=> *
=> **
=> ** GV()
=> ** IV(2) IV(3) IV(5)
=> ** IV(2) IV(3) IV(5) *
=> ** IV(2) IV(3) IV(5) * UNDEF
=> ** IV(2) IV(3) IV(5) * UNDEF UNDEF
=> ** IV(2) IV(3) IV(5) * UNDEF UNDEF UNDEF
=> *
=> *
=> * IV(3)
=> * IV(3) IV(5)
=> * SV_NO
=> *
=> **
=> ** IV(3)
=> ** IV(3) IV(2)
=> ** IV(6)
=> ** IV(6) IV(3)
=> ** IV(6) IV(4)
=> ** IV(6) IV(4) IV(5)
=> ** IV(6) IV(4) IV(5) GV()
=> * IV(6) IV(4) IV(5)
=> *
=> **
=> ** GV()
=> ** IV(6) IV(4) IV(5)
=> ** IV(6) IV(4) IV(5) *
=> ** IV(6) IV(4) IV(5) * UNDEF
=> ** IV(6) IV(4) IV(5) * UNDEF UNDEF
=> ** IV(6) IV(4) IV(5) * UNDEF UNDEF UNDEF
=> *
=> *
=> * IV(4)
=> * IV(4) IV(5)
=> * SV_NO
=> *
=> **
=> ** IV(4)
=> ** IV(4) IV(6)
=> ** IV(24)
=> ** IV(24) IV(4)
=> ** IV(24) IV(5)
=> ** IV(24) IV(5) IV(5)
=> ** IV(24) IV(5) IV(5) GV()
=> * IV(24) IV(5) IV(5)
=> *
=> **
=> ** GV()
=> ** IV(24) IV(5) IV(5)
=> ** IV(24) IV(5) IV(5) *
=> ** IV(24) IV(5) IV(5) * UNDEF
=> ** IV(24) IV(5) IV(5) * UNDEF UNDEF
=> ** IV(24) IV(5) IV(5) * UNDEF UNDEF UNDEF
=> *
=> *
=> * IV(5)
=> * IV(5) IV(5)
=> * SV_NO
=> *
=> **
=> ** IV(5)
=> ** IV(5) IV(24)
=> ** IV(120)
=> ** IV(120) IV(5)
=> ** IV(120) IV(6)
=> ** IV(120) IV(6) IV(5)
=> ** IV(120) IV(6) IV(5) GV()
=> * IV(120) IV(6) IV(5)
=> *
=> **
=> ** GV()
=> ** IV(120) IV(6) IV(5)
=> ** IV(120) IV(6) IV(5) *
=> ** IV(120) IV(6) IV(5) * UNDEF
=> ** IV(120) IV(6) IV(5) * UNDEF UNDEF
=> ** IV(120) IV(6) IV(5) * UNDEF UNDEF UNDEF
=> *
=> *
=> * IV(6)
=> * IV(6) IV(5)
=> * SV_YES
=> *
=> * IV(120)
=> * IV(120)
=> * IV(120)
=> * IV(120)
=> * IV(120)
=> * IV(120)
=> * IV(120)
=> * IV(120)
=> SV_YES
120120