Recursion vs iteration: compute factorial

Context

There are two ways to deal with loops in computer science: the recursive way and the iterative way.

• Recursion: a function that contains calls to itself, creating a loop through nested calls
• Iteration: do something until a condition is met

Both have pros and cons.

Using recursion, it's generally easier to prove algorithm validity by induction: if you can prove that your result is correct for smallest input possible, and that having a valid result for an input N implies a valid result for N+1, then your algorithm is valid for any input.

But recursion also implies to carefully watch at the memory stack: each recursive call uses memory, and you may reach a 'stack overflow' after too many recursive calls...

Using iterations, you can do something a given number of times, not necessarily using more memory on each loop. Validity can be proven as well, but using an invariant that might be complex to find.

In BrainFuck however, there are no functions, so how can we use recursive calls?

It actually requires to understand one of the key points of recursion: what happens when you have something like

function F(n)
  do something
  F(n')
  do something

Calling function F (any function actually) will

• Push on stack some details about the returning point
• Push also function parameters
• Then execute code

In BrainFuck, we can easily do something similar.

Let's implement the factorial function, denoted by n! = product of all integers from 1 to n.

• The iterative definition of this function is n! = 1 * 2 * 3 ... * n
• The recursive definition is n! = n * (n-1)!, with 0! = 1

Note: as factorial grows faster than any polynomial or exponential function, we may reach integer limit pretty quickly. Actually, BrainFuck uses memory cells valued from 0 to 255, modulo 256, so:

• 5! is the biggest integer we may have (120)
• 6!, 7!, 8!, 9! will be computed modulo 256
• 10! is divisible by 256, so any n! mod 256 with n ≥ 10 will be 0

Therefore, there is no need to read complex integers in our algorithms. A single digit is enough

Initial state

• Memory: empty
• Cursor: first cell
• Input: one char

Process

• Read character, convert to integer (-48). This would be n
• Iterative way
• Set a cell to 1 (this would be our result)
• While n is not null
• Decrease n
• Increase the cell besides (let's call it j)
• Multiply our result by j
• Loop invariant: result equals j! and n+j = initial value of n
• When n is null, then j = initial n, and result = initial n!
• Recursive way
• While current cell is not null
• Copy value 2 cells on the right
• Decrease copy by 1, and stay on this copy
• Move to left, set result to 1, move to left
• While current cell is not null
• multiply this value with the next cell's one
• store result on the previous cell
• move 2 cells on the left compared to the original position

Note: the recursive algorithm is a bit harder to understand. We will

• Generate a memory that looks like n 0 n-1 0 n-2 0 ... 2 0 1 0 0
• Then, set the red cell to 1 : ... 2 0 1 1 0
• Multiply 1 by 1 and store the result after 2 : ... 3 0 2 1 0 0 0
• Multiply 2 by 1 and store the result after 3 : ... 4 0 3 2 0 0 0 0 0
• Multiply 3 by 2, and so on...

Code (iterative version) - try it

read n
,>++++++++[-<------>]
set result to 1
>>>+<<<<
while n is not null
[
  decrease n and increase j by one
  ->+
  copy current value of j
  [->+>+<<]>[-<+>]>
  multiply current result by j
  -[->[->+>+<<]>[-<+>]<<]>>>[-<<+>>]<<<
  go back to n and loop
<<<]

Code (recursive version) - try it

read n (leave some free space to stop the final loop)
>>,>++++++++[-<------>]
generate all integers from n to 0 separated by 0
<[[->+>+<<]>[-<+>]>-]
set result to 1 and move to integer '1'
<+<
While current integer is not null
[
  multiply result by current integer
  [->[->+>+<<]>[-<+>]<<]
  store result at its new location (and reset temporary cells)
  >>>[-<<<<+>>>>]<<[-]<
  go to previous integer in the stack
<<]

Final state 

• Memory : 
• Iterative method: 0 n 0 0 n!
• Recursive method: 0 n! 0 0 
• Pointer: first cell (in both cases)
• Input: one character read
• Output: unchanged