2 Replies - 352 Views - Last Post: 05 December 2017 - 05:40 AM Rate Topic: -----

#1 chloeCodes   User is offline

  • D.I.C Head

Reputation: 4
  • View blog
  • Posts: 178
  • Joined: 05-January 17

Infinite Recursion

Posted 04 December 2017 - 12:30 PM

Hi!
I have written some code that finds a particular node in a Binary Search tree data structure.
I get a stack overflow error pointing at the bold line. This means that the code I have written
uses infinite recursion. Could anyone help me understand how this causes infinitive recursion.
Thanks!

private Node find(String word)
{
 if(rootNode != null) 
 {
     return findNode(rootNode, new Node(word));
 }
 return null;
}
//Helper method for find
private Node findNode(Node search, Node node)
{
 if(search == null) //Base case
 {
     return null;
 } 
 if(search.getData().equals(node.getData()))
 {
     return search;
 }
 else
 {
     [b]Node returnNode = findNode(search.getLeft(), node);[/b]
     if(returnNode == null)
     {
         returnNode = findNode(search.getRight(),node);
     }
     return returnNode;
 }
}



Is This A Good Question/Topic? 0
  • +

Replies To: Infinite Recursion

#2 macosxnerd101   User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12317
  • View blog
  • Posts: 45,416
  • Joined: 27-December 08

Re: Infinite Recursion

Posted 04 December 2017 - 12:34 PM

Add some println() statements to help you see precisely which nodes are being visited and whether the left note is being passed to the recursive call, or the right node. Compare this to what you expect should happen to the tree. This will help shed some light on the issue.

As I have mentioned in your previous threads, this is really what you should be doing at the start.
Was This Post Helpful? 2
  • +
  • -

#3 chloeCodes   User is offline

  • D.I.C Head

Reputation: 4
  • View blog
  • Posts: 178
  • Joined: 05-January 17

Re: Infinite Recursion

Posted 05 December 2017 - 05:40 AM

Hi Macos,

Because I'm adding huge words to an already huge collection size (1 million roughly) at run time I was getting
StackOverFlowException. So I thought I could make the algorithm iterative. Here is my iterative approach:
public int count(String target)
{
       int count=0;
       Node cursor=rootNode;
       while(cursor!=null)
       {
         int compare=target.compareTo(cursor.getData());
        if(compare==0)
        {
          count++;
          cursor = cursor.getLeft();
        } 
        else if(compare>0) 
            cursor=cursor.getRight();
         else
            cursor=cursor.getLeft();
       }
       //System.out.println(count);
       return count;
   }


I think this works! Thanks for all your help! Let me know however if anything about this method shouts out as being wrong!

Cheers! :)
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1