ABSTRACT DATA STRUCTURES | RECURSION
SECTION 1 | WHAT IS RECURSION?
Recursion is a method used to solve a big problem by repeating smaller problems in a pattern that eventually reaches the end result. In programming terms, we can create a function that calls itself until a condition is met.
When using a recursive method we need to consider the two principles:
1. The pattern (recursion) to follow. (Recursive Case)
2. When the goal has been reached where to stop. (Base Case)
SECTION 2 | THE DIFFERENCE BETWEEN LOOPS AND RECURSION
Everything recursion can do, loops can do. So why use recursion? For loops in Python or Java and Do loops in some early languages such as Fortran can nest loops(put loops within a loop). By nesting loops we can achieve the same as using a recursive method. Using nested loops can get complicated, heavy on the compiler and process heavy. Previous limitations on how deep loops can be nested, with early programming languages like Fortran allowing for around 8 nested loops, although currently 256+ nested loops in some programming languages are accepted they can get messy and recursion can provide a more efficient solution to solving the same problem.
Recursion can still cause processing problems with the amount of data that is stacked up waiting to be processed, and this is known as a stack overflow.
While recursion is a much more elegant solution to nested loops, in the past there may not be many real world examples of where recursion is needed because loops cannot deal with the situation, however we may see more recursive methods used in future programming as computational solutions may be more frequently done 'on the fly' and compiling speed becomes more crucial. A counter argument for future use of recursion is that we may see more programs being written in low level languages, as more and more future programs will be written by computers therefore reducing the load in the compiling stage. Furthermore is the impact quantum computers may have with the change in programming languages for quantum computing.
Some practical uses for recursion include:
-
Tree Traversal: When dealing with a tree data structure, such as a binary search tree, using recursion can be an effective way to traverse the tree in a depth-first search manner.
-
Sorting: Recursion can be used to implement several sorting algorithms, such as quicksort and mergesort.
-
Fractals: Fractals are shapes that have self-similar patterns, and they can be generated using recursive algorithms.
SECTION 3 | FACTORIALS WITH RECURSION
Factorials are simply products of all the numbers below the given numbers. Often notated with an explanation mark, for example factorial 4 would be 4!. To calculate 4! you simply do 1x2x3x4 = 24, so factorial 4 is 24. (! means to multiply by decreasing positive integers). Below is an example code of a recursive method to calculate the factorial of a given number.
SECTION 4 | FIBONACCI WITH RECURSION
The Fibonacci sequence is calculated by adding the two previous numbers together to generate the next number in the sequence. The Fibonacci sequence in the code below has two recursive calls, each containing one of the two previous numbers needed to calculate the next number.