Recursion by a simple definition is the event when a function contains a call to itself. This method of solving problems as i stated above is the divide and conquer method, we basically take a problem, divide it into smaller segments of it self and solve it mostly using the same algorithm and then combine those solutions back together.
Why is recursion important?
I have asked and been asked this question a lot of times, and i will try to answer to the best of my knowledge.
First of all, some will say it is easier to use iteration instead of recursion and sometimes it is more effective since recursion can take a lot of memory and time when it gets too deep. But there are some scenarios and problems such as:
- Iterating through linked list, binary trees, and some other level based data structures.
- Searching games and exploring possible scenarios such as in chess, checkers etc.
- Searching files in different locations in a system (i.e recursion can get to the root)
Recursion is your best solution for this type of problems, since it moves from one level to a deeper level till it gets to the root then comes back with or without a result, using a single algorithm that is called over and over again. Writing algorithm for this in an iterative manner can really get complicated.
Of course recursion is not normally easy to comprehend and can be confusing because of the inability to visualize the levels and what happen at each level, but once one understands the concept behind recursion, it is really fun and time saver.
There are two major segments of recursion one needs to know;
- Termination segment, and
- Call to itself
this two have to be considered, when to terminate recursion is very important because if it is not dealt with, it can grow and fill the memory until there are no more space causing the system to terminate and also lose of data.
Examples:
The most popular problem solved recursively is finding the factorial of a number
e.g (5! = 5x4x3x2x1). solution in C:
int factorial(int number){
//termination segment
if(number == 0 || number ==1){
return 1;
}
//recursion: calling itself in a deeper level
if(number > 1){
return number * factorial(number - 1)
}
}
Also another example can be writing a Fibonacci function recursively.
Solution in Python:
def fibonacci(number):
#terminates when number is 1 or 0 returning the number
if number < 2:
return number
#compute the fibonacci sequence
else:
return (fibonacci(number - 1)+fibonacci(number - 2))
Another example can be searching for an element in an array.
Solution in Java:
// we pass the array, the value to be searched and the// position is returned, initialized to zero
public in search(int array[], int value, int position){
if(array[position] == value){
return position;
//as long as we have not reach the end //of array, we keep searching
} else if(position < array.length){
search(value, position + 1);
}
// returning -1 when not found, Note: i used -1 because// index of an array starts from 0.
return -1;
}
Leave your comments below if you found this materail to be helpful and ideas on what you will love to see in one of my series. Have fun hacking.
