unit 6
Recursion
• Introduction,
• Principle of Recursion,
• Recursion vs. Iteration,
• Recursion Examples: TOH,
• Fibonacci Series,
• Application of Recursion,
• Search Tree
Define Define Recursion. Explain the Principle of Recursion.
We learn Differentiate Differentiate between Recursion and Iterations.
following
question List out List out advantages and disadvantages of Recursion.
s in this Use Use Recursion to solve the different problems (calculate factorial,
unit
reversing an integer, checking prime number, TOH, Fibonacci Series etc.).
Implement Implement recursion to find form search tree
• Recursion is the process which comes into
existence when a function calls a copy of itself
to work on a smaller problem. Any function
which calls itself is called recursive function,
and such function calls are called recursive calls.
What is Recursion involves several numbers of recursive
calls. However, it is important to impose a
recursion? termination condition of recursion. Recursion
code is shorter than iterative code however it is
difficult to understand.
• Recursion cannot be applied to all the problem,
but it is more useful for the tasks that can be
defined in terms of similar subtasks.
• For Example, recursion may be applied to sorting, searching, and
traversal problems.
• Generally, iterative solutions are more efficient than recursion since
function call is always overhead. Any problem that can be solved
recursively, can also be solved iteratively. However, some problems
are best suited to be solved by the recursion, for example, tower of
Hanoi, Fibonacci series, factorial finding, etc.
• Properties
• A recursive function can go infinite like a loop. To avoid infinite running of recursive
function, there are two properties that a recursive function must have −
• Base criteria − There must be at least one base criteria or condition, such that, when
this condition is met the function stops calling itself recursively.
• Progressive approach − The recursive calls should progress in such a way that each
time a recursive call is made it comes closer to the base criteria.
Advantage of recursion.
• Recursion can reduce time complexity. ...
• Recursion adds clarity and reduces the time needed to write
and debug code. ...
• Recursion is better at tree traversal. ...
• Recursion uses more memory. ...
• Recursion can be slow. ..
Principle of recursion
• A recursive algorithm must have a base case.
• A recursive algorithm must change its state and move toward
the base case.
• A recursive algorithm must call itself, recursively.
Program (do your self and post me
on teams).
• Write a program to find factorial of given number.
• Write a program to print the series of Fibonacci number
• Write a program to find the sum of n natural number.
Types of recursion
1. Primitive Recursion
• It is the types of recursion that can be converted into a loop.
• We have already seen the Fibonacci series example which can be
programmed with recursion as well as with loop.
2. Tail Recursion
• It is a primitive recursion in which the recursive call is present as the
last thing in the function.
• In the above Fibonacci example, the recursive function is executed as
the last statement of the ‘fibo’ function.
3. Single Recursion
It is the types of recursion when there is only one recursive call in the
function.
4. Multiple Recursion
As by its name, it is the types of recursion when there are multiple
recursive calls in the function.
It is just the opposite of a single recursion. Recursion can be either
single or multiple type.
5. Mutual Recursion or Indirect Recursion)
There are two or more functions involved in this type of recursion.
In this type of recursion, a function calls another function, which
eventually calls the original function.
• 6. General Recursion
• If there is a function which cannot be defined without recursion, is
called as general recursion.
• It is the opposite of primitive type recursion.
What is the difference between tailed and non-tailed recursion?
In tail recursion, a recursive call is executed at the end of the function.
If the recursive call is executed at the beginning or in the middle of
the function, it is called as non-tailed recursion.
When to (not) use recursion?
If the memory utilization is the concern of if there is limited memory
resource available, it is always a good choice implementing primitive
type recursion with loops.
Mobile has very limited memory space to execute any apps. If you are
developing a mobile application, avoid using recursion.
How the memory is allocated to the recursive function call?
When the recursive function gets called, the memory is allocated in
stack memory. For every recursive function call, a copy of the all local
variable in the function is created.
After executing the recursive function, it returns the value to the
function by whom it is called and memory gets deallo0ctaed from the
stack.
RECURSION VS. ITERATION,
BASIS FOR COMPARISON RECURSION ITERATION
Basic The statement in a body of function calls the Allows the set of instructions to be
function itself. repeatedly executed.
Format In recursive function, only termination condition Iteration includes initialization, condition,
(base case) is specified. execution of statement within loop and
update (increments and decrements) the
control variable.
Termination A conditional statement is included in the body The iteration statement is repeatedly
of the function to force the function to return executed until a certain condition is
without recursion call being executed. reached.
Condition If the function does not converge to If the control condition in the
some condition called (base case), it iteration statement never become
leads to infinite recursion. false, it leads to infinite iteration.
Infinite Repetition Infinite recursion can crash the Infinite loop uses CPU cycles
system. repeatedly.
Applied Recursion is always applied to Iteration is applied to iteration
functions. statements or "loops".
Stack The stack is used to store the set of Does not uses stack.
new local variables and
parameters each time the function
is called.
Overhead Recursion possesses the overhead of No overhead of repeated function
repeated function calls. call.
Speed Slow in execution. Fast in execution.
Size of Code Recursion reduces the size of the Iteration makes the code longer.
code.
FACTORIAL TREE IN RECURSION
TOH problem using recursion
• the Tower of Hanoi mathematical puzzle was invented by the
French mathematician Edouard Lucas. The inspiration came from a
legend that states - In Ancient Hindu temple, this puzzle was
presented to the young priest. The puzzle is, there are three poles,
and 64 disks, and each disk is smaller than the other. To solve this
problem, move all 64 disks from one of the three poles to another
pole without violating the essential constraints.
• The disks can be moved one disk at a time and they should place a
smaller disk top of a larger one.
Rules of the game
The rules of "Tower of Hanoi" are quite simple, but the solution is slightly
hard. There are three rods. The disks are stacked in the descending
order; the largest disk stacked at the bottom and the smallest one on
top
The task is to transfer the disks from one source rod to another target
rod.
The following rule must not be violated
• Only one disk can be moved at a time.
• The most upper disk from one of the rod can be stimulated in move.
• The smaller disk cannot be placed at the lower of the largest disk.
TOH problems solution.
From above example we know that:
1 move n-1 disk from source to temporary using destination
2. move N disk from source to destination.
3. move n-1 disk from temporary to destination using source.
The main recursion function is as
void TOH(int n,char x,char y,char z)
{
if(n>0)
{
TOH(n-1,x,z,y);
printf("\n%c to %c",x,y);
TOH(n-1,z,y,x);
}
}
Program of toh
/* Program for solution of Tower of Hanoi*/ toh( int ndisk, char source, char temp, char dest )
#include<stdio.h> {
void main() if ( ndisk > 0 )
{ {
char source= 'S',temp= 'T ', dest= 'D'; toh ( ndisk-1, source, dest, temp );
int ndisk; printf ( "Move Disk %d %c-->%c\n", ndisk, source,dest );
printf("Enter the number of disks : "); toh( ndisk-1, temp, source, dest );
scanf ( "%d", &ndisk ); }
printf ("Sequence is :\n"); return 0;
toh( ndisk, source, temp, dest ); }/*End of toh()*/
getch();
return;
}
Toh tree of disk size 3.
Practical Applications:
• The practical applications of recursion are near endless. Many math functions
cannot be expressed without its use. The more famous ones are the Fibonacci
sequence and the Ackermann function. It’s through math functions that many
software applications are built. Take for example Candy Crush which uses
them to generate combinations of tiles.
• If you’re not familiar with Candy Crush (You should be) then chess is another
example of recursion in action. Almost all searching algorithms today use a
form of recursion as well. In this day and age where information is key,
recursion becomes one of the most important methods in programming.
Any Question ??
The End.
