What is Recursion?
Any function which calls itself is called a recursive function. A recursive method solves a problem by calling a copy of itself to work on a smaller problem. This is called the recursion step. The recursion step can result in many more such recursive calls. It is important to ensure that the recursion terminates. Each time the function calls itself with a slightly simpler version of the original problem. The sequence of smaller problems must eventually converge on the base case.
Why Recursion?
Recursion is a useful technique borrowed from mathematics. Recursive code is generally shorter and easier to write than iterative code. Generally, loops are turned into recursive functions when they are compiled or interpreted. Recursion is most useful for tasks that can be defined in terms of similar sub tasks. For example, sort, search, and traversal problems often have simple recursive solutions.
Format of a Recursive Function
A recursive function performs a task in part by calling itself to perform the sub tasks. At some point, the function encounters a sub task that it can perform without calling itself. This case, where the function does not recur, is called the base case, the former, where the function calls itself to perform a sub task, is referred to as the recursive case. We can write all recursive functions using the format:-
if( test for the base case )
return some base case value;
else if( test for another base case )
return some other base case value;
// the recursive case
else
return ( some work ) and then ( a recursive call )
