1 2 Previous Next 24 Replies Latest reply: Nov 7, 2008 10:18 AM by 843785 RSS

    Recursion:returning the largest value in a linked list

    843785
      import java.io.*;
      import java.util.*;
      
      
      class Node{
           int num;
           Node next;
           
           Node(int n){
                num = n;
                next = null;
           }
      }
      
      class RecursivePrint{
           public static void main(String[] args){
           
                Node np, last;
                Node top = null;
                last = null;
                for(int i = 1; i <11; i++){
                     np = new Node(i);
                     if(top==null)top = np;
                          else
                     last.next = np;
                     last = np;
                }
                
                int x =Largest(top);
               System.out.println("large is "+ x);
      
                
           }//end main
      
           public static int Largest(Node top){
                int large = 0;
                
                if(top==null){
                     return 0;
                }
                     while(top!=null){
                 if(top.num > large){
                
                     large = top.num;
                     //top = top.next;
                     
                }
                Largest(top.next);     
                
           }//while
                     
           
           
           return large;
      
           }
      }//end class
           
      I am trying to return the largest value in a linked list (10) in this case.  when I do it withour recurrsion it works ok, but when I try it with recurrsion it dies.  The logic seems ok to me, cannot figure why it dies.
        • 1. Re: Recursion:returning the largest value in a linked list
          843785
          chetah wrote:
          I am trying to return the largest value in a linked list (10) in this case. when I do it withour recurrsion it works ok, but when I try it with recurrsion it dies.
          Define "it dies". Do you get an exception? Does it simply hang and not continue? Does it explode and send burning monkeys flying across the room?
          • 2. Re: Recursion:returning the largest value in a linked list
            843785
            It hangs and does nothing.
            • 3. Re: Recursion:returning the largest value in a linked list
              843785
              JoachimSauer wrote:
              Does it explode and send burning monkeys flying across the room
              Hope so!
              • 4. Re: Recursion:returning the largest value in a linked list
                843785
                while(top!=null){
                           if(top.num > large){
                          
                               large = top.num;
                               //top = top.next; 
                               
                          }
                If you enter this loop you aint gettin out boi!
                Doesn't even get to the recursive bit.

                Edit: Missed a bit of code off but you get the idea
                • 5. Re: Recursion:returning the largest value in a linked list
                  843785
                  As you've been told, remove the loop from your method.
                  • 6. Re: Recursion:returning the largest value in a linked list
                    843785
                    while(top!=null){
                              if(top.num > large){
                              
                                   large = top.num;
                                   //top = top.next;
                                   Large(top.next); //Even when I have it in this place, the result is the same, do difference,
                              }
                    • 7. Re: Recursion:returning the largest value in a linked list
                      843785
                      mintedjo wrote:
                      JoachimSauer wrote:
                      Does it explode and send burning monkeys flying across the room
                      Hope so!
                      Let's all get another [piercing |http://k43.pbase.com/g6/36/640536/2/73261872.QHixqEAb.jpg] today
                      • 8. Re: Recursion:returning the largest value in a linked list
                        843785
                        chetah wrote:
                        Large(top.next); //Even when I have it in this place, the result is the same, do difference,
                        We told you to remove the loop. Remove the entiry line "while..." and the matching closing brace. You don't need it.
                        • 9. Re: Recursion:returning the largest value in a linked list
                          843785
                          public static int Largest(Node top){
                                    int large = 0;
                                    
                                    if(top==null){
                                         return 0;
                                    }
                                    
                                    if(top.num > large){
                                    
                                         large = top.num;
                                         //top = top.next;
                                         Largest(top.next);
                                    }
                                         
                               return large;
                               }
                          Initially I had the above, it return only 1 that was the reason for puting the loop.
                          • 10. Re: Recursion:returning the largest value in a linked list
                            843785
                            Please use the CODE-button when posting code in the future, it makes it more readable.

                            Also, please call your method largest(), as methods should start with a lower-case letter.

                            The problem you have is that you ignore the return value of your recursive call.

                            Remember "largest(top.next)" effectively means "get the largest number in the rest of the list".

                            So you need to compare your current largest number with the result of that method and return the bigger one of the two.
                            • 11. Re: Recursion:returning the largest value in a linked list
                              843785
                              chetah wrote:
                              public static int Largest(Node top){
                                        int large = 0;
                                        
                                        if(top==null){
                                             return 0;
                                        }
                                        
                                        if(top.num > large){
                                        
                                             large = top.num;
                                             //top = top.next;
                                             Largest(top.next);
                                        }
                                             
                                   return large;
                                   }
                              Initially I had the above, it return only 1 that was the reason for puting the loop.
                              You don't seem to understand recursion or variable scope.
                              int large = 0;
                              large is a different variable inside each instance of the method.
                              So when you get back up to the value 1 from the recursive calls its just comparing 1 to 0

                              Here's a solution...
                                   public static int Largest(Node top){
                                        if(top.next != null){
                                             if(Largest(top.next) > top.num)
                                                  return Largest(top.next);}
                                        return top.num;
                                   }
                              • 12. Re: Recursion:returning the largest value in a linked list
                                843785
                                mintedjo wrote:
                                     public static int Largest(Node top){
                                          if(top.next != null){
                                               if(Largest(top.next) > top.num)
                                                    return Largest(top.next);}
                                          return top.num;
                                     }
                                That's craptastic.
                                • 13. Re: Recursion:returning the largest value in a linked list
                                  843785
                                  DrLaszloJamf wrote:
                                  mintedjo wrote:
                                       public static int Largest(Node top){
                                            if(top.next != null){
                                                 if(Largest(top.next) > top.num)
                                                      return Largest(top.next);}
                                            return top.num;
                                       }
                                  That's craptastic.
                                  Its better than something that doesn't work :-D
                                  I didn't claim it was a good answer because, well I'm not a good programmer...
                                  In fact, if it was a good answer, i wouldn't know, i would assume it wasn't good because it was written by me :-)
                                  • 14. Re: Recursion:returning the largest value in a linked list
                                    843785
                                    mintedjo wrote:
                                    DrLaszloJamf wrote:
                                    mintedjo wrote:
                                         public static int Largest(Node top){
                                              if(top.next != null){
                                                   if(Largest(top.next) > top.num)
                                                        return Largest(top.next);}
                                              return top.num;
                                         }
                                    That's craptastic.
                                    Its better than something that doesn't work :-D
                                    I didn't claim it was a good answer because, well I'm not a good programmer...
                                    In fact, if it was a good answer, i wouldn't know, i would assume it wasn't good because it was written by me :-)
                                    You know your code is craptastic; I was just warning the OP.

                                    It's Friday, I'm feeling generous:
                                    public static int largest(Node n) {
                                        return (n==null)? Integer.MIN_VALUE : Math.max(n.num, largest(n.next));
                                    }
                                    1 2 Previous Next