Recursion
To begin, I want to make it clear that my purpose of studying a career as a full stack programmer is to learn to program, therefore if my interest were to be a famous writer, I would have chosen a career in literature.
I’ll try to explain the recursion as best I can.
Definition: Recursion (adjective: recursive) occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathematics and computer science, where a function being defined is applied within its own definition. While this apparently defines an infinite number of instances (function values), it is often done in such a way that no infinite loop or infinite chain of references can occur.
What is recursion in programming?
Recursion means “defining a problem in terms of itself”. This can be a very powerful tool in writing algorithms. Recursion comes directly from Mathematics, where there are many examples of expressions written in terms of themselves. For example, the Fibonacci sequence is defined as: F(i) = F(i-1) + F(i-2)
Recursion
Recursion is the process of defining a problem (or the solution to a problem) in terms of (a simpler version of) itself.
For example, we can define the operation “find your way home” as:
- If you are at home, stop moving.
- Take one step toward home.
- “find your way home”.
Here the solution to finding your way home is two steps (three steps). First, we don’t go home if we are already home. Secondly, we do a very simple action that makes our situation simpler to solve. Finally, we redo the entire algorithm.
The above example is called tail recursion. This is where the very last statement is calling the recursive algorithm. Tail recursion can directly be translated into loops.
RECURSION — EXAMPLE
float _pow_recursion(float x, float y)
{
if (y == 0)
return (1);
if (y < 0)
return (_pow_recursion(x, y + 1) / x);
return (_pow_recursion(x, y — 1) * x);
}
The base case in this function is when y equals 0. The other if statement “if y < 0” is there as a safeguard against the user trying to raise a number to the negative power and can be ignored in this recursion discussion.
Let’s step through a simple example and see what happens in the stack at each recursive step.
Say we want to perform the calculation ³⁴. Using the function above, the first time the function gets called, x will be 3 and y will be 4. On the call stack, it can be pictured as follows(bottom to top, remember Last In, First Out):
In the diagram above, the main function is represented as the bottom most block (0) and the next block up (1) is the first call to _pow_recursion. Execution of the code goes from block 0 to block 5, each block is paused after a new block is added above and waits. Then, once the base condition is met and the top most block completes execution, the process reverses and each function runs to completion from top to bottom and returns the result until we finally get back to main (0) and arrive at the final result. Visually, one can follow the arrows in the diagram above starting from the bottom left (0) up to the top (5), then going to the right and following the arrows down until arriving back at main (0).
Walking through the code, the main function is the entry point into the program, inside main, the recursive function _pow_recursion is called with x = 3 and y = 4. The actual function call will look like the following:
result = _pow_recursion(3,4);
Within the _pow_recursion function, the first few lines of code are a couple of if statements. As discussed earlier, the first if statement “if y < 0” is a safeguard against an infinite loop condition if negative y value is used.
The next if statement “if y == 0” is the base case or stop condition. This statement will stop the recursion and just return the value 1 to the calling function.
The next line of code: return (_pow_recursion(x, y-1) * x); is arguably the most interesting and complex line of code in this function. Even though it looks like it just returns a value, this where the recursion happens. Inside the parenthesis for the return, there is a function call to _pow_recursion again, but this time with value of y-1. To visualize this, prior to this point, we are at block 1 in the diagram, when this line gets executed, execution of block 1 pauses and block 2 is added to the stack and block 2 starts executing the function from the beginning. This will run the 2 if statements again to check if the base case has been satisfied. If not, execution will get to the line with the “return” statement again, and again this block in the stack will pause and a new block added. The process repeats until y is 0. In the diagram, this happens at block (5). At this point, y is 0, so it will execute the line of code for “if y == 0”. This will return the value 1 from block 5 to block 4. Recall that block 4 was paused at the return statement. At this point block 5 returned 1 and the return statement of block 4 takes this value and multiply by x. So the code will calculate 1 * 3 and return the result of this multiplication to block 3. This process repeats with the code multiplying the value returned by x each time until we get to block 0 where the return value from block 1 is 81.
Parts of a Recursive Algorithm
All recursive algorithms must have the following:
- Base Case (i.e., when to stop)
- Work toward Base Case
- Recursive Call (i.e., call ourselves)
The “work toward base case” is where we make the problem simpler (e.g., divide list into two parts, each smaller than the original). The recursive call, is where we use the same algorithm to solve a simpler version of the problem. The base case is the solution to the “simplest” possible problem (For example, the base case in the problem ‘find the largest number in a list’ would be if the list had only one number… and by definition if there is only one number, it is the largest).
In programming terms a recursive function can be defined as a routine that calls itself directly or indirectly.
Using recursive algorithm, certain problems can be solved quite easily. Towers of Hanoi (TOH) is one such programming exercise. Try to write an iterative algorithm for TOH. Moreover, every recursive program can be written using iterative methods (Refer Data Structures by Lipschutz).
Mathematically recursion helps to solve few puzzles easily.
For example, a routine interview question,
In a party of N people, each person will shake her/his hand with each other person only once. On total how many hand-shakes would happen?
Solution:
It can be solved in different ways, graphs, recursion, etc. Let us see, how recursively it can be solved.
There are N persons. Each person shake-hand with each other only once. Considering N-th person, (s)he has to shake-hand with (N-1) persons. Now the problem reduced to small instance of (N-1) persons. Assuming TN as total shake-hands, it can be formulated recursively.
TN = (N-1) + TN-1 [T1 = 0, i.e. the last person have already shook-hand with every one]
Solving it recursively yields an arithmetic series, which can be evaluated to N(N-1)/2.
Exercise: In a party of N couples, only one gender (either male or female) can shake hand with every one. How many shake-hands would happen?
Usually recursive programs results in poor time complexities. An example is Fibonacci series. The time complexity of calculating n-th Fibonacci number using recursion is approximately 1.6n. It means the same computer takes almost 60% more time for next Fibonacci number. Recursive Fibonacci algorithm has overlapped subproblems. There are other techniques like dynamic programming to improve such overlapped algorithms.
However, few algorithms, (e.g. merge sort, quick sort, etc…) results in optimal time complexity using recursion.
Base Case:
One critical requirement of recursive functions is termination point or base case. Every recursive program must have base case to make sure that the function will terminate. Missing base case results in unexpected behaviour.
Different Ways of Writing Recursive Functions
Function calling itself: (Direct way)
Most of us aware atleast two different ways of writing recursive programs. Given below is towers of Hanoi code. It is an example of direct calling.
#include <bits/stdc++.h>
using namespace std;
// Assuming n-th disk is bottom disk (count down)
void tower(int n, char sourcePole,
char destinationPole, char auxiliaryPole)
{
// Base case (termination condition)
if(0 == n)
return;
// Move first n-1 disks from source pole
// to auxiliary pole using destination as
// temporary pole
tower(n — 1, sourcePole, auxiliaryPole,
destinationPole);
// Move the remaining disk from source
// pole to destination pole
cout << “Move the disk “<< n << “ from “ <<
sourcePole <<” to “<< destinationPole << endl;
// Move the n-1 disks from auxiliary (now source)
// pole to destination pole using source pole as
// temporary (auxiliary) pole
tower(n — 1, auxiliaryPole, destinationPole,
sourcePole);
}
// Driver code
int main()
{
tower(3, ‘S’, ‘D’, ‘A’);
return 0;
}
// This code is contributed by SHUBHAMSINGH10
Output :
Move the disk 1 from S to D
Move the disk 2 from S to A
Move the disk 1 from D to A
Move the disk 3 from S to D
Move the disk 1 from A to S
Move the disk 2 from A to D
Move the disk 1 from S to D
The time complexity of TOH can be calculated by formulating number of moves.
We need to move the first N-1 disks from Source to Auxiliary and from Auxiliary to Destination, i.e. the first N-1 disks requires two moves. One more move of last disk from Source to Destination. Mathematically it can be defined recursively.
MN = 2MN-1 + 1.
We can easily solve the above recursive relation (2N-1), which is exponential.
Recursion using mutual function call: (Indirect way)
Indirect calling. Though least pratical, a function [funA()] can call another function [funB()] which inturn calls [funA()] former function. In this case both the functions should have the base case.
Defensive Programming:
We can combine defensive coding techniques with recursion for graceful functionality of application. Usually recursive programming is not allowed in safety critical applications, such as flight controls, health monitoring, etc. However, one can use a static count technique to avoid uncontrolled calls (NOT in safety critical systems, may be used in soft real time systems).
void recursive(int data)
{
static callDepth;
if(callDepth > MAX_DEPTH)
return;
// Increase call depth
callDepth++;
// do other processing
recursive(data);
// do other processing
// Decrease call depth
callDepth — ;
}
// This code is contributed by rutvik_56
callDepth depth depends on function stack frame size and maximum stack size.
Recursion using function pointers: (Indirect way)
Recursion can also implemented with function pointers. An example is signal handler in POSIX complaint systems. If the handler causes to trigger same event due to which the handler being called, the function will reenter.
