Recursion is the process of defining a problem in terms of a simpler version of itself. Recursion comes directly from Mathematics, where there are many examples of expressions written in terms of themselves.
It can be a very powerful tool, not in all cases, in writing algorithms.
Let us look at the traditional finding temple squere problem to make the idea more clear.
We can define the steps for operation "Find Temple Square" as:
-
If you are at Temple Square, you are done.
-
Ask Someone which way to go. (they point "that away")
-
Move "that away" until unsure.
Parts of a Recursive Algorithm
All recursive algorithms must have the following:
-
Base Case (this defines when to stop –> it is "simplest" possible problem)
-
Work toward Base Case (here we make the problem simpler)
-
Recursive Call (call to itself i.e. use same algorithm to solve a simpler version of the problem)
The above mentioned "Find Temple Square" now becomes more clear. Here is simplest version of pseudocode that helps you to have insight of recursive algorithm.
Algorithm find_temple_square(route,start_point) if start_point == Temple Squere //this is basis step you are done ask someone which way to go they say 'that_way' find_temple_squere(route,that_way) //recursive step
Recursion Examples:
Now let us look at some practical examples to illustrate recursion.
Factorial
A factorial of a number “x”, which is x!, is just the product of all integers between 1 and x.
x! = x * (x-1) * (x-2) * ... * 2 * 1
So, if x is equal to the number 5, then it's factorial would be 5*4*3*2*1, which equals 120. It can also be defined as 5 * 4!, or 5*4*3*2*1. This means, the factorial of any number “x” could also be defined as:
x! = x * (x - 1)!
Note: 0! = 1 and 1! = 1
We define the properties above mentioned as base case of algorithm to find a factorial.
So, here is program to find the factorial for given integer.
//program to find the factorial of an integer
#include<iostream>
using namespace std;
int factorial (int x)
{
if(x == 0 || x ==1 ) //base case
return 1;
//recursive case:
return factorial(x-1) * x;
}
int main(){
cout << "3 ! = " << factorial(3) <<endl;
cout << "5 ! = " << factorial(5) <<endl;
}
The output of the program is:
3 ! = 6 5 ! = 120
How recursion works?
In a recursive algorithm, the computer "remembers" every previous state of the problem. This information is "held" by the computer on the "activation stack" (i.e., inside of each functions workspace).
Every function has its own workspace PER CALL of the function.
The following diagram depicts how the stack frames work in recursion which will really help to clarify things on how recursion works.
Figure : Stack frame call during recursion
The figure above shows the stack frames for finding the factorial of “3” using the function that we created above (so “x” is equal to 3).
Explanation:
Here, whenever factorial(x) gets call, first stack frame is created with x equal to 3. As it does not meet the base case, a call to factorial(2) is made before the very first call to Factorial can run to completion. Again, since base case is not meet, again 3rd stack frame is created.
Finally, in the 3rd stack frame,base case is meet, which means the recursive calls are finished and then control is returned to the 2nd stack frame, where factorial(1) * 2 is calculated to be 2, and then control is returned to the very first stack frame. Finally, our result of “6” is returned.
Note: A stack frame is used to “hold” the “state” of the function or subroutine call – it will store the local function variables (and their values) of the current function call, and it will also store the return address of the method that called it. Because the stack frame also stores the return address, the corresponding function or subroutine knows where to return to when it finishes running.
Fibonacci Series or numbers
The Fibonacci Sequence is the series of numbers:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …
The next number is found by adding up the two numbers before it.
- The 2 is found by adding the two numbers before it (1+1)
- Similarly, the 3 is found by adding the two numbers before it (1+2),
- And the 5 is (2+3),
- and so on!
In mathematical terms, the sequence Fn of Fibonacci numbers is defined by the recurrence relation as
Fn = Fn-1 + Fn-2 where F0 = 0 and F1 = 1.
Here is a program to find the nth element in finbonacci series:
#include<iostream>
using namespace std;
int Fibonacci(int); //function declaration
main()
{
cout << "5 ! = " << factorial(5) <<endl;
cout << "7 ! = " << factorial(7) <<endl;
return 0;
}
int Fibonacci(int n) // function definition
{
if ( n == 0 )
return 0;
else if ( n == 1 )
return 1;
else
return ( Fibonacci(n-1) + Fibonacci(n-2) );
}
The ouput of the program is:
fibonacci ( 5 ) =5 fibonacci ( 7 ) =13
So, 5th and 7th term in Fibonacci Series are 5 and 13.
We'll talk more about recursion on arrays.