Factorial Visualisation - Recursive Algorithm - Under the Hood

Many algorithms need to do tasks repetitively.
This can be done in two ways, iterations and recursion.
For iterations, we can use for-loop and while-loop constructs.
Recursion is an entirely different and very interesting method to achieve repetitions.
Recursive technique makes a function call to itself providing it with a subset of the problem it is trying to solve.
This way, every function call has to solve a smaller and relatively easier problem to solve.
There are many examples of recursion in art and nature.
Fractal patterns, for example, are naturally recursive.
Russian Matryoshka dolls are another physical example of recursion where a doll is either made of solid wood or is hollow and hence contains another doll.
Recursion provides a very powerful alternative for performing repetitive tasks in computing.
Most modern programming languages support recursion.
After making a recursive call to itself, a function is suspended until the recursive function call is complete.
This can happen any number of times depending on the problem and the algorithm.
This video will explain recursion using the example of computing the value of factorial function.
The factorial of a positive integer n, denoted by n!, usually called n-not in computing, is defined as the product of integers from 1 to n.
If n = 0, then n! Is defined as 1 by convention.
In mathematical notation, for any integer n greater than or equal to 0, n! will be 1 if n = 0 and will be n.(n-1).(n-2)...3.2.1 if n is greater than or equal to 0
For example 5! = 5.4.3.2.1 which equals 120.
The factorial function is important because n! is known to equal the number of permutations of n items.
There are a vast number of applications of permutations in mathematics, statistics, and many other fields that give the factorial function its importance.
Permutations of n distinct items mean the number of ways these n items can be arranged into a sequence.
For example, the three characters x, y, and z can be arranged in 3! = 3.2.1 = 6 ways.
The factorial function has a natural recursive definition.
5! Is equal to 5.4.3.2.1 which is the same as 5.4!.
To make this definition generic, we can say that n! Is equal to n multiplied by factorial of (n-1).
This recursive definition can be formally written as this.
All recursive definitions have one or more base cases and one or more recursive cases.
Factorial function’s base case is where n = 0 and in this case it returns the integer 1.
For all other cases, it calls itself recursively.
This is the code example of the recursive factorial function written in python.
There are no loops in this function, repetition is provided by the repeated call to itself resulting in recursion.
Each function call is provided with an argument which is 1 less than the previous call.
When the base case is reached, no further recursive calls are made.
When the execution of a function leads to a nested function call, the execution of the former call is suspended and its activation record stores the place in the source code at which the flow of control should continue upon return of the nested call.
This process is the same for a standard function call and a recursive function call.
Execution of a recursive function can be illustrated with a recursion trace.
Each entry of the trace corresponds to a recursive call.
When the function returns, its return value is replaced in the code where the function was called.
It is very interesting to see that problems that have a naturally recursive solution, can be simplified that much in programming.
There are many other interesting examples of recursion such as drawing the english ruler, binary search, and drawing the Koch fractals.
All of these will be explained in separate videos to keep this one short and focused on factorials.
Let's take a look at our recursive factorial function at work one last time.