Recursion, though important is frequently overlooked by programmers who do not understand its potential and place in algorithm design. It allows the expression of some problems in a very elegant and succinct manner, problems such as the famous Fibonacci number sequence are better understood and written with the aid of recursion. We will go through a few algorithms that employ It in an attempt to explain its function in a clear and concise manner.
I will be using python in this post because its a scripting language and therefore there is no need to recompile while testing my code. If you do not have python on you machine you can get it here python; python IDE .
“A picture is worth a thousand words” is certainly true for this photo, in order for recursion to work there has to be at least one base case. The algorithm can have multiple base cases each of which is responsible for a particular state in which the algorithm may be in at each step. So lets look at our first example of a simple recursive function written in python.
Counting backwards from 10 to 0
def countDescending(num): print num if num == 0: return countDescending(num - 1)
- The countDescending accepts a number as input then prints that number
- Base case: When num = 0 return from the function.
- Recursive step:The function calls itself with the input being reduced by 1
NB* All recursive solutions the initial problem must be one that can be broken down into simpler problems, which eventually leads to the base case. Also to note, each function call along with scoped non-static variables are held on the stack until the base case is reached at which point the stack is unwound and the resources released.
def fib(num): if num < 2:return num if num > 0 :return fib(num-1) + fib(num-2)
Fibonacci Number sequence: 0, 1, 1, 2, 3, 4, 5, 6
Base case: If input is less than 2 return the original input.
Recursive step: If input greater than 0 call fib with number – 1 and number – 2
A recursion tree allows us to gain insight into the workings of a recursive algorithm, the above diagram shows the recursion tree for the Fibonacci number for 6. From it we note that there is lot of repetition in calculation, this could be avoided with the use momoization which we will discuss in a future article.