RECURSE

Interpretation:

Interpretation semantics for this word are undefined.

Compilation:

( -- )

Append the execution semantics of the current definition to the current definition. An ambiguous condition exists if RECURSE appears in a definition after DOES>.

See:

Rationale:

Typical use: : X ... RECURSE ... ;

This is Forth's recursion operator; in some implementations it is called MYSELF. The usual example is the coding of the factorial function.

: FACTORIAL ( +n1 -- +n2)
   DUP 2 < IF DROP 1 EXIT THEN
   DUP 1- RECURSE *
;

n2 = n1(n1-1)(n1-2)...(2)(1), the product of n1 with all positive integers less than itself (as a special case, zero factorial equals one). While beloved of computer scientists, recursion makes unusually heavy use of both stacks and should therefore be used with caution. See alternate definition in A.6.1.2140 REPEAT.

Testing:

T{ : GI6 ( N -- 0,1,..N ) 
     DUP IF DUP >R 1- RECURSE R> THEN ; -> }T

T{ 0 GI6 -> 0 }T
T{ 1 GI6 -> 0 1 }T
T{ 2 GI6 -> 0 1 2 }T
T{ 3 GI6 -> 0 1 2 3 }T
T{ 4 GI6 -> 0 1 2 3 4 }T

DECIMAL
T{ :NONAME ( n -- 0, 1, .., n ) 
     DUP IF DUP >R 1- RECURSE R> THEN 
   ; 
   CONSTANT rn1 -> }T

T{ 0 rn1 EXECUTE -> 0 }T
T{ 4 rn1 EXECUTE -> 0 1 2 3 4 }T

:NONAME ( n -- n1 )
   1- DUP
   CASE 0 OF EXIT ENDOF
     1 OF 11 SWAP RECURSE ENDOF
     2 OF 22 SWAP RECURSE ENDOF
     3 OF 33 SWAP RECURSE ENDOF
     DROP ABS RECURSE EXIT
   ENDCASE
; CONSTANT rn2

T{  1 rn2 EXECUTE -> 0 }T
T{  2 rn2 EXECUTE -> 11 0 }T
T{  4 rn2 EXECUTE -> 33 22 11 0 }T
T{ 25 rn2 EXECUTE -> 33 22 11 0 }T

ContributeContributions

enochavatar of enoch proposal: recurse' to complement recurseComment2015-12-03 23:46:08

recurse' is just like recurse but returns an XT instead of calling. It is being implemented in amforth-shadow and is mainly used by words to reschedule themselves for execution after a desired delay. A trivial example:

: every-1000ms
  ." do something" cr
  1000 0 recurse' enlist  if  ." enlist error" cr  then
;

I hope what "enlist" does can easily be guessed. If not visit my github repository :-)

Thanks, Enoch.

AntonErtlavatar of AntonErtl

Gforth has RECURSIVE, which can be used for this purpose; e.g., your example would become:

: every-1000ms recursive \ <-- makes EVERY-1000ms visible
  ." do something" cr
  1000 0 ['] every-1000ms enlist  if  ." enlist error" cr  then
;

enochavatar of enoch

recurse (and therefore its absent recurse' counterpart) does have a right to exist, cf. :noname and [: quotations ;] I don't like Gforth recursive declaration... it should be called "revealed" or something similar, if at all ...

ruvavatar of ruv

IMO, recurse' is not good enough name due to use of tick (it is better to avoid special chars in names for regular words). I can suggest the name itself for such word.

enochavatar of enoch

The use of tick ', sharp #, etc. is encouraged by the Forth Programmer’s Handbook -- Table 15: Naming conventions. We should minimize the number of names to remember thus, I would have no problem if recurse is renamed itself and completed by **itself', but that's not an option for historical reasons.

ruvavatar of ruv

In the light of recognizers it is better to leave the special characters for various literals and the like.

ruvavatar of ruv

Also, itself is not directly connected with recursion — it can be returned as result or compiled into another definition.

: tt  ... if  ... lit, itself compile, ... then ... ;

It is one real usage case.

Reply New Version

Blackiceavatar of Blackice Why RECURSE is needed?Request for clarification2020-01-09 21:15:01

: FACTORIAL ( +n1 -- +n2 ) DUP 2 < IF DROP 1 EXIT THEN DUP 1- FACTORIAL * ; After the execution of the ":" the word FACTORIAL is defined in the vocabulary and available for FIND. Even as incomplete definition, nothing prevents to compile the call to itself. Why special word is needed?

AntonErtlavatar of AntonErtl

See the specification of : :

The current definition shall not be findable in the dictionary until it is ended

So your FACTORIAL does not work in standard Forth. That's why Forth has RECURSE.

Why are colon definitions only visible later? 1) If you make an error, resulting in an incomplete definition, this protects you from calling it. 2) You can define words with the same name, and extended behaviour that calls a previous word with the same name.

massungavatar of massung

There is a reason why it's not findable in the dictionary, and it's a feature: it allows you to extend existing words in the dictionary be referencing the old behavior without having to know the original code. For example:

: dup ." Duplicating " dup . cr dup ;

I don't need to know how DUP is implemented, but I just extended it so that future uses of DUP will output to the console that it was called. Additionally, it doesn't affect the original behavior, which other code is using; it only impacts new uses, meaning there's no chance of damaging existing, working code.

PeterKnaggsavatar of PeterKnaggs

Your assumption is invalid. Although the dictionary entry for FACTORIAL is indeed defined when : (colon) is executed, the definition is "smudged" so that it is not available to FIND and friends. Thus using FACTORIAL will execute a previous definition of FACTORIAL rather than starting the current definition again. The when ; (semi-colon) is executed it removes the smudge from the dictionary entry, making the new definition of FACTORIAL viable. Thus to direct execution back to the start of the current definition you must use RECURSE.

ruvavatar of ruv

It is important to add that creating and "smudging" a dictionary entry by Colon ":" is only one of several possible ways of implementing the requirements. All these details, such as a dictionary entry and smudging, are under the hood and not available for a standard program.

GeraldWodniavatar of GeraldWodni

This his been discussed by the TC and we deem the replies above by Anton Ertl and Peter Knaggs to clarify the question.

As to smudging: this is not used in the standard any more.

Closed
Reply New Version