Tail call optimization


#1

e$B!!$5$5$@$G$9!%e(B

e$B!!KvHx8F$S=P$7$N:GE,2=5!G=$r!$$-$A$s$H9M$($F;H$($k$h$&$K$7$F$_$^$7$?!%A0e(B
e$B$+$i=hM}<+BN$OF~$C$F$?$s$G$9$,!$>/$7??LLL$K9M$(D>$7$F;H$($k$h$&$K$7$?$@e(B
e$B$1$G$9!%e(B

def rec n
rec n-1 if n > 0
end

rec 100000

e$B!!$3$s$J%W%m%0%i%`$bF0$-$^$9!%e(B

e$B!!$?$@$7!$%G%U%)%k%H$G$O;H$($J$$$h$&$K$J$C$F$$$^$9!J<B9T;~$K@Z$jBX$(2De(B
e$BG=!K!%$3$l$O!$5sF0$,$$$m$$$m$HJQ$o$k$+$i$G$9!%6qBNE*$K$O!$e(B

e$B!&%9%?%C%/%H%l!<%9$,JQ$o$k!Je(Bcallere$B$NJV$jCM$b!Ke(B
e$B!&%9%?%C%/%*!<%P!<%U%m!<%(%i!<$,=P$J$/$J$k>l9g$,$"$ke(B

e$B$H$$$&$N$,82Cx$@$H;W$$$^$9!%B>$K$b$"$k$+$b$7$l$^$;$s$,!$$H$j$"$($:;W$$$De(B
e$B$-$^$;$s!%e(B

e$B!!$3$N5!G=$I$&$7$^$7$g$&!%e(B

(1)
e$B$3$l$Ge(BRubye$B$G$b4X?t7?%W%m%0%i%_%s%0$,=PMh$k$>!$$H$U$l$^$o$ke(B
(2) Rubye$B$K9g$o$J$$$+$i5!G=$r$J$+$C$?;v$K$9$k!J>C$9!Ke(B
(3) e$BCN$C$F$$$k?M$7$+;H$o$J$$$h$&$J!$1#$75!G=$K$9$ke(B
e$B!!!Nc$($Pe(B ObjC e$B3HD%$de(B python like e$B%V%m%C%/$H$+$HF1$8e(B
(3’) e$B$H$j$"$($:F~$l$F$*$/$,!$$b$&$A$g$C$H!$;EMM$r8!F$$9$ke(B

e$B!!$A$J$_$K!$$$$o$f$kKvHx:F5/$N:GE,2=!J<+J,<+?H$X$Ne(B jump
e$B$KJQ49!K$G$O$Je(B
e$B$/!$KvHx8F$S=P$7$N:GE,2=$G!$%9%?%C%/$,$"$U$l$J$$$h$&$K:Y9)$7$?$b$N$G$9!%e(B
e$B$J$N$G!$9bB.2=$K$O$"$s$^$j4sM?$7$F$$$^$;$s!%e(B


#2

e$B$^$D$b$He(B e$B$f$-$R$m$G$9e(B

In message “Re: [ruby-dev:30800] tail call optimization”
on Mon, 21 May 2007 14:23:38 +0900, SASADA Koichi removed_email_address@domain.invalid
writes:

|(1) e$B$3$l$Ge(BRubye$B$G$b4X?t7?%W%m%0%i%_%s%0$,=PMh$k$>!$$H$U$l$^$o$ke(B
|(2) Rubye$B$K9g$o$J$$$+$i5!G=$r$J$+$C$?;v$K$9$k!J>C$9!Ke(B
|(3) e$BCN$C$F$$$k?M$7$+;H$o$J$$$h$&$J!$1#$75!G=$K$9$ke(B
|e$B!!!Nc$($Pe(B ObjC e$B3HD%$de(B python like e$B%V%m%C%/$H$+$HF1$8e(B
|(3’) e$B$H$j$"$($:F~$l$F$*$/$,!$$b$&$A$g$C$H!$;EMM$r8!F$$9$ke(B

(4) e$BF~$l$k$7;H$&$1$IJL$K?($l2s$k$3$H$^$G$O$7$J$$e(B

e$B$/$i$$$G$$$+$,$G$7$g$&!)e(B
e$B;EMM$K$D$$$F$OLdBj$J$$$s$8$c$J$$$+$He(B
e$B;W$$$^$9!#e(BRubye$B$N>l9g!“e(Baliase$B$H$+$”$k$s$GK\Ev$K:F5"$J$N$+H=Dje(B
e$B$9$k$N$K%3%9%H$,$+$+$j$^$9$+$i!"e(Bjumpe$B$X$N:GE,2=$O7k9=Fq$7$$$se(B
e$B$G$J$$$+$H;W$$$^$9$7!#e(B

e$B$A$g$C$H9M$($?$N$O!"e(B recall e$B$H$$$&%-!<%o!<%I$rMQ0U$7$F!"e(B
recall(args)e$B$G<+J,<+?H$r8F$S=P$7e(B(jumpe$B$K:GE,2=$G$-$ke(B)e$B$H$$$&$Ne(B
e$B$O$I$&$G$7$g$&$M$(!#e(B


#3

e$B!!$5$5$@$G$9!%e(B

Yukihiro M. wrote:

(4) e$BF~$l$k$7;H$&$1$IJL$K?($l2s$k$3$H$^$G$O$7$J$$e(B

e$B$/$i$$$G$$$+$,$G$7$g$&!)e(B e$B;EMM$K$D$$$F$OLdBj$J$$$s$8$c$J$$$+$He(B
e$B;W$$$^$9!#e(BRubye$B$N>l9g!“e(Baliase$B$H$+$”$k$s$GK\Ev$K:F5"$J$N$+H=Dje(B
e$B$9$k$N$K%3%9%H$,$+$+$j$^$9$+$i!"e(Bjumpe$B$X$N:GE,2=$O7k9=Fq$7$$$se(B
e$B$G$J$$$+$H;W$$$^$9$7!#e(B

e$B!!$3$l$OKvHx:F5"$N:GE,2=$NOC$G$9$+!%e(BRubye$B$NJ8K!$r<i$k8B$j!$%8%c%s%W$X$NJQe(B
e$B49$O@dBP$KL5M}$J$s$8$c$J$$$+$H;W$$$^$9!%e(BJavae$B$G$$$&!$e(Bprivatee$B%a%=%C%I$r:ne(B
e$B$k$N$J$i$J$s$H$G$b$J$j$=$&$G$9$,!%e(B

e$B$A$g$C$H9M$($?$N$O!"e(B recall e$B$H$$$&%-!<%o!<%I$rMQ0U$7$F!"e(B
recall(args)e$B$G<+J,<+?H$r8F$S=P$7e(B(jumpe$B$K:GE,2=$G$-$ke(B)e$B$H$$$&$Ne(B
e$B$O$I$&$G$7$g$&$M$(!#e(B

e$B!!$=$3$^$G$9$k$J$i%k!<%W$G$$$$$h$&$J5$$O$7$^$9!%5$$N$;$$$+$7$i$s!%e(B

e$B!!%a%=%C%IFb$G$Ne(B retry(args) e$B$H$+!$$U$H;W$$$D$-$^$7$?!%e(B

def cnt n
retry n-1 if n>0
end

e$B!!$C$F!$%V%m%C%/Cf$G$O;H$($J$$$+$i%@%a$+!%e(B


#4

e$B!!$5$5$@$G$9!%e(B

Yukihiro M. wrote:

e$B$h$M!#F10U$7$^$9!#%a%=%C%I%k%C%/%"%C%W$r9T$C$F!"<+J,<+?H$r8Fe(B
e$B$s$G$$$k$3$H$r3NG’$G$-$l$Pe(Bjumpe$B$K:GE,2=$G$-$k$H;W$$$^$9$,!"%3e(B
e$B%9%HE*$K@^$j9g$o$J$$$G$7$g$&$M!#e(B

e$B!!$"$"!$@dBPL5M}$H8@$C$F$$$?$N$O%3%s%Q%$%k;~$Ke(B jump
e$B$XCV$-49$($k!$$H$$$&e(B
e$BOC$G$7$?!%e(B

e$B!!$G!$$3$l$O%G%U%)%k%H$G%%U$K$7$F$$$^$9$,!$%%s$K$7$H$-$^$9!)!!$=$l$He(B
e$B$b!$%%U$N$^$^$K$7$F$$-$^$7$g$&$+!%e(B


#5

e$B$^$D$b$He(B e$B$f$-$R$m$G$9e(B

In message “Re: [ruby-dev:30802] Re: tail call optimization”
on Tue, 22 May 2007 01:48:34 +0900, SASADA Koichi removed_email_address@domain.invalid
writes:

|> e$B$/$i$$$G$$$+$,$G$7$g$&!)e(B e$B;EMM$K$D$$$F$OLdBj$J$$$s$8$c$J$$$+$He(B
|> e$B;W$$$^$9!#e(BRubye$B$N>l9g!“e(Baliase$B$H$+$”$k$s$GK\Ev$K:F5"$J$N$+H=Dje(B
|> e$B$9$k$N$K%3%9%H$,$+$+$j$^$9$+$i!“e(Bjumpe$B$X$N:GE,2=$O7k9=Fq$7$$$se(B
|> e$B$G$J$$$+$H;W$$$^$9$7!#e(B
|
|e$B!!$3$l$OKvHx:F5”$N:GE,2=$NOC$G$9$+!%e(BRubye$B$NJ8K!$r<i$k8B$j!$%8%c%s%W$X$NJQe(B
|e$B49$O@dBP$KL5M}$J$s$8$c$J$$$+$H;W$$$^$9!%e(BJavae$B$G$$$&!$e(Bprivatee$B%a%=%C%I$r:ne(B
|e$B$k$N$J$i$J$s$H$G$b$J$j$=$&$G$9$,!%e(B

e$B@dBP$K!"$H$$$&$N$O!V8=<BE*$J%3%9%H$G$O!W@dBP$K$H$$$&0UL#$G$9e(B
e$B$h$M!#F10U$7$^$9!#%a%=%C%I%k%C%/%"%C%W$r9T$C$F!"<+J,<+?H$r8Fe(B
e$B$s$G$$$k$3$H$r3NG’$G$-$l$Pe(Bjumpe$B$K:GE,2=$G$-$k$H;W$$$^$9$,!"%3e(B
e$B%9%HE*$K@^$j9g$o$J$$$G$7$g$&$M!#e(B

|> e$B$A$g$C$H9M$($?$N$O!"e(B recall e$B$H$$$&%-!<%o!<%I$rMQ0U$7$F!"e(B
|> recall(args)e$B$G<+J,<+?H$r8F$S=P$7e(B(jumpe$B$K:GE,2=$G$-$ke(B)e$B$H$$$&$Ne(B
|> e$B$O$I$&$G$7$g$&$M$(!#e(B
|
|e$B!!$=$3$^$G$9$k$J$i%k!<%W$G$$$$$h$&$J5$$O$7$^$9!%5$$N$;$$$+$7$i$s!%e(B

e$B$$$d!":F5"8F=P$7$C$]$/8+$($k$N$,=EMW$J$N$G$7$g$&!"$?$V$s!#e(B
recalle$B$O:G6aFI$s$@2?$+$N8@8l$K$D$$$F$?5!G=$G$9!#$(!<$H!"e(BRe$B$@$Ce(B
e$B$?$+$J!#e(B

                            e$B$^$D$b$He(B e$B$f$-$R$me(B /:|)

#6

e$B$^$D$b$He(B e$B$f$-$R$m$G$9e(B

In message “Re: [ruby-dev:30804] Re: tail call optimization”
on Tue, 22 May 2007 12:38:05 +0900, SASADA Koichi removed_email_address@domain.invalid
writes:

|e$B!!$G!$$3$l$O%G%U%)%k%H$G%%U$K$7$F$$$^$9$,!$%%s$K$7$H$-$^$9!)!!$=$l$He(B
|e$B$b!$%%U$N$^$^$K$7$F$$-$^$7$g$&$+!%e(B

e$B%G%U%)%k%H%*%s$G$$$$$s$8$c$J$$$G$7$g$&$+!#%9%?%C%/$N@aLs$Ke(B
e$B$b$J$j$=$&$@$7!#e(B