Scribd Logo
Upload

Welcome to Scribd!

  • 46 views

    Recursive Functions

    Uploaded by

    yash
    Recursive functions call themselves during their execution. They are useful for evaluating mathematical functions and accessing dynamic data structures like linked lists and binary trees recursively. To compute the value of a recursive function like factorial, one plugs the recursive definition into itself until reaching the base case. Recursive algorithms can be implemented on a computer by defining a recursive function that calls itself, ultimately terminating at a base case.

    Copyright:

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

    Recursive Functions

    Uploaded by

    yash
    46 views32 pages
    Recursive functions call themselves during their execution. They are useful for evaluating mathematical functions and accessing dynamic data structures like linked lists and binary trees recursively. To compute the value of a recursive function like factorial, one plugs the recursive definition into itself until reaching the base case. Recursive algorithms can be implemented on a computer by defining a recursive function that calls itself, ultimately terminating at a base case.

    Copyright

    © © All Rights Reserved

    Available Formats

    PPT, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Recursive functions call themselves during their execution. They are useful for evaluating mathematical functions and accessing dynamic data structures like linked lists and binary trees recursively. To compute the value of a recursive function like factorial, one plugs the recursive definition into itself until reaching the base case. Recursive algorithms can be implemented on a computer by defining a recursive function that calls itself, ultimately terminating at a base case.

    Copyright:

    © All Rights Reserved
    Download as PPT, PDF, TXT or read online from Scribd
    Download as ppt, pdf, or txt
    46 views32 pages

    Recursive Functions

    Uploaded by

    yash
    Recursive functions call themselves during their execution. They are useful for evaluating mathematical functions and accessing dynamic data structures like linked lists and binary trees recursively. To compute the value of a recursive function like factorial, one plugs the recursive definition into itself until reaching the base case. Recursive algorithms can be implemented on a computer by defining a recursive function that calls itself, ultimately terminating at a base case.

    Copyright:

    © All Rights Reserved
    Download as PPT, PDF, TXT or read online from Scribd
    Download as ppt, pdf, or txt
    You are on page 1of 32

    What is a Recursive Function ?

    Recursion is the process of defining something


    in terms of itself.
    A recursive function is one which calls itself.
    What is the need for Recursive Functions ?
     Recursive functions are sometimes the simplest answer to a
    calculation. However there is always an alternative non-
    recursive
    solution available too. This will normally involve the use of a
    loop, and may lack the elegance of the recursive solution.

     Recursive functions are useful in evaluating certain types of


    mathematical function and certain dynamic data structures such
    as linked lists or binary trees. Recursion is a very useful way of
    creating and accessing these structures.
    Recursive Functions Factorial

    A:INITIALIZATION: 0!= 1
    RECURSION: n != n · (n -1)!

    To compute the value of a recursive


    function, e.g. 5!, one plugs into the
    recursive definition obtaining expressions
    involving lower and lower values of the
    function, until arriving at the base case.
    The Binomial coefficients arise in several
    applications:
    1) Combinatorics/Probability (n choose
    k): C (n,k) = the number of different
    groups of size k from an initial group
    of size n
    2) Algebra:
    C (n,k) = coefficient of k th term in the
    expansion of the n th binomial power
    (x + y )n  n
    Commonly used notation: C (n, k )   
    k
    Recursive Algorithms Computer
    Implementation
    int factorial(int n){
    if (n==0) return 1;
    return n*factorial(n-1);
    }

    Compute 5!

    L16 6
    Recursive Algorithms Computer
    Implementation
    long factorial(int n){
    if (n<=0) return 1;
    return n*factorial(n-1);
    }
    f(5)=
    5·f(4)

    L16 7
    Recursive Algorithms Computer
    Implementation
    long factorial(int n){
    if (n<=0) return 1;
    return n*factorial(n-1);
    }
    f(4)= f(5)=
    4·f(3) 5·f(4)

    L16 8
    Recursive Algorithms Computer
    Implementation
    long factorial(int n){
    if (n<=0) return 1;
    return n*factorial(n-1);
    }

    f(3)= f(4)= f(5)=


    3·f(2) 4·f(3) 5·f(4)

    L16 9
    Recursive Algorithms Computer
    Implementation
    long factorial(int n){
    if (n<=0) return 1;
    return n*factorial(n-1);
    }

    f(2)= f(3)= f(4)= f(5)=


    2·f(1) 3·f(2) 4·f(3) 5·f(4)

    L16 10
    Recursive Algorithms Computer
    Implementation
    long factorial(int n){
    if (n<=0) return 1;
    return n*factorial(n-1);
    }

    f(1)= f(2)= f(3)= f(4)= f(5)=


    1·f(0) 2·f(1) 3·f(2) 4·f(3) 5·f(4)

    L16 11
    Recursive Algorithms Computer
    Implementation
    long factorial(int n){
    if (n<=0) return 1;
    return n*factorial(n-1);
    }

    f(0)= f(1)= f(2)= f(3)= f(4)= f(5)=


    1 1·f(0) 2·f(1) 3·f(2) 4·f(3) 5·f(4)

    L16 12
    Recursive Algorithms Computer
    Implementation
    long factorial(int n){
    if (n<=0) return 1;
    return n*factorial(n-1);
    }

    1·1= f(2)= f(3)= f(4)= f(5)=


    1 2·f(1) 3·f(2) 4·f(3) 5·f(4)

    L16 13
    Recursive Algorithms Computer
    Implementation
    long factorial(int n){
    if (n<=0) return 1;
    return n*factorial(n-1);
    }

    2·1= f(3)= f(4)= f(5)=


    2 3·f(2) 4·f(3) 5·f(4)

    L16 14
    Recursive Algorithms Computer
    Implementation
    long factorial(int n){
    if (n<=0) return 1;
    return n*factorial(n-1);
    }

    3·2= f(4)= f(5)=


    6 4·f(3) 5·f(4)

    L16 15
    Recursive Algorithms Computer
    Implementation
    long factorial(int n){
    if (n<=0) return 1;
    return n*factorial(n-1);
    }

    4·6= f(5)=
    24 5·f(4)

    L16 16
    Recursive Algorithms Computer
    Implementation
    long factorial(int n){
    if (n<=0) return 1;
    return n*factorial(n-1);
    }
    5·24=
    120

    L16 17
    Recursive Algorithms Computer
    Implementation
    long factorial(int n){
    if (n<=0) return 1;
    return n*factorial(n-1);
    }
    Return 5!
    = 120

    L16 18
    public void recursion(int y)
    {
    if(y>0)
    {
    System.out.println(y);
    recursion(y-1);
    System.out.println(y);
    }
    }
    Sample Recursive Function
    int func ( int n)
    {
    if ( n= = 1 )
    return( 1 );
    else
    return( n + func ( n - 1)) ;
    }
    http://www.programmerinterview.com/index.php/recursion/explanati
    on-of-recursion/

    http://www.cs.wustl.edu/~kjg/cse131/modules/recursion/lab.html
    Function Stack –

    https://www.youtube.com/watch?v=jRcll9qY6b0

    Recursion
    https://www.youtube.com/watch?v=PORo1ut9kMs
    Exercise

    Write the recursive version of the


    1. Power function
    2. Fibonacci value
    3. HCF
    void func(String s,int i)
    {
    if (i>=0)
    {
    char ch=s.charAt(i);
    System.out.print(ch);
    func(s,i-1);
    System.out.print(ch);
    }

    }
    void display()throws IOException
    {
    DataInputStream in=new DataInputStream(System.in);
    System.out.print("Enter any word :");
    String s=in.readLine();
    func(s,s.length( )-1);
    }
    import java.io.*;
    class recursive1
    {static int i=0;String c="";
    String rev(String s)
    {
    if (i<s.length())
    {
    char ch=s.charAt(i);i++;
    rev(s);
    c=c+ch;
    return c ;
    }
    else return "";
    }
    void display()throws IOException
    {
    DataInputStream in=new DataInputStream(System.in);
    System.out.println("Enter any word :");
    String s=in.readLine();
    System.out.println("Reverse of the word = "+rev(s));

    }}
    class funct
    {
    static int i=2;
    public static int fun(int num)
    {
    if(num%i==0 && num!=i)
    return 0;
    if(i<num)
    {
    i++;
    return fun(num);
    }
    else
    return 1;

    }
    }
    public static boolean isPrime(int num)
    { int result;
    result =Prime(num, num-1);
    if(result>1)
    return false;
    else
    return true;
    }
    public static int Prime(int number, int i)
    {
    int prime= number%i;
    if (prime >0 && i>1)
    {
    return Prime(number, i - 1);
    }
    else
    {
    return i;
    }

    You might also like