What is recursion?
Recursion is when a subroutine calls itself under certain conditions. A recursive subroutine must have three characteristics:
1. It must have a stopping condition i.e. a conditon in which it no longer calls itself.
2. It must call itself in all cases except the stopping condition.
3. The stopping condition must be reached in a finite number of steps.
The stopping condition
The stopping condition is the criteria that must be met for the subroutine to stop calling itself. The stopping condition is sometimes referred to as the base case. When the subroutine stops calling itself and the results of
the individual calls to the subroutine are popped off the call stack the subroutine is said to 'unwind'.
If it is possible for the subroutine to go on indefinitely calling itself without reaching the stopping condition then we will end up in a situation of stack overflow. In practical terms it not only needs to be finite but
feasible with the amount of memory available to the stack.
Uses of recursion
Recursion is often used where the algorithm itself is essentially recursive. Some common uses of recursion include:
* Mathematical sequences
* Tree traversal
* Searching and sorting
In many imperative languages
iteration is more efficient than recursion but it is favoured in functional programming where functions are the building blocks of programs.
Factorials - a recursion example
A factorial is a mathematical term. n! (pronounced n factorial) is the product of all positive integers less than or equal to n.
n! = n x (n-1) x (n-2) x ... x 3 x 2 x 1
This essentially means n! = n x (n-1)!. As 1! = 1 provides a base case it is effective to implement as a recursive algorithm.
Factorial(4)
= 4 x Factorial(3)
= 4 x (3 x Factorial(2))
= 4 x (3 x (2 x Factorial(1))
= 4 x (3 x (2 x 1))
= 4 x (3 x 2)
= 4 x 6
= 24
