BrainFuck part 11 - Iterative and recursive ways

DPAmar
8,336 views

Open Source Your Knowledge, Become a Contributor

Technology knowledge has to be shared and made accessible for free. Join the movement.

Create Content

Tail recursive solution

First solution was definitely iterative : we built N! by building all X! values for X = 1..N

Second solution was defintely recursive : we built N! from the result of (N-1)!

But there is a specific kind of recursive way, called tail-recursive. In the previous example, there was a stack of all possible values for N. Although it's pointless when we talk about BF, for other languages it means a virtually very very very long stack of integers, that can lead to some memory issue...

The tail-recursive way is a specific recursion where the call to the sub-problem is the only operation done in the recursive process.

  • F(N) = F(N-1) x N is definitely not tail-recursive
  • F(N) = N x F(N-1) isn't, either : after calling F(N-1) there is still a multiplication

It seems impossible to write a tail-recursive definition of factorial, doesn't it?

Actually, it is indeed impossible to define this exact function F in a tail-recursive manner. However, we can define another function F':

  • F'(N,R) = F'(N-1,R*N)
  • F(N) = F'(N,1)

The main advantage of this implementation is that it doesn't add more and more frames to the stack. Instead :

  • we have a state (N,R)
  • we apply the same method on our state again and again until we reach a given condition
  • final state gives us a result

This recursion pattern is often optimized by compilers. It's also a very efficient way to handle recursions in BF

  • It doesn't force us to add more and more values on the stack
  • It does not need a real "function" or "subroutine" definition: with BF we can easily apply the same method on a given state again and again (as long as a flag is set on our state to indicate whether we should continue or not).

Actually, tail-recursive way can be considered as a recursion implemented with a similar technique than the iterative way: for (state=...;state not final;) state=F(state). But again, the philosophy behind is different : we compute the result based on results for smaller inputs, and not iteratively

Let's start

  • Memory: N 0 0 0 0 0
  • Cursor: first cell
  • Input: any

Process

  • Set result to 1 (2nd cell)
  • invariant: memory is A, B with A! x B = N!
  • while A is not null
    • decrease A
    • copy "A-1"
    • multiply B by A-1
    • add Bx(A-1) to B to get AxB
  • loop
  • A = 0, so B = N!

Code

>+<                            Set result to 1
[                              while A is not null
  -[->>+>+<<<]>>>[-<<<+>>>]<   decrease and copy A
  [-<[->>+>+<<<]>>[-<<+>>]<]   get AxB
  >>[-<<<+>>>]                   ** part 2 **
<<<<]                          loop
  

Minified version

>+<[-[->>+>+<<<]>>>[-<<<+>>>]<[-<[->>+>+<<<]>>[-<<+>>]<]>>[-<<<+>>>]<<<<]

Final state

  • Memory: 0 N! 0 0 0 0
  • Cursor: first cell
  • Input: unchanged
  • Output: unchanged

Test program

This programs prints x, code 120 = 5!

+++++>+<[-[->>+>+<<<]>>>[-<<<+>>>]<[-<[->>+>+<<<]>>[-<<+>>]<]>>[-<<<+>>>]<<<<]>.
Open Source Your Knowledge: become a Contributor and help others learn. Create New Content