This discussion is archived
1 2 Previous Next 24 Replies Latest reply: Nov 7, 2008 8:18 AM by 843785 RSS

Recursion:returning the largest value in a linked list

843785 Newbie
Currently Being Moderated
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 Newbie
    Currently Being Moderated
    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 Newbie
    Currently Being Moderated
    It hangs and does nothing.
  • 3. Re: Recursion:returning the largest value in a linked list
    843785 Newbie
    Currently Being Moderated
    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 Newbie
    Currently Being Moderated
    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 Newbie
    Currently Being Moderated
    As you've been told, remove the loop from your method.
  • 6. Re: Recursion:returning the largest value in a linked list
    843785 Newbie
    Currently Being Moderated
    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 Newbie
    Currently Being Moderated
    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 Newbie
    Currently Being Moderated
    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 Newbie
    Currently Being Moderated
    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 Newbie
    Currently Being Moderated
    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 Newbie
    Currently Being Moderated
    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 Newbie
    Currently Being Moderated
    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 Newbie
    Currently Being Moderated
    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 Newbie
    Currently Being Moderated
    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