Example of a recursive function in brainfuck

Question

Straight to the point - I've been learning brainfuck, but I'm having trouble getting round the idea of recursion in it. I've googled for this and searched the forums - so apologies in advance if needed - and come up with nothing.

First of all, is it actually possible?

If so, are there any examples? I'll add in anything useful I can come up with.

I'm specifically trying to work out the Fibonacci numbers using recursion, so it'd help a lot if we could base it on that.

Answer 1

Since BF doesn't really offer anything other than a tape and a pointer and VERY basic looping capabilities (typically you need to ensure that the pointer ends up in the same place as it started, what are called balanced loops. In rare cases you can do loops without them being balanced such as arrays), it is quite difficult to implement recursive algorithms in it. You may try to simulate a "normal" computer in bf (it all depends on how you treat the tape). I believe the C2BF project works this way (it compiles C to brainfuck). If I'm not mistaken they treat groups of cells in alternating pairs of stack/heap (making certain pointer operations a bit different, since everything has to be multiplied by 2)

So, after all this text here's my conclusion: It IS possible to implement recursive algorithms in brainfuck although it is really difficult. What I urge you to remember is that every recursive algorithm can be done iteratively. You just have to maintain your own stack. This is actually what you will end up doing anyway if you want to implement it recursively. But if you think about it as being iterative and maintaining your own stack, instead of recursive, it will help you understand what you are actually doing and ultimately result in a better designed algorithm.

Answer 2

UPDATE: I have implemented such a thing. https://github.com/benrap/Assembly2Brainfuck

Original message:

I've yet to implement such a thing, but I will update once I will. However, I've thought of an implementation of a true recursive function. First notice that brainfuck runs code only in one direction, so we can't actually use the code storage for recursion. The only other means of storage we have is the storage the code is changing. So in fact, we must write code to save our function on storage, and then read that storage WITHOUT CHANGING IT and execute it accordingly. This in turn will require a stack and some more complicated stuff.

As I said I plan on making such an implementation, so once I have a working prototype I will update. Hopefully my answer so is sufficient.

Answer 3

Standard Brainfuck has neither calls nor a call stack, so you must implement your own stack in order to do recursive programming.

The two-dimensional language SNUSP has the same operators and memory model as Brainfuck, but adds a call stack and ENTER ("@") and LEAVE ("#") instructions, allowing for recursive programming. Brainfuck's brackets for looping are replaced with reflectors ("\", "/"), skip ("!") and skip-if-zero ("?"). For example, here is a recursive implementation of the Fibonacci function:

             /========\    />>+<<-\  />+<-\
fib==!/?!\-?!\->+>+<<?/>>-@\=====?/<@\===?/<#
      |  #+==/     fib(n-2)|+fib(n-1)|
      \=====recursion======/!========/