Tail Recursion

Normally a call to a function in an expression, in M2000, pass a new stack with values, and a Read statement read these values. We can define a type and a number, on just a number if it is double, for some arguments, as the default value, so when the Read statement define the variable, and there is no value in stack, then assign the default value.

This is an example which we use a Restart at the end of function, to call the function body. the parameter list convert to a Read statement, so the actual function body has one more line for these functions. (one function has the parameter list with as space after the name, this is the same without the space).
The second call, using restart, has to use a proper feeding

\\ Factorial tail Recursion
Function TailRecursion (x, z as decimal=1){ 
        z*=x
        If x<=1 Then =z: Exit
        Push z, x-1  ' fix stack
        Restart  ' call again
}
Print TailRecursion(10), TailRecursion(5)
Print TailRecursion(1), TailRecursion(20)
\\ Fibonacci tail recursion
Function fibTailRecursion(x, f0 as decimal=0, f1 as decimal=1) {
        If x<=1 Then =f0: Exit
        Push  f0+f1,f1,x-1
        Restart
}
For i=1 to 134
        Print fibTailRecursion(i), i
Next

We can use stack to save multiple results. The statement shift 1,-stack.size reverse the order of stack items. So now the Push statement push another value, which stay to stack, and because the last value push to top (we say at position 1 of stack items), we have to reverse the items. The [] is a keyword, an identifier which tell to interpreter to return the pointer to current stack, and leave an empty stack as the current stack, so we move the current stack to return value. Variable z now is a pointer to a stack object. The print statement when get a container type object like array, pointer to array, stack and inventory (a kind of vector) make a local iterator and print each item in separate column, and change row if needed. Only strings and numbers renderer to screen, and objects types are rendered as a space. So print statement leave an empty column, in current row, and advance to next column and or next row.

Function fibTailRecursionStack(x, f0 as decimal=0, f1 as decimal=1) {
        Push f0
        If x<1 Then Shift 1,-Stack.size : =[]: Exit
        Push  f0+f1,f1,x-1
        Restart
}
Z=fibTailRecursionStack(10)
Print Z
For i=0 to 5
        Print fibTailRecursionStack(i)
Next

We can use a lambda function too. The function part is the same. We have no closures here.
 

fibTailRecursionStack=lambda (x, f0 as decimal=0, f1 as decimal=1)-> {
        Push f0
        If x<1 Then Shift 1,-Stack.size : =[]: Exit
        Push  f0+f1,f1,x-1
        Restart
}
Z=fibTailRecursionStack(10)
Print Z
For i=0 to 5
        Print fibTailRecursionStack(i)
Next

Because M2000 is an interpreter. a function call is more than one function call in machine code. If name of functions has $ then a call to a function for string function called first. This function find the function by the name in a Hash Object, a fast way to find the code of function. Then a new execution object prepared, then parameters processed and placed in a new stack object, and then the function called passed the process object and the function's reference. The code from function's reference "loaded" in a string and passed to execution. If a restart happen then the code loaded again.

 We can separate the f0 and f1 parameters from parameter list using a second lambda, inside the fibtailRecursionStack. Now we call two functions, but the second one using the Call statement. A call statement pass the same stack of values, because is a call of the function like it is a module. Before the call we do a flush to stack (so stack start as an empty). We pass only the x in the call to fibaux function. I another implementation we can check if the x is valid for the calling. The Fibaux has no return value, all values stay at stack, at the exit.

If we want to get the first 5 items (including 0) we call Fibaux with x-1
 Or if we want to drop 0 then before exit we insert a Drop statement without a value (is same as Drop 1). so the statement change to
 If x<1 then Shift 1,-Stack.Size: Drop:Exit

Fibaux=lambda  (x, f0 as decimal=0, f1 as decimal=1) -> {
        Push f0
        If x<1 Then Shift 1,-Stack.size : Exit
        Push f0+f1,f1,x-1
        Restart
}
fibTailRecursionStack=lambda Fibaux (x)->{
        Flush
        Call Fibaux(x)
        =[]
}
Z=fibTailRecursionStack(5)
Print Z

 About stack statements DROP, SHIFT, SHIFTBACK, OVER, PUSH, DATA, FLUSH
The flush statement leave an empty the stack. The Push statement push a value to stack at the top. A Push 1,2,3 push all values to the top, so 3 is the new top. A Drop statement is same like Drop 1, which drop 1 item from the top. So a Frop1 leave stack with 2 the new top, and 3 after it. An Over 2 make a copy of 3 to new top (internal is an indirect copy, we copy the pointer which point to 3). An Shift 3 shift the third item to position 1. A ShiftBack 3 send the top after the current third item, so the third item became the second one. Data push items to end of stack. Variable Empty is true if stack is empty. Also Stack.Size return the size in items of stack. SHIFT, SHIFTBACK and OVER get a second parameter, the repeat factor. This factor if is negative then change the behavior of statement Shift and ShiftBack.

Flush
Data 1,2,3,4
Stack' display the Stack in console1 2 3 4
Shift 3,-2
Stack ' 4 3 1 2
Over 3, 2
Stack' 3 1 4 3 1 2
Shift 3, 2
Stack'4 3 3 1 1 2
Over 1, 4 
Stack ' 4 4 4 4 4 3 3 1 1 2
Push Number+1
Stack ' 5 4 4 4 4 3 3 1 1 2
Shift Stack.size-5,-2
Stack ' 3 4 5 4 4 4 3 1 1 2 
Shift Stack.size-1,2
Stack ' 1 2 3 4 5 4 4 4 3 1
Shift 1,-4
Stack' 4 3 2 1 5 4 4 4 3 1
ShiftBack stack.size-3, -stack.size
Stack '5 4 4 4 3 1 1 2 3 4
Drop 6
Stack ' 1 2 3 4
ShiftBack 3,2
Stack ' 3 4 1 2
Shift3, 2    ' reverse of ShiftBack 3, 2
Stack ' 1 2 3 4