Mailing List Archive: 49091 messages

## [REBOL] Re: Stack depth & Recursion

### From: joel:neely:fedex at: 10-Jul-2001 16:58

```
Hi, Cal!

Cool!

Cal Dixon wrote:
> After seeing this discussion I wrote a little hack to implement
> tail recursion elimination.  I'm sure it could be done better
> (Joel? Ladislav? anybody wanna fix this thing up?) but works
> well enough that I'll probably use it the next time I need deep
> recursion. (wow.. up to 452000 already) anyway, here it is, enjoy!
>
...
> ; example:
> ; >> tail-func 'recfun [x] [] [prin [x #" "] x: x + 1 recfun x]
> ;>> recfun 1
> ;   now watch it run  ;-)
>

I'm not quite as ambitious!  Rather than trying to make something
that looks like the current FUNC or FUNCTION, I thought about the
idea that a typical tail-recursive function looks something like
the following schema

blort: func [arg-a arg-b ... arg-z] [
either termination-condition [
final-expression
][
blort expr-a expr-b ... expr-z
]
]

For example, the tail-recursive block-summer from earlier:

>> nums: [90 1 45 52 42 19]
== [90 1 45 52 42 19]

tr-sum: func [b [block!] /local -tr-sum] [
-tr-sum: func [b [block!] s [number!]] [
either tail? b [s] [-tr-sum  next b  s + first b]
]
-tr-sum b 0
]

>> tr-sum nums
== 249

fits that scheme with

[b [block!] s [number!]]

as the arguments,

tail? b

as the exit condition,

s

as the exit expression, and

next b   s + first b

as the arguments to the recursive call.

Thinking of it that way led me to define this:

recurrence: function [
"Create a tail-recurrence function"
funargs [block!]
exitcond [block!]
exitexpr [block!]
recurrence [block!]
][
pureargs funbody
][
pureargs: copy/part funargs any [find funargs /local length?
funargs]
while [not tail? pureargs] [
either word? first pureargs [
pureargs: next pureargs
][
remove pureargs
]
]
funbody: compose/deep [
while [not (exitcond)] [ set [(pureargs)] reduce
[(recurrence)] ]
(exitexpr)
]
func funargs funbody
]

which can define our block-summer by saying:

rr: recurrence [b [block!] s [number!]] [
tail? b
][
s
][
next b   s + first b
]

>> rr nums 0
== 249

and can do the canonical Fibonacci example (using a helper function)
as follows:

-fib: recurrence [
"tail-recurrence function for Fibonacci numbers"
a [integer!] "current value"
b [integer!] "prior value"
n [integer!] "Fibonacci index desired"
][
n <= 0
][
a
][
a + b   a   n - 1
]

fib: func [i [integer!]] [-fib 0 1 i]

use [i] [
repeat j 10 [i: j - 1  print [i fib i]]
]

which gives us the standard

0 0
1 1
2 1
3 2
4 3
5 5
6 8
7 13
8 21
9 34

Have fun!

-jn-

--
My hero, zero. Such a funny little hero,
But till you came along, we counted on our fingers and toes.
-- Schoolhouse Rock (1973)
joelDOTneelyATfedexDOTcom
```