Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
re: Tail recursion & CL
34 views
Skip to first unread message
WJ
May 23, 2012, 9:49:30 AM5/23/12
to
Barry Margolin wrote:
> In my experience, most recursive functions are not written in a
> tail-recursive manner, so the benefit is not even that significant.
> Writing tail-recursive code often requires contorting the way the algorithm
> is expressed. For instance, the simple recursive factorial:
>
> (defun fact (n)
> (if (<= n 2)
> 1
> (* n (fact (1- n)))))
>
> must become:
>
> (defun fact (n)
> (flet ((fact-internal (n accumulator)
> (if (<= n 2)
> accumulator
> (fact-internal (1- n) (* n accumulator)))))
> (fact-internal n 1)))
Racket:
(define (fac n [result 1])
(if (zero? n)
result
(fac (sub1 n) (* n result))))
> In my experience, most recursive functions are not written in a
> tail-recursive manner, so the benefit is not even that significant.
> Writing tail-recursive code often requires contorting the way the algorithm
> is expressed. For instance, the simple recursive factorial:
>
> (defun fact (n)
> (if (<= n 2)
> 1
> (* n (fact (1- n)))))
>
> must become:
>
> (defun fact (n)
> (flet ((fact-internal (n accumulator)
> (if (<= n 2)
> accumulator
> (fact-internal (1- n) (* n accumulator)))))
> (fact-internal n 1)))
Racket:
(define (fac n [result 1])
(if (zero? n)
result
(fac (sub1 n) (* n result))))
WJ
May 23, 2012, 10:22:57 AM5/23/12
to
4023872600770937735437024339230039857193748642107146325437999104
2993851239862902059204420848696940480047998861019719605863166687
2994808558901323829669944590997424504087073759918823627727188732
5197795059509952761208749754624970436014182780946464962910563938
8743788648733711918104582578364784997701247663288983595573543251
3185323958463075557409114262417474349347553428646576611667797396
6688202912073791438537195882498081268678383745597317461360853795
3452422158659320192809087829730843139284440328123155861103697680
1357304216168747609675871348312025478589320767169132448426236131
4125087802080002616831510273418279777047846358681701643650241536
9139828126481021309276124489635992870511496497541990934222156683
2572080821333186116811553615836546984046708975602900950537616475
8477284218896796462449451607653534081989013854424879849599533191
0172335555660213945039973628075013783761530712776192684903435262
5200015888535147331611702103968175921510907788019393178114194545
2572238655414610628921879602238389714760885062768629671466746975
6291123408243920816015378088989396451826324367161676217916890977
9911903754031274622289988005195444414282012187361745992642956581
7466283029555702990243241531816172104658320367869061172601587835
2075151628422554026517048330422614397428693306169089796848259012
5458327168226458066526769958652682272807075781391858178889652208
1643483448259932660433676601769996128318607883861502794659551311
5655203609398818061213855860030143569452722420634463179746059468
2573103790084024432438465657245014402821885252470935190620929023
1364932734975655139587205596542287497740114133469627154228458623
7738753823048386568897646192738381490014076731044664025989949022
2221765904339901886018566526485061799702356193897017860040811889
7299183110211712298459016419210688843871218556461249607987229085
1929681937238864261483965738229112312502418664935314397013742853
1926649875337218940694281434118520158014123344828015051399694290
1534830776445690990731524332782882698646027898643211390835062170
9500259738986355427719674282224875758676575234422020757363056949
8825087968928162753848863396909959826280956121450994871701244516
4612603790293091208890869420285106401821543994571568059418727489
9809425474217358240106367740459574178516082923013535808184009699
6372524230560855903700624271243416909004153690105933983835777939
4109700277534720000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
00000000
0 new messages