# 6.1.2120RECURSECORE

## 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>.

## 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

## enoch[9] 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.

### AntonErtl[r5] 2015-12-15 13:19:28

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
;
``````

### enoch[r6] 2015-12-15 15:52:07

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 ...

### ruv[r7] 2015-12-30 19:14:02

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.

### enoch[r9] 2016-01-06 23:00:24

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.

### ruv[r176] 2018-08-16 11:23:47

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

### ruv[r177] 2018-08-16 11:32:01

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.

## Blackice[125] 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?

### AntonErtl[r342] 2020-01-10 09:49:12

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.

### massung[r343] 2020-01-11 01:25:34

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.

### PeterKnaggs[r344] 2020-01-11 10:35:06

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.

### ruv[r354] 2020-02-07 15:05:02

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.

### GeraldWodni[r466] 2020-09-02 15:28:08

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

## JohanKotlinski[288] Tail call eliminationComment2023-02-21 06:27:11

Wouldn't it be nice if the standard guaranteed tail call elimination, like in Scheme and other languages?

### AntonErtl[r975] 2023-02-22 10:32:42

Programs could use tail-recursion instead of loops.

Concerning the performance advantage of tail-call elimination, there is no need to standardize tail-call elimination for individual systems to reap this benefit. Also, the standard does not specify any performance guarantees.

Backtraces would not contain all calls in a call chain. Forth systems that do not perform tail-call elimination now would have to be rewritten (unless this feature was made optional, but then the advantage would vanish).

## Existing practice

Many Forth systems do not perform tail-call elimination.

Several Forth systems, in particular SwiftForth and colorForth perform tail-call elimination, although I don't know of any guarantees. AFAIK colorForth programs are written to perform tail-recursion instead of loops, but I doubt that there is any SwiftForth-specific program that requires this feature (well, maybe some return-address manipulating programs that were written to take the return-stack behaviour of SwiftForth in consideration; but such programs are non-standard either way). Recursion seems to be not very popular among Forth programmers.

I expect that the committee sees things like I discussed them above, so I am closing this comment. If you want consideration from the whole committee, please reopen it.

Closed

### StephenPelc[r976] 2023-02-22 10:38:33

Guaranteeing tail call elimination would be a disaster. Any word that manipulates the return stack cannot be eliminated. Identifying such words automagically is non-trivial.

``````: jmp >r ;

: (.")  r> count  2dup + >r  type  ;
``````

Now introduce a word further up that adjusts the return stack.

``````: (.")  ((")) type  ;
``````

Stephen

### AntonErtl[r977] 2023-02-22 18:23:36

A program that performs return-address manipulation like your examples is not a standard program. So any guarantees the standard might give would not apply to these programs.

Nonetheless, I expect that you have legacy return-address manipulating programs that expect no tail-call elimination. Automatically covering both these legacy programs and hypothetical standard programs that require tail-call elimination would be a challenge (depending on how the guarantee was specified). But it would be possible to cover both with a manual switch.

BTW, the use of return-address manipulation for implementing locals results in VFX 5.11 being slower than lxf by more than a factor of four on sendmore.fth. I understand why you want to support legacy programs that use such techniques, but it's unclear why you still use it internally.

### ruv[r978] 2023-02-23 11:29:51

Programs could use tail-recursion instead of loops.

Yes, and it's the only advantage on the source code level.

I employed a kind of loop, which just jumps to the begin of the word. It can be used in any place where `exit` can be used, and semantically it's equivalent to tail-recursion `recurse exit`. Such a loop can be easily implemented (with some limitations — even in a standard program), and it does not break anything.

A practical result is that in some cases definitions become shorter.

An example: a word that returns the next value (a string) from the current SQL query, having multiple result sets.

``````: next-value ( -- sd.value | 0 0 )
res if
row if
next-col? if
get-value
exit
then
then
next-row? if itself-again then
then
next-result? if itself-again then
0.
;
``````

NB: the word `next-value` is defined in a local namespace, so names are so short. Obviously, `recurse exit` can be used in place of `itself-again`.

But it would be possible to cover both with a manual switch.

SP-Forth/4 has such a switch, which turn on tail call elimination. By default it's turned off, since in some cases incorrect code is still produced.

Of course tail call elimination cannot be required by the standard since it's difficult to implement, and sometimes it's even impossible to implement without changing the format of generated code (e.g. in case of generating asmjs).

### AntonErtl[r979] 2023-02-23 16:09:25

Standard Forth cannot be implemented to generate asm.js as is, because asm.js does not support run-time code generation (at least that's what a student reported who was interested in a project with that topic). Should we destandardize `POSTPONE`, `COMPILE,` etc. because of that? Of course, you can still implement a Forth interpreter in asm.js and such an interpreter can support tail-call elimination.

In any case, hypothetical implementations are a weak reason for non-standardization. If you have a particular asm.js-based implementation in mind, please provide a pointer.

### JohanKotlinski[r990] 2023-02-24 19:42:45

Hi, sorry for being unclear! I certainly did not mean that there should be a general guarantee of tail-call elimination.

What I meant, `RECURSE ;` and `RECURSE EXIT` could guarantee tail-call elimination.

I realize that it is a bold proposal. But it would make `RECURSE` way more useful, to allow recursive code without stack-overflow.