6 Replies Latest reply: Dec 16, 2006 11:14 AM by 800282 RSS

    recursive method

    807607
      hi!
      How this recursive method works?
      ex: F(3) : out put is 1
      F(6): out put is 7
      class Recursion
      {
          int F( int n){
            if ( n <= 1 )
            {
                 return 0;
            }
                         
            else if ( n == 2 )
            {
              return 1;
              }
                 
              else
             {
                    
              return F(n-1) + F(n-2)+ F(n - 3);
             }
      }
      
      
          public static void main(String[]args)
          {      
               Recursion r= new Recursion();     
                 System.out.println("Rec:  "+r.F(6)); 
             }
      }
        • 1. Re: recursive method
          800322
          It works like all recursive methods work: it calls itself.

          What exactly is your question?
          • 2. Re: recursive method
            807607
            My question is how the mothod calls itself:
            if you can please explain step by step
            • 3. Re: recursive method
              800322
              My question is how the mothod calls itself:
              if you can please explain step by step
              first, method F is called. Then it does something, then it calls method F, and uses the return values to calculate its final result.
              • 4. Re: recursive method
                800282
                My question is how the mothod calls itself:
                if you can please explain step by step
                Here you go:
                F(6) =
                                                  6
                                                 /|\
                                                / | \
                                               /  |  \
                                              /   |   \
                                             /    |    \
                                            /     |     \
                                           /      |      \
                                          /       |       \
                                         /        |        \
                                        /         |         \
                                       /          |          \
                                      /           |           \
                                     /            |            \
                                    /             |             \
                                   /              |              \
                                  /               |               \
                                 /                |                \
                                5                 4                 3
                               /|\               /|\               /|\
                              / | \             / | \             2 1 0
                             /  |  \           /  |  \            |
                            /   |   \         3   2   1          (+1)
                           /    |    \       /|\   \
                          /     |     \     2 1 0  (+1)
                         /      |      \    |
                        /       |       \  (+1)
                       4        3        2
                      /|\      /|\       |
                     / | \    2 1 0     (+1)
                    /  |  \    \
                   3   2   1   (+1)
                  /|\   \
                2 1 0  (+1)
                |
                (+1)

                = +1 +1 +1 +1 +1 +1 +1
                = 7
                And don't ask for the tree where n > 6!
                ; )
                • 5. Re: recursive method
                  807607
                  thank you very much for your help.
                  • 6. Re: recursive method
                    800282
                    thank you very much for your help.
                    You're welcome.
                    When code is a bit confusing for you, try to add some System.out.println's in it to see what is being called and returned.
                    Running your code like this:
                    class Recursion {
                        
                        int counter = 1;
                        
                        int F(int n) {
                            System.out.print("\nRecursive call ("+(counter++)+") --> n="+n);
                            if(n <= 1 ) {
                                System.out.print("\treturn 0");
                                return 0;
                            } else if(n == 2) {
                                System.out.print("\treturn 1");
                                return 1;
                            } else {
                                System.out.print("\tcalling: F("+(n-1)+") + F("+(n-2)+")+ F("+(n-3)+")");
                                return F(n-1) + F(n-2) + F(n-3);
                            }
                        }
                        
                        public static void main(String[]args) {   
                            Recursion r= new Recursion(); 
                            System.out.println("\nRec:  "+r.F(6)); 
                        }
                    }
                    produces the followinf output:
                    Recursive call (1) --> n=6     calling: F(5) + F(4)+ F(3)
                    Recursive call (2) --> n=5     calling: F(4) + F(3)+ F(2)
                    Recursive call (3) --> n=4     calling: F(3) + F(2)+ F(1)
                    Recursive call (4) --> n=3     calling: F(2) + F(1)+ F(0)
                    Recursive call (5) --> n=2     return 1
                    Recursive call (6) --> n=1     return 0
                    Recursive call (7) --> n=0     return 0
                    Recursive call (8) --> n=2     return 1
                    Recursive call (9) --> n=1     return 0
                    Recursive call (10) --> n=3     calling: F(2) + F(1)+ F(0)
                    Recursive call (11) --> n=2     return 1
                    Recursive call (12) --> n=1     return 0
                    Recursive call (13) --> n=0     return 0
                    Recursive call (14) --> n=2     return 1
                    Recursive call (15) --> n=4     calling: F(3) + F(2)+ F(1)
                    Recursive call (16) --> n=3     calling: F(2) + F(1)+ F(0)
                    Recursive call (17) --> n=2     return 1
                    Recursive call (18) --> n=1     return 0
                    Recursive call (19) --> n=0     return 0
                    Recursive call (20) --> n=2     return 1
                    Recursive call (21) --> n=1     return 0
                    Recursive call (22) --> n=3     calling: F(2) + F(1)+ F(0)
                    Recursive call (23) --> n=2     return 1
                    Recursive call (24) --> n=1     return 0
                    Recursive call (25) --> n=0     return 0
                    Rec:  7
                    Good luck.