1 of 11

Yavatmal Zilha Akhil Kunbi Samaj Dwara Sanchalit,

Gopikabai Sitaram Gawande Mahavidyalaya, Umarkhed

Department of Computer Application

Name of Topic :- Unit II - Recursion

Subject :- Data Structure

Created by : Pravin Nakhate

Email:-nakhate@gsgcollege.edu.in

Mobile No. +919420621381

Class :- BCA – II

2 of 11

Learning Objectives:-

​

​

  1. Describe Recursion.
  2. Describe examples of Recursion.
  3. Difference Between Recursion and iteration.
  4. Describe Disadvantages of recursion
  5. Translation from prefix to postfix simulation recursion.
  6. Describe Tower of Hanoi

3 of 11

Introduction:-

​

  • Recursion is one of the application of the stack.
  • Stack is internally used by compiler when we implement any recursive function.
  • If we want to implement a recursive function non-recursively, stack is programmed explicitly.

​

4 of 11

Recursion:-

​

  • Recursion occurs when a function is called by itself repeatedly; the function is called recursive function.
  • Recursion of course is an elegant programming technique, but not the best way to solve a problem, even if it is recursive in nature.

​

​

5 of 11

Iteration vs. Recursion:-

Iteration

Recursion

It is a process of executing a statement or a set of statements repeatedly, until some specified condition is specified.

Recursion is the technique of defining anything in terms of itself.

Iteration involves four clear-cut steps like initialization, condition, execution and updating.

There must be an exclusive if statement inside the recursive function, specifying stopping condition.

Any recursive problem can be solved iteratively.

Not all problems have recursive solution.

Iterative counterpart of a problem is more efficient in terms of memory utilization and execution speed.

Recursion is generally a worse option to go for simple problems, or problems not recursive in nature.

6 of 11

Examples of Recursion:-

1. To calculate the factorial of number we can use recursive function.

#include <stdio.h>  

int fact (int);  

int main()  

{  

    int n,f;  

    printf("Enter the number whose factorial you want to calculate?");  

    scanf("%d",&n);  

    f = fact(n);  

    printf("factorial = %d", f);  

}  

int fact(int n)  

{  

    if ( n == 1)  

           return 1;  

    else    

        return n*fact(n-1);  

}  

7 of 11

2. Let's see an example to find the nth term of the Fibonacci series

.

#include<stdio.h>  

int fibonacci(int);  

void main ()  

{  

    int n,f;  

    printf("Enter the value of n?");  

    scanf("%d",&n);  

    f = fibonacci(n);  

    printf("%d ",f);  

}  

int fibonacci (int n)  

{  

    if (n==0)  

     return 0;    

    else if (n == 1)  

        return 1;    

    else  

        return fibonacci(n-1)+fibonacci(n-2);  

}  

8 of 11

A recursive solution to conversion

function convert(in pre:string, out post:string)

ch = first character of pre

delete first character of pre

if ch is an operand

post = post + ch //concatenate

else

// recursion to convert 1st

convert(pre, post)

// recursion to convert 2nd

convert(pre, post)

// concatenate the operator

post = post + ch

endif

endfunction

Translation from prefix to postfix simulation recursion.

9 of 11

Disadvantages of Recursion:-

  • It consumes more storage space because the recursive calls along with automatic variables are stored on the stack.
  • The computer may run out of memory if the recursive calls are not checked.
  • It is more efficient in terms of speed and execution time.
  • According to some computer professionals, recursion does not offer any concrete advantage over non-recursive procedures/functions.
  • If proper precautions are not taken, recursion may result in non-terminating iterations.
  • Recursion is not advocated when the problem can be through iteration. Recursion may be treated as a software tool to be applied carefully and selectively.

10 of 11

TOWER OF HANOI:-

Now let us look at the Tower of Hanoi and see how we can use recursive technique to produce a logical and elegant solution.

https://youtu.be/fffbT41IuB4

Click below To View animation of Tower of Hanoi

The problem setup is as below :-

  1. Here three pegs (or Towers) A, B and C.
  2. There will be some different sized disk, says 1, 2, 3, ….. N
  3. Each disk has a hole in the center so that it can be stacked on any of the pegs.
  4. At the beginning, the disks are stacked on the A Tower, that is the largest sized disk on the bottom and the smallest sized disk on top.

Here we have to transfer all the disks from source Tower A to the destination Tower C by using an intermediate Tower B. Following are the rules to be followed during transfer:-

  1. Transferring the disks from the source Tower to the destination Tower such that at any point of transformation no large size disk is placed on the smaller one.
  2. Only one disk may be moved at a time.
  3. Each disk must be stacked on any of the Tower.

11 of 11

Thank You