[ Home Page ] [ Back ] [ Content of Contributions ] [ Movement: Green Leaf World ]
----------------------------------------------------------------------------------------------------------------
Till now, we are working with iterative algorithms. In iterative algorithm loop is used. We can write algorithm using recursion.
What is recursion?
A function(or algorithm or method) f is said to recursive, iff What is recursion?
- f(t) can be called(used) in f(z) and
- A condition, called base criteria, for which f(t) will not be called (used) further under f(z) and
- In each recursive call, z must be closer to the base criteria.
Note, that, t is a function of z, such that, changes of z to t must be toward base criteria.
Example of a recursive definition:
The Fibonacci Sequence{0, 1, 1, 2, 3, 5, 8, 13, 21....} can be recursively defined as,
f(0)= 0,
f(1)= 1,
f(i)= f(i-1) + f(i-2).
So, f(4) can be calculated using this formulation as follows,
f(4)= f(3) + f(2)
= {f(2) + f(1)} + {f(1) + f(0)}
= {f(1) + f(0) + 1} + {1 + 0}
= {1 + 0 + 1 } + 1
= 3
Why recursive definition is useful?
It is very simple to express a solution. Easy to understand.
Limitation of recursion: Very costly in terms of time & space (memory).
Problem 01
Let us move to our first recursive algorithm to compute 1+ 2+ ....+ N, N>=0.Analysis:
What is the result for the following N= 0, 1, 2, 3?
Answer:
N Sum
0 0
1 0+1
2 0+1+2=3
3 0+1+2+3=6
From the analysis, for N=0, the result does not require any computation, i.e. result is constant, So, N=0 is the base criteria for our algorithm as we know the result for N=0.
Algorithm_01.01: Rec_Sum_Series (N, R)
Here, N is the input to the algorithm.
R is the output, to store 1+2+....+N.
1. IF N=0 then
Set, R= 0
Return
End of IF
2. Call Rec_Sum_Series( (N-1), R)
3. R= (R+N)
4. Return
How the algorithm will work?
Ok, trying to represent the fact as far as possible for N=2. The algorithm will be used 3 times, 3 column is used for it.
1st Call 2nd Call 3rd Call
Rec_Sum_Series(2, R)
1. False
2. Call---------------->Rec_Sum_Series(1, R)
1. False
2. Call---------------->Rec_Sum_Series(2, R)
<---------------1. R=0, Return
3. R= 0+1
<---------------4. Return
3. R= 1+1
4. return
Now, we have the result in R(=2) after returning from 1st call.
Note that,
- Each row is representing the time & 3 columns are representing 3 different recursive calls of the same method but with different value.
- When 1st call is activated from somewhere, it started with N=2, and not satisfied the base criteria, thus without returning it continues to the next steps. In step 2 there is a call, so the remaining part of the 1st call will be in hold(in stack) and 2nd call will be initiated.
- In 2nd call, N=1, failing base criteria, so moving to 3rd call without computing step 3 & 4.
- In 3rd call, N=0, satisfying the base criteria, and will start returning toward 1st call through last call, i.e. 2nd call, after setting R=0.
- After returning to the step 3 of 2nd call, remaining steps will be computed, what is the value of R & N now? It is 2nd call, so, N=1 here and R=0, as set by the 3rd call. So, in step 3 R will 0+1. So, R is now 1 and will return to 1st call from 2nd call in step 4.
- After returning to the step 3 of 1st call, remaining steps will be computed, what is the value of R & N now? It is 1st call, so, N=2 here and R=1, as set by the 2nd call. So, in step 3 R will 1+2. So, R is now 3 and will return to there from where it has been called for first time.
Try Your Own
Use pencil & paper to demonstrate calls of the algorithm for N=4. The result must be 10.Another approach to the same problem.
Algorithm_01.02: Rec_Sum_Series (N, R)
Here, N is the input to the algorithm.
R is the output(must be set to 0 before 1st call), to store 1+2+....+N.
1. IF N=0 then
Return
End of IF
2. R= (R+N)
3. Call Rec_Sum_Series( (N-1), R)
4. Return
The output will be same as previous algorithm.
Another approach to the same problem.
Algorithm_01.03: Rec_Sum_Series (N)
Here, N is the input to the algorithm.
Result will be returned.
1. IF N=0 then
Return 0
End of IF
2. Return ( N + Rec_Sum_Series (N-1) )
The output will be same as previous two algorithms but interesting part of this approach is that there are no operation after the recursive call. This kind of recursive algorithm is called Tail Recursion.
Problem 02
Find the highest digit in a given number.Analysis:
Lowest digit is 0,
Highest digit is 9,
Algorithm_02.01: Rec_Check_Highest_Digit (N, R)
N is the input number.
R is the output, to store highest digit of N, initial value of R must be set to 0, before first call.
1. IF N=0, Return
2. D:= (N%10)
3. IF D=9, Set, R:= 9, Return
4. IF D>R, Set, R:= D
5. Call Rec_Check_Highest_Digit ( (N/10), R)
6. Return
Another approach to the same problem,
Algorithm_02.02: Rec_Check_Highest_Digit (N, R)
N is the input number.
R is the output, to store highest digit of N.
1. IF N=0, Set, R:=0, Return
2. Call Rec_Check_Highest_Digit ( (N/10), R)
3. D:= (N%10)
4. IF D>R, Set, R:= D
5. Return
Note that, in the above algorithm, n is the z of the definition of recursion and (N/10) is the t of the definition of recursion.
Now tell me,
how much times recursive call will be performed for Algorithm 02.01 and 02.02 a number 2341567456897?
In the next article we will have a look on Complexity of the algorithm.
