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!