Recur

Recur is an esoteric programming language created by User:D, inspired by Iteration can replace Recursion?. Instead of using an implicit call stack, the language requires users to handle the call stack manually.

Inspiration

The inspiration was rather mixed. The design was mainly based on the following OISC:

s1: if x = b, x := c; goto s2

Also, there was an answer saying the following:

You do not need recursion, and as you suggest, and as confirmed by Dave Clarke's answer, you only need conditionals, loops and memory allocation and assignment.

After reading most of the answers in Iteration can replace Recursion?, I added infinite loops, conditional breaks, "register" pushing/popping and built all of that onto the call stack typically used to implement recursion. Resulting in this language.

Commands

If there aren't enough stack items to perform the operation, then the operation is a NOP. (An exception is the , command, as specified below.)

• 123: Push the natural number (includes 0) onto the stack. (There is an infinite number of natural numbers.)
• s: Successor function: Pops a, pushes a+1.
• ,: Pops a and v. Store a to the variable numbered v. (If there is no a on the stack, break out of the [ ... ] loop.)
• !: Pops v. Push the value of the variable numbered v onto the stack.
• [ ... ]: Infinite loop: Executes ... forever.
• =: Pops a and b. If a and b are equal, break out of the [ ... ] loop.

Examples

Predecessor function

Expects a value on the top of the stack. Wouldn't work for input = 0 (which will loop forever).

0,
0 1,
1 2,
[ 2! 0! =
  1! s 1,
  2! s 2,
] 1!

Minified & golfed:

0,0 1 2,[2!0!=s2!s2,]

Double the number

1,0 0 2,[2!1!=ss2!s2,]

Ackermann function

I've used m, n and r in place of the actual numbers to avoid confusing myself.

[ n,m,
  [ n! s
    m! 0=
    r,

    0 1 r,
    [ r! m! =
      s
      r! s r,]
    1
    n! 0=

    r, m!
    0 1 r,
    [ r! n! =
      s
      r! s r,]
    0 0 =
  ]
]

Computational Class

Recur is Turing-complete. To demonstrate this, here is a translation from brainfuck with unbounded cells.

0 represents the tape head, 1 is a scratchpad used for the - operation.

Program setup:
2 0,

>:
0! s 0,

<:
1 1,
0 [1! 0! = s 1! s 1,]
0,

+:
0!! s 0! ,

-:
1 1,
0 [1! 0!! = s 1! s 1,]
0! ,

[:
[ 0!! 0 =

]:
]

External Resources

• Interpreter/Debugger written in Python

See also

• Rec