I'm using Scheme to explain recursion due to its predicate first syntax, which better lends itself to AST evaluation.
During the session, the presenter listed three hurdles to becoming an Erlang developer:
- Pattern Matching
- Recursion (Tail Recursion) and
- Concurrency
After looking around at a few Erlang tutorials, I found myself returning to sicp site to review its section on recursion optimisations. Basically, it all comes down to a rudimentary understanding of how execution processes utilise the humble stack to perform tasks.
The stack keeps tabs on the sequence in which instructions should be processed. When a function is called, the current instruction pointer is pushed onto the stack and a new stack for the called function is created, ready to sequence instructions to the process. Once the function returns a value, the stack is cleared an the previous instruction pointer is restored to continue execution. Imagine this as a tree of stacks, representing execution blocks, which point to child blocks when computational delegation is required to achieve the the blocks goal. These blocks wink in and out of existence, dependent upon execution completion and dependency counts.
Apply this knowledge to a recursive function:
(define linear-factorial-recursion n)
(if (= n 1) 1
(* n (linear-factorial-recursion (- n 1))))
The multiplier on the last line, requires n and a recursive call to linear-factorial-recursion to evaluate and so the stack is retained until the entire function achieves its goal. We can imagine this evaluation like so:
(linear-factorial-recursion 3)
(* 3 (linear-factorial-recursion 2))
(* 3 (* 2 (linear-factorial-recursion 1)))
(* 3 (* 2 1))
(* 3 2)
= 6
As you can see, retaining a reference to achieve a full evaluation goal at the highest level, requires an expanding/Collapsible stack scenario, where the rate of expanse is proportional to the number of iterations - linear recursion - Imagine factorial 10000 - that's allot of stack space!!
To break the recursive dependency on the last line of the above function, one simply has to supply all state into the recursive function so that the calling function evaluates immediately, clearing the functions stack.
(define (iterative-factorial n) (tail-recursive-factorial 1 n))
(define (tail-recursive-factorial p n)
(if (= n 1) p
(tail-recursive-factorial (* p n) (- n 1))))
Notice that the last line is not assigned to a multiplier function, eliminating a reference to the calling function stack; Instead all state is evaluated as its passed into the recursive call to the function. We could imagine this evaluation like so:
(iterative-factorial 3)
(tail-recursive-factorial 1 3)
(tail-recursive-factorial 3 2)
(tail-recursive-factorial 6 1)
=6
Notice how the stack size remains constant, due to the fact that the previous function call passes all evaluated state to the new function call in an iterative linear fashion.
So some nice things about iterative linear recursion - or tail recursion:
- The function can recurse indefinitely since stack resources are constant.
- Increase in performance as a result of less push pops for stacks
- parallelism due to orthogonal nature of recursive function calls. Stacks do not create child stack dependencies to achieve goals.
Tail recursive factorial function in Erlang:
-module(basic).
-compile(export_all).
factorial2(P, C) ->
if
C < 1 -> P;
true -> factorial2( P*C, C-1)
end.
factorial(N) -> basic:factorial2(1, N).
