jonnifyelixir
F2 / F2.04 / tail-calls

F2.04 · part 2 of 3

Tail calls & accumulators

Body recursion does its work on the way back up, so it holds a frame for every pending call. A tail-recursive function does the work on the way down and carries the result in an accumulator — so there is nothing to come back to, and the stack stays flat.

A call is in tail position when it is the last thing a function does — its result is returned directly, with no pending addition or multiplication around it. The runtime can then reuse the current frame instead of stacking a new one: tail-call optimisation. The trick that puts a recursive call in tail position is an accumulator: an extra argument that carries the answer-so-far.

Body vs tail The accumulator builds Worked examples

Body vs tail

The same sum, two ways. Body recursion writes h + sum(t): the addition waits on the recursive call, so the call is not in tail position and each step adds a frame. Tail recursion writes sum(t, acc + h): the call is the whole result, so the frame is reused and the stack never grows.

Switch between them and compare the stack at its deepest.

body recursion
work wraps the recursive call; the stack grows with the input.
tail call
the recursive call is the last action, returned directly.
accumulator
an extra argument carrying the result-so-far down the recursion.
tail-call optimisation
reusing the current frame for a tail call — constant stack space.

sum([1, 2, 3, 4]) · the stack at its deepest

5 FRAMES · O(n) SPACE 


      
body recursion · the stack grows to one frame per element · O(n) space

    

    

      

        
Idea

        
If nothing waits on the recursive call, nothing needs to be remembered.

      

      
      

        
Elixir

        
The BEAM reuses the frame for a tail call, so deep recursion runs in constant space.

      

    

    
Body recursion: a frame per element. Tail recursion: one frame, reused. The difference is
      whether the recursive call is the last thing the clause does.

  


  
  

    
The accumulator builds

    

      
Watch the accumulator carry the running total down the recursion. The list shrinks, the accumulator
        grows, and the single frame is reused at each step. When the list is empty, the accumulator is the
        answer — no unwinding required.

      
Step through the tail-recursive sum.

    


    

      
sum([1, 2, 3, 4], 0) · one frame, growing accumulator

      

        

          
          
          1 / 6
        

      


      
        ONE FRAME · REUSED EACH STEP
        
        sum([1, 2, 3, 4], 0)

        list remaining
        

        accumulator
        
        0
      

      


      
step 1 · sum([1, 2, 3, 4], 0) · acc = 0

    

    

      

        
Idea

        
Carry the answer-so-far instead of leaving it for the return trip.

      

      
      

        
Elixir

        
sum([], acc), do: acc — at the base, the accumulator is the result.

      

    

    
The accumulator turns “remember to add this later” into “add it now and pass it
      on.” The result arrives at the base case fully formed.