Iterative vs Recursive vs Tail-Recursive in Golang

4 min readJan 25, 2017

I’ve wrote a simple Fibonacci function in 3 different way (you can find the code here) :

Iterative :

// Iterative version of Fibonacci
func fiboI(n int) int {
 var result intfor i, first, second := 0, 0, 1; i <= n; i, first, second = i+1, first+second, first {
  if i == n {
   result = first
  }
 }return result
}

Recursive :

// Recursive version of Fibonacci
func fiboR(n int) int {
 if n < 2 {
  return n
 }
 return fiboR(n-2) + fiboR(n-1)
}

Tail-Recursive :

func fiboTail(n int) int {
 return fiboT(n, 0, 1)
}//Tail-recursive version of Fibonacci
func fiboT(n, first, second int) int {
 if n == 0 {
  return first
 }return fiboT(n-1, second, first+second)
}

Benchmark :

Benchmark_FibIterative_10-4     100000000               16.4 ns/op
Benchmark_FibTailRecursive_10-4  50000000               33.3 ns/op
Benchmark_FibRecursive_10-4       5000000                394 ns/op
PASS
ok      github.com/tkanos/recursion-test        5.735s

As expected The iterative is the faster running 100000000 times at a speed of 16.4 ns per loop.

But i’m wondering …

Why the recursive is so long ?

So are you ready to talk about stack frame, (it could be complex):D

The computer use a stack frame where it put all new function called.

Each time a function is called, internally the computer add a new block in the stack frame :

(remark : if we add to much functions (a infinite/or just to big recursive loop for example) will have a stack overflow))

The stack frame is used to “hold” the “state” of each functions .So for that it will store all local function variables (and their values), to maintain the context of the parent function , like that when the children function finish its works (RET), when the program comes back to the parent function, the program is able to continue working of all saved variables.

It means concretely, that on the assembly code, you will see that before calling each function, the computer needs to :

update esp register (pointer to the top of the stack at any time).
update ebp register (pointer to the beginning of the stack)
save all local variables of the function
save the EIP (the address of the next operation to call when the function is over)

So when you call a function, the program do that, then do a CALL to the address of the function, and at the end of the function (RET) the computer get the EIP address saved previously to be able to come back to the next execution of the function caller, POP all old variables to be able to enter in the context saved, and continue the parent function.

And all this memory management + CALLs takes, on hundreds of function opened (because of recursion) takes time to the processor. It’s for that recursive is slower.

You can ask me : “But tail-recursion do the same think, and it’s faster”.

Yes, because the recursion will open each time a new function without closing the last one until the last recursive function answer.

Fibo(10)
Fibo(8) + Fibo(9)
Fibo(6) + Fibo(7) + Fibo(7) + Fibo(8)
.....
.....
..... + Fibo(2)

Till Fibo(2) that have the breaking loop condition the stack frame manage all the others Fibo function opened, so for Fibo(10) we will have something like 177 function opened. (yes it’s too much)

On tail-recursive, we only have 2 functions to manage in the stack :

the parent calling function (FiboTail(10))
The function executing.

Because when a executing fuction is over (RET) it’s cleaned (because it’s over) and replace by the next one.

FiboTail(10)    // one opened
FiboT(10, 0, 1) // one opened
FiboT(9, 1, 1)  // this one will only be in the stack when the previous one will be over, so removed from the stack.

Tail-Recursion optimization

Some compiler are optimized to work with tail recursion :

doing inline function (copying the code from the function, on the parent function instead do a CALL + all stack things) (disadvantage the executable is bigger.)
knowing that the result will only be in the last function, the compilers will not create a new stack frame for each recursive call, and will instead just re-use the same stack frame.

It as hard to explain, I hope you could understand. You can find a good explanation between recursion vs Tail recursion on this video: