Open Source Your Knowledge, Become a Contributor
Technology knowledge has to be shared and made accessible for free. Join the movement.
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
- Memory: N 0 0 0 0 0
- Cursor: first cell
- Input: any
- 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
- A = 0, so B = N!
>+< Set result to 1 [ while A is not null -[->>+>+<<<]>>>[-<<<+>>>]< decrease and copy A [-<[->>+>+<<<]>>[-<<+>>]<] get AxB >>[-<<<+>>>] ** part 2 ** <<<<] loop
- Memory: 0 N! 0 0 0 0
- Cursor: first cell
- Input: unchanged
- Output: unchanged
This programs prints
x, code 120 = 5!