recursive method to comput psF(n)


DevX Home    Today's Headlines   Articles Archive   Tip Bank   Forums   

Results 1 to 5 of 5

Thread: recursive method to comput psF(n)

Hybrid View

  1. #1
    Join Date
    Oct 2005
    Location
    Chicago
    Posts
    24

    recursive method to comput psF(n)

    can someone explain to me how recursive methods work
    we went over it in class but i was not listening and now i'am to scared to tell the teacher. can't focus for more than 50 mins at a time
    how can you use a method within it self

    static int psF(int n) {
    if(n<2)
    return n;
    else
    return 2*psF(n-1)+psF(n-2);
    }

    how can he use a method call with in a method
    Last edited by Mcody2; 11-30-2006 at 03:30 PM.

  2. #2
    Join Date
    Apr 2006
    Posts
    28
    Here your fibonacci program
    import javax.swing.*;
    public class Fibo
    {

    static long fibo(int n) {
    if(n==0) //Stop
    return n;
    else if (n==1)
    return 1;
    else
    return fibo(n-1)+fibo(n-2);

    }
    public static void main(String[] args)
    {
    String stNo=JOptionPane.showInputDialog("Enter n>0: ");
    int n=Integer.parseInt(stNo);
    JOptionPane.showMessageDialog(null,"Fibonacci number at n "+n+" is "+fibo(n));
    }

    }

  3. #3
    Join Date
    Jul 2005
    Location
    the Netherlands
    Posts
    128
    Quote Originally Posted by Mcody2
    can someone explain to me how recursive methods work
    we went over it in class but i was not listening and now i'am to scared to tell the teacher. can't focus for more than 50 mins at a time
    how can you use a method within it self

    static int psF(int n) {
    if(n<2)
    return n;
    else
    return 2*psF(n-1)+psF(n-2);
    }

    how can he use a method call with in a method
    If you don't understand some code, try putting some System.out.println() statements in it to see what's happening to the variables in your code.
    The previous' posters code can even be shortened with only one if-statement:
    Code:
    public class Fibo {
    
        public static int fibonacci(int n) {
            System.out.println("********************************************");
            System.out.println("Begin of the method, n = "+n);
            if(n < 2) {
                System.out.println(" - returning: "+n);
                return n;
            } else {
                System.out.println(" - calling fibonacci("+n+"-1)+fibonacci("+n+"-2)");
                return fibonacci(n-1)+fibonacci(n-2);
            }
        }
        
        public static void main(String[] args) {
            int N = 4;
            System.out.println("\n\nAnswer fibonacci("+N+") = "+fibonacci(N));
        }
    }
    When you run the code the following will be printed:
    Code:
    ********************************************
    Begin of the method, n = 4,     
     - calling fibonacci(4-1)+fibonacci(4-2)     [1]-+
    ********************************************     |
    Begin of the method, n = 3,                      |
     - calling fibonacci(3-1)+fibonacci(3-2)      <--+ [2]-+
    ********************************************     |     |
    Begin of the method, n = 2,                      |     |
     - calling fibonacci(2-1)+fibonacci(2-2)         |  <--+ [3]-+
    ********************************************     |     |     |
    Begin of the method, n = 1,                      |     |     |
     - returning: 1                                  |     |  <--+
    ********************************************     |     |     |
    Begin of the method, n = 0,                      |     |     |
     - returning: 0                                  |     |  <--+
    ********************************************     |     |
    Begin of the method, n = 1,                      |     |
     - returning: 1                                  |  <--+
    ********************************************     |
    Begin of the method, n = 2,                      |
     - calling fibonacci(2-1)+fibonacci(2-2)      <--+ [4]-+
    ********************************************           |
    Begin of the method, n = 1,                            |
     - returning: 1                                     <--+
    ********************************************           |
    Begin of the method, n = 0,                            |
     - returning: 0                                     <--+
    
    
    Answer fibonacci(4) = 3
    I've drawn some arrows to show how the flow of the recursive calls work. As you can see, the number 1 gets returned three times, which is the answer.
    Hope it's clear to you now.

    Good luck.

  4. #4
    Join Date
    Jul 2005
    Location
    the Netherlands
    Posts
    128
    Quote Originally Posted by prometheuzz
    ...
    The previous' posters code can even be shortened with only one if-statement:
    ...
    If you really want to shorten it, you can even put it all in one line:
    Code:
    public static int fib(int n) {
      return n < 2 ? n : fib(n-1)+fib(n-2);
    }
    ; )

  5. #5
    Join Date
    Oct 2005
    Location
    Chicago
    Posts
    24
    thanks prometheuzz that helped alot, also good advice about inserting print lines i remember reading that in my text somewere thought it was a waste of time lol now i see it is good programming practice.

Similar Threads

  1. Permutation recursive help
    By i.mogal in forum Java
    Replies: 2
    Last Post: 09-03-2008, 10:14 AM
  2. Replies: 2
    Last Post: 08-05-2006, 10:40 PM
  3. Comparing .NET delegates
    By Quimbly in forum .NET
    Replies: 1
    Last Post: 04-21-2006, 11:51 AM
  4. Replies: 1
    Last Post: 04-13-2006, 04:57 AM
  5. Replies: 3
    Last Post: 04-13-2001, 09:13 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
HTML5 Development Center
 
 
FAQ
Latest Articles
Java
.NET
XML
Database
Enterprise
Questions? Contact us.
C++
Web Development
Wireless
Latest Tips
Open Source


   Development Centers

   -- Android Development Center
   -- Cloud Development Project Center
   -- HTML5 Development Center
   -- Windows Mobile Development Center