Implement recursion in ASM without procedures

Question

I'm trying to implement functions and recursion in an ASM-like simplified language that has no procedures. Only simple jumpz, jump, push, pop, add, mul type commands.

Here are the commands:
(all variables and literals are integers)

• set (sets the value of an already existing variable or declares and initializes a new variable) e.g. (set x 3)
• push (pushes a value onto the stack. can be a variable or an integer) e.g. (push 3) or (push x)
• pop (pops the stack into a variable) e.g. (pop x)
• add (adds the second argument to the first argument) e.g. (add x 1) or (add x y)
• mul (same as add but for multiplication)
• jump (jumps to a specific line of code) e.g. (jump 3) would jump to line 3 or (jump x) would jump to the line # equal to the value of x
• jumpz (jumps to a line number if the second argument is equal to zero) e.g. (jumpz 3 x) or (jumpz z x)

The variable 'IP' is the program counter and is equal to the line number of the current line of code being executed.

In this language, functions are blocks of code at the bottom of the program that are terminated by popping a value off the stack and jumping to that value. (using the stack as a call stack) Then the functions can be called anywhere else in the program by simply pushing the instruction pointer onto the stack and then jumping to the start of the function.

This works fine for non-recursive functions.

How could this be modified to handle recursion?

I've read that implementing recursion with a stack is a matter of pushing parameters and local variables onto the stack (and in this lower level case, also the instruction pointer I think)

I wouldn't be able to do something like x = f(n). To do this I'd have some variable y (that is also used in the body of f), set y equal to n, call f which assigns its "return value" to y and then jumps control back to where f was called from, where we then set x equal to y.

(a function that squares a number whose definition starts at line 36)

1 - set y 3
2 - set returnLine IP
3 - add returnLine 2
4 - push returnLine
5 - jump 36
6 - set x y
...
36 - mul y 2
37 - pop returnLine
38 - jump returnLine

This doesn't seem to lend itself to recursion. Arguments and intermediate values would need to go on the stack and I think multiple instances on the stack of the same address would result from recursive calls which is fine.

Answer 1

Next code raises the number "base" to the power "exponent" recursively in "John Smith Assembly":

1 - set base 2            ;RAISE 2 TO ...
2 - set exponent 4        ;... EXPONENT 4 (2^4=16).
3 - set result 1          ;MUST BE 1 IN ORDER TO MULTIPLY.
4 - set returnLine IP     ;IP = 4.
5 - add returnLine 4      ;RETURNLINE = 4+4.
6 - push returnLine       ;PUSH 8.
7 - jump 36               ;CALL FUNCTION.
.
.
.
;POWER FUNCTION.
36 - jumpz 43 exponent    ;FINISH IF EXPONENT IS ZERO.

37 - mul result base      ;RESULT = ( RESULT * BASE ).
38 - add exponent -1      ;RECURSIVE CONTROL VARIABLE.
39 - set returnLine IP    ;IP = 39.
40 - add returnLine 4     ;RETURN LINE = 39+4.
41 - push returnLine      ;PUSH 43.
42 - jump 36              ;RECURSIVE CALL.

43 - pop returnLine
44 - jump returnLine
;POWER END.

In order to test it, let's run it manually :

 LINE | BASE EXPONENT RESULT RETURNLINE STACK
------|---------------------------------------
   1  |   2
   2  |         4
   3  |                  1
   4  |                           4
   5  |                           8
   6  |                                   8
   7  |
  36  |
  37  |                  2
  38  |         3
  39  |                          39
  40  |                          43
  41  |                                  43(1)
  42  |
  36  |
  37  |                  4
  38  |         2
  39  |                          39
  40  |                          43
  41  |                                  43(2)
  42  |
  36  |
  37  |                  8
  38  |         1
  39  |                         39
  40  |                         43
  41  |                                  43(3)
  42  |
  36  |
  37  |                 16
  38  |         0
  39  |                         39
  40  |                         43
  41  |                                  43(4)
  42  |
  36  |
  43  |                         43(4)
  44  |
  43  |                         43(3)
  44  |
  43  |                         43(2)
  44  |
  43  |                         43(1)
  44  |
  43  |                          8
  44  |
   8  |

Edit : parameter for function now on stack (didn't run it manually) :

1 - set base 2            ;RAISE 2 TO ...
2 - set exponent 4        ;... EXPONENT 4 (2^4=16).
3 - set result 1          ;MUST BE 1 IN ORDER TO MULTIPLY.
4 - set returnLine IP     ;IP = 4.
5 - add returnLine 7      ;RETURNLINE = 4+7.
6 - push returnLine       ;PUSH 11.
7 - push base             ;FIRST PARAMETER.
8 - push result           ;SECOND PARAMETER.
9 - push exponent         ;THIRD PARAMETER.
10 - jump 36              ;FUNCTION CALL.
...
;POWER FUNCTION.
36 - pop exponent         ;THIRD PARAMETER.
37 - pop result           ;SECOND PARAMETER.
38 - pop base             ;FIRST PARAMETER.
39 - jumpz 49 exponent    ;FINISH IF EXPONENT IS ZERO.

40 - mul result base      ;RESULT = ( RESULT * BASE ).
41 - add exponent -1      ;RECURSIVE CONTROL VARIABLE.
42 - set returnLine IP    ;IP = 42.
43 - add returnLine 7     ;RETURN LINE = 42+7.
44 - push returnLine      ;PUSH 49.
45 - push base
46 - push result
47 - push exponent
48 - jump 36              ;RECURSIVE CALL.


49 - pop returnLine
50 - jump returnLine
;POWER END.