Scribd Logo
Upload

Welcome to Scribd!

  • 21 views

    Class-Xii CH-11

    Uploaded by

    YAFAS
    This document discusses recursion in computer programming. It defines recursion as a technique where a function calls itself instead of calling another function. It provides examples of direct and indirect recursion. It also describes different types of direct recursion like linear, tail, head, binary, and tree recursion. Finally, it discusses the uses of recursive functions for displaying series, performing calculations, and comparing recursion to iteration.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd

    Class-Xii CH-11

    Uploaded by

    YAFAS
    21 views14 pages
    This document discusses recursion in computer programming. It defines recursion as a technique where a function calls itself instead of calling another function. It provides examples of direct and indirect recursion. It also describes different types of direct recursion like linear, tail, head, binary, and tree recursion. Finally, it discusses the uses of recursive functions for displaying series, performing calculations, and comparing recursion to iteration.

    Original Title

    CLASS-XII CH-11

    Copyright

    © © All Rights Reserved

    Available Formats

    PPTX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document discusses recursion in computer programming. It defines recursion as a technique where a function calls itself instead of calling another function. It provides examples of direct and indirect recursion. It also describes different types of direct recursion like linear, tail, head, binary, and tree recursion. Finally, it discusses the uses of recursive functions for displaying series, performing calculations, and comparing recursion to iteration.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    21 views14 pages

    Class-Xii CH-11

    Uploaded by

    YAFAS
    This document discusses recursion in computer programming. It defines recursion as a technique where a function calls itself instead of calling another function. It provides examples of direct and indirect recursion. It also describes different types of direct recursion like linear, tail, head, binary, and tree recursion. Finally, it discusses the uses of recursive functions for displaying series, performing calculations, and comparing recursion to iteration.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    of 14

    RECURSION

    GURU HAR RAI ACADEMY


    KANPUR
    DEPARTMENT OF COMPUTER SCIENCE

    By Vineet Saxena
    RECURSION
     Recursion is a programming technique in which a
    function calls itself instead of calling other function.
     Example

     void A ( )

    {

     -------

     -------

     -------

     A ( );

    }
    TYPES OF RECURSION
     Direct Recursion
     Indirect Recursion

     Direct recursion

     When a function calls itself.


     void A( )
     {
     -------
     -------
     -------
     A( );
     }
     Indirect recursion
     This function calls itself with the help of some other functions
    • void A( )
    • {
    • ------
    • ------
    • B( )
    • ----
    • ----
    • }
    • void B( )
    • {
    • ---
    • ---
    • A()
    ----
    • ----
    • }
    TYPES OF DIRECT RECURSION

     No Tail / Head Recursion


     Tail Recursion

     Linear Recursion

     Binary Recursion

     Tree Recursion

     Nested Recursion
    PARTS OF RECURSIVE FUNCTION
     Base Case /Stopping case
     Recursive Case/Inductive Case

     Base Case

     The case in which we end our recursion

     Recursive Case

     The case in which we call it self.

     Infinite Recursion

     Forgetting the base case leads to infinite recursion


    USE OF RECURSIVE FUNCTIONS
    Recursive functions are generally defined for the following tasks.
    For displaying series
    For performing calculations
    For displaying series
    class xyz
    {
    public void test (int i)
    {
    if(i>5)
    return; Base case
    else
    {
    System.out.print(i+”, “);
    test(i+1); Recursive case
    }}
    public static void main (String args[ ])
    {
    xyz ob = new xyz( );
    ob.test(1)}}
    }}
    OUTPUT : 1,2,3,4,5
    RECURSION VS. ITERATION
     Recursion is a substitute of iterative statements (loop).
     When a function calls a new set of a local variables and
    parameters are allocated.
     The recursive version of most routines may execute a bit
    slower than their iterative equivalents ,because of the
    overhead of the repeated function calls.
     The main advantage of recursive function is that you can
    use to create and simpler version.
     Recursive functions are useful in evaluating certain types
    of mathematical function.
     Recursive function is a very useful way of creating
    dynamic data structures such as linked list & Binary tree.
    TYPES OF DIRECT RECURSION
     Linear Recursion
     Example sum of numbers
     For performing calculations:

     Recursive function to calculate 1+2+3+4+5

     class xyz

    {

     public int cal (int i)

    {

     if(i>5)

     return 0;

     else

     return (i + cal(i+1); Linear recursion


    }

     public static void main (String args[ ])

    {

     xyz ob = new xyz ();

     int s = ob.cal(1);

     System.out.print(“Total=“+s);

     }}
     Tail Recursion
     Example
     Display reverse even numbers from 20 to 2

     // 20 18 16 14……..4 2

     class xyz

     {

     public void test (int i)

     {

     if(i<2)

     return ;

     else

     {

     System.out.print(i+” “);

     test(i -2); tail recursion


     }

     public static void main (String args[ ])

     {

     xyz ob = new xyz ();

     ob.test(20);

     }}
     Head recursion
     Example
     Display reverse even numbers from 20 to 2
     // 20 18 16 14……..4 2
     class xyz
     {
     public void test (int i)
     {
     if(i>20)
     return ;
     else
     {
     test(i +2); No tail/Head recursion
     System.out.print(i+” “);
     }
     public static void main (String args[ ])
     {
     xyz ob = new xyz ();
     ob.test(2);
     }}
     Binary recursion Example Binary Search
     public int binary_search(int a[ ],int sn,int lb,int ub)
     if(lb >ub) lb = lower bound
    ub = upper bound
     return -1; sn = number to be searched
     int mi = (lb+ub)/2; a[] = array variable
     if(sn.compareTo(a[mi])>0) mi = middle index
     return binary_search(a,sn,mi+1,ub)
     else if(sn.compareTo(a[mi])<0) Binary recursion
     return binary_search(a,sn,lb,mi-1);
     else
     return mi;
     }
     Tree Recursion
     Example : Fibonacci series

     public int fib(int n)

     {

     if(n<=1)

     {

     return; Tree recursion


     }

     else

     {

     return fib(n-1)+fib(n-2);

     }

     }
    Thank you…

    You might also like