recursion (was: exercise in double number arithmetic)

minforth@gmx.net (minforth) writes:

On Mon, 15 Jul 2024 10:41:54 +0000, albert@spenarnc.xs4all.nl wrote:

So I prefer:
>
:F binom ;
>
:R binom  ( n1 n2 -- nd ) \ n k --> C(n,k)
  dup 0=
  IF     2drop 1 s>d
  ELSE   2dup 1- swap 1- swap binom 2swap m*/
  THEN ;
>
In my efforts to Make A Lisp (a github https://github.com/kanaka/mal )
I discovered that using recurse is an ugly cludge that present
a lot of problems in refactoring code, if not prevent it.
Forward and resolve definitions is the more sane method, cf. c.
It is hardly more complicated.

>
IIRC gforth has RECURSIVE to avoid duplicating definitions.

Yes.  So for a direct recursion like this one you can write

: binom  ( n1 n2 -- nd ) recursive \ n k --> C(n,k)
  dup 0=
  IF     2drop 1 s>d
  ELSE   2dup 1- swap 1- swap binom 2swap m*/
  THEN ;

RECURSIVE also allows you to tick the word in its own definition (not
possible with RECURSE), a feature that I actually have used; something
along the lines:

: walk ( node -- ) recursive
  dup is-leaf? if
    ... \ do something for the leaf
  else \ the node has subnodes
    node ['] walk for-each-subnode
  then ;

Gforth (development) also has FORWARD, which also allows you to do
mutual recursion, e.g.

forward foo

: bar ( n -- ) dup . 1- foo ;

: foo ( n -- ) dup 0> if bar else drop then ;

5 foo \ prints "5 4 3 2 1 "

let's see what the decompiler says:

simple-see foo
$7F54E256E870 dup    0->0
$7F54E256E878 0>    0->0
$7F54E256E880 ?branch    0->0
$7F54E256E888 <foo+$40>
$7F54E256E890 call    0->0
$7F54E256E898 bar
$7F54E256E8A0 branch    0->0
$7F54E256E8A8 <foo+$48>
$7F54E256E8B0 drop    0->0
$7F54E256E8B8 ;s    0->0  ok
simple-see bar
$7F54E256E810 dup    0->0
$7F54E256E818 call    0->0
$7F54E256E820 .
$7F54E256E828 1-    0->0
$7F54E256E830 call    0->0
$7F54E256E838 foo
$7F54E256E840 ;s    0->0  ok

$7F54E256E838 @ hex. \ prints $7F54E256E870

The last like shows that the call to FOO inside BAR directly calls the
FOO defined above, no DEFER or somesuch involved in this case.

The definition of FORWARD is quite intricate and uses several recent
features of Gforth.  Read all about it in
<2018Dec31.161743@mips.complang.tuwien.ac.at>.

- 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: https://forth-standard.org/
   EuroForth 2024: https://euro.theforth.net