Recursion

[Mark Wills]

Does anyone have any simple examples of recursion using RECURSE?
Preferably something where one can see the 'un-winding' as each
instance exits.

Thanks

Mark

[Luca Saiu]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

The most classical one:

- --8<---------------cut here---------------start------------->8---
: fact ( u -- u! ) dup 0= if drop 1 else dup 1- recurse * then ;
- --8<---------------cut here---------------end--------------->8---

If you want to see the "unwinding", you can print out the stack just
before returning:

- --8<---------------cut here---------------start------------->8---
: fact ( u -- u! ) dup 0= if drop 1 else dup 1- recurse * then .s ;
- --8<---------------cut here---------------end--------------->8---

Regards,

- --
Luca Saiu
Home page: http://www-lipn.univ-paris13.fr/~saiu
My blog: http://ageinghacker.net/blog
GNU epsilon: http://www.gnu.org/software/epsilon
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.11 (GNU/Linux)

iEYEARECAAYFAk997ooACgkQvzOavibF0oaLOQCdEx1AMqXX1q15cdid6nwUHxEM
9dAAnjVw6ijTx1y5sLuU7KORLGZsZl3G
=r5wT
-----END PGP SIGNATURE-----

[Luca Saiu]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 2012-04-05 at 21:12, Luca Saiu wrote:

> On 2012-04-05 at 17:15, Mark Wills wrote:
>
>> Does anyone have any simple examples of recursion using RECURSE?
>> Preferably something where one can see the 'un-winding' as each
>> instance exits.
>
> The most classical one:
>

> --8<---------------cut here---------------start------------->8---
> : fact ( u -- u! ) dup 0= if drop 1 else dup 1- recurse * then ;

> --8<---------------cut here---------------end--------------->8---

- From your past contributions to c.l.f. you don't seem to be a beginner;
hence I probably misunderstood your question. Sorry for the noise, if
that's the case.

- --
Luca Saiu
Home page: http://www-lipn.univ-paris13.fr/~saiu
My blog: http://ageinghacker.net/blog
GNU epsilon: http://www.gnu.org/software/epsilon
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.11 (GNU/Linux)

iEYEARECAAYFAk998tsACgkQvzOavibF0oYs6ACgpTTF8Ytul7oc/19dcaNC/OiR
zC8An0+jU3XKto2VlcF1+0pq4jQ3jB0+
=O9jg
-----END PGP SIGNATURE-----

[Mark Wills]

No, this is perfect, thank you very much!

You can see how I modified it viewing this page: http://turboforth.net/locals.html

Regards

Mark

[David N. Williams]

Here are some examples supplied by Bill Muench, with tests:

http://www.umich.edu/~williams/archive/forth/utilities/recurse-test.fs

--David

[P.M.Lawrence]

I would suggest eforth's high level implementations of PICK and ROLL.
They use a test for a parameter of zero to handle a base case, and for
higher values they recurse and do "winding" and "unwinding" on either
side of a recursive call with a parameter one less, to move the stack
item that was below the parameter temporarily on and off the return
stack during the recursive call and then SWAP it with the top of the
stack that was left by the recursive call. P.M.Lawrence.

[Hugh Aguilar]

Every example program in the novice package involves recursion, except
for the N-Queens program which is iterative --- that is supposed to be
ironic, as the N-Queens problem is a textbook example of recursion.

The simplest would likely be the recursive version of fibonacci or
parallel-resistance. Slightly more complicated would be HANOI. The
LowDraw poker analysis program is a step up from that. Symtab or
ASSOCIATION is a step up from that. There are lots of example programs
in there that use recursion, so pick something to suit you. Some of
these use RECURSE, and some use mutual recursion.

Why do you ask about this? Do you not understand how RECURSE works? It
is really simple --- it is just a function call. The reason why the
function name can't be used, is because it is smudged during the
definition of the function --- you will either get a error message
saying that your function is undefined, or (worse) you will get a
previous definition with the same name --- but to get the function
itself you need to use RECURSE.

[Paul Rubin]

This relates to Euler problem 303. Enumerate in increasing order, the
numbers that can be written in base 10 using just the digits 0, 1, and 2.

: r ( n -- n ) 3 /mod dup if recurse 10 * + else drop then ;
: test ( -- ) 50 0 do i r . loop ;

[Mark Wills]

Hi,

Yes. I understand RECURSE - I've implemented it in TurboForth and it
works just fine. I was just looking for some example code to post on
my web site. I've posted a write-up on my web site about the local
variable code that I developed, as I consider it will be useful for
users of my Forth system (the vast majority of them are total
beginners).

I wanted to demonstrate that when recursing using RECURSE, each
*instance* has its own set of local variables.

See http://turboforth.net/locals.htm

Mark

[Hugh Aguilar]

I have two versions of HANOI --- one with locals and one without ---
HANOI is a very easy example that "total beginners" should be able to
grasp.

[Albert van der Horst]

In article <0411f347-b5ae-46ab...@f5g2000vbt.googlegroups.com>,

Mark Wills <markrob...@yahoo.co.uk> wrote:
>Does anyone have any simple examples of recursion using RECURSE?

You can look at benchpin.frt at my website below for a simple
example where recursion is essential.
(Or go via numbertheory.html on my site below.)

>Preferably something where one can see the 'un-winding' as each
>instance exits.

You can add .S at the right place if you want a visible record.

>
>Thanks
>
>Mark

Groetjes Albert

--
--
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst

[Andrew Haley]

Surely for a recursion exaple to be meaningful it has to be something
that actually requires backtracking, such as a tree walk. This
example is better done with a loop:

: test 3 base ! 50 0 do i . loop ;

Andrew.

[Anton Ertl]

Andrew Haley <andr...@littlepinkcloud.invalid> writes:

>Paul Rubin <no.e...@nospam.invalid> wrote:
>> This relates to Euler problem 303. Enumerate in increasing order, the
>> numbers that can be written in base 10 using just the digits 0, 1, and 2.
>>
>> : r ( n -- n ) 3 /mod dup if recurse 10 * + else drop then ;
>> : test ( -- ) 50 0 do i r . loop ;
>
>Surely for a recursion exaple to be meaningful it has to be something
>that actually requires backtracking, such as a tree walk. This
>example is better done with a loop:
>
>: test 3 base ! 50 0 do i . loop ;

If you want just the printout, that's a solution, but in Euler303 you
want to do something else with the numbers; note the "in base 10" in
the partial problem statement above.

I used BASE, <# #s #> and >number to do this part, but my code is not
smaller (and probably slower), so one can argue that recursion is used
productively here.

- anton
--
M. Anton Ertl http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
New standard: http://www.forth200x.org/forth200x.html
EuroForth 2011: http://www.euroforth.org/ef11/

[P.M.Lawrence]

When locals aren't readily available and I need them (rare), I do a
quick and dirty "roll your own" by first setting up the variables as
globals, say X and Y, and then making them act like locals with
wrapper code in the calling secondary like this:-

X @ >R Y @ >R ( explicitly stacking former values on the return
stack )
... ( code using X and Y as if they were locals )
R> Y ! R> X ! ( carefully matching unstacking the former values to
their stacking, and making sure the return stack is left correct )

It's very important to comment the wrapper code!

This isn't precisely the same as true local variables, since only the
variables' contents work like that. Pointers to the variables don't
stay pointing at older/outer values, so achieving that would need
another layer of indirection. That usually isn't important as long as
you understand what is happening, and doing that is awkward enough
that it's probably worth setting up a proper local variable system
instead if you do need proper local behaviour.

Maybe you could use this approach in your examples since it makes it
fairly clear how the values are getting stacked and unstacked to work
like locals (fresh instances). Then you could say that using proper
locals automates that and puts it behind the scenes, and also clears
away any issues with indirect referencing of outer values (assuming
your implementation does!). P.M.Lawrence.

[Ian Osgood]

Agreed. Rosetta Code also has versions with and without locals.

http://rosettacode.org/wiki/Towers_of_Hanoi#Forth

Some of the other examples under Category:Recursion might also be of
interest, such as merge sort and quick sort.

Ian

[Hugh Aguilar]

The Hanoi problem is a good demonstration of recursion. The student
can visualize himself physically moving the disks from one peg to
another. Numeric problems are too abstract. Way back in maybe 1984 I
wrote an article for "Computer Languages" magazine describing the
Hanoi problem. I think I provided both Forth and BASIC code. I don't
remember the issue date, but it was the issue with interviews of Knuth
and Wirth.

All of the Forth code in that rosettacode website is ugly. Who wrote
that stuff?

I have QuickSort in the novice package. My default is HeapSort though
--- a big part of why I chose HeapSort is that I could avoid messing
with recursion this way. Notice how I use MACRO: for the sub-
functions, and they access the local variables in the calling
function. This lets me use locals rather than globals, which makes the
whole thing reentrant, but I don't have to reinitialize the locals
repeatedly as I would in a recursive function --- so I get reentrancy
*and* efficiency. This is one of many examples of code in the novice
package that was originally written using global variables (which
helps for testing), and then upgraded to use MACRO: and local
variables after I had it working.

Mostly though, I like HeapSort because it has very little variance in
how long it takes to run. QuickSort varies a lot depending upon how
ordered the data is initially. This is worthwhile in the novice
package because it could be used by anybody on any data --- I have no
way of predicting what the data will look like. If you do know what
the data will look like, it might be possible to chose a better
algorithm (such as the BucketSort, which is very fast but can only be
used with certain kinds of data).

The advantage of QuickSort is primarily that it is so simple that it
can be memorized (by comparison, I have to look up HeapSort every time
that I implement it) --- QuickSort is worthwhile to memorize, as
writing a sort function on the blackboard is a typical job-interview
task --- you would look pretty novice if the only sort algorithm
you've memorized is the BubbleSort. LOL It is all nonsense though,
because memorizing algorithms isn't a part of any computer programming
job. Real programmers have libraries of this stuff available --- you
don't actually stop in the middle of writing your application program
to figure out sort algorithms.