Recursion and Tail-recursion

What is recursion?

The concept is general. Stories inside stories, movies inside movies, images inside an images….

Formal definition?
Recursion is function that call itself.

why would a function call itself?
There are LOTS of algorithms for which the simplest and easiest to maintain version is recursive.
Sorting/searching Algorithms, Most data structures.

A factorial number is a simple recursive function,
Its the product of all positive integers less than or equal to n. For example

5! = 5 * 4 * 3 * 2 * 1

First thing to think about is the base case, When to stop?
When we reach 1 …

if Number == 1; then the answer is 1

if Number == 1; then the answer is 1
factorial(Number) = Number * factorial(Number -1)

In a C-style language it would be

factorial(Number)
if x == 1
return Number
else
return Number * factorial(Number - 1)

This function will be executed like this

5! = 5 * factorial(4)
5! = 5 * 4 * factorial(3)
5! = 5 * 4 * 3 * factorial(2)
5! = 5 * 4 * 3 * 2 * factorial(1) #Where it meets the base case
5! = 5 * 4 * 3 * 2 * 1 = 120 … #Congratulations!
Is it a good practice to keep that much of operations in memory?

Do you see the growth rate of this function? It grows as much as there are elements to multiply
2!= 2, 3!= 6, 4!= 24, 5!= 120… 9!= 362880
Dare we calculate 120! ? 🙂 …

– Another concept introduced here is Tail Recursion to transform the above linear process to an iterative one.

In order to eliminate this stacking of operation we want to reduce them,
So we will need to hold an extra temporary variable as a parameter in our function, They call it Accumulator

Accumulator is place to hold our calculation results as they happen.

A Tail recursion version of our function

tail_factorial(Number, Accumulator = 1 )
if Number == 1    #Our base case
return Accumulator
else
return tail_factorial(Number -1, Accumulator * Number)

tail_factorial(4) execution looks like

tail_factorial(4)     = tail_factorial(4, 1)
tail_factorial(4, 1)  = tail_factorial(4-1, 4*1)
tail_factorial(3, 4)  = tail_factorial(3-1, 3*4)
tail_factorial(2, 12) = tail_factorial(2-1, 2*12)
tail_factorial(1, 24) = tail_factorial(1-1, 1*24) #Reach the base case
tail_factorial(0, 24) = 24

Do you see the difference? Now we never need to hold more than two terms in memory!