7 Replies - 328 Views - Last Post: 29 October 2017 - 12:57 PM Rate Topic: -----

#1 chloeCodes  Icon User is offline

  • D.I.C Head

Reputation: 3
  • View blog
  • Posts: 125
  • Joined: 05-January 17

Can't see the problem with my Recursive method

Posted 29 October 2017 - 03:27 AM

Hello,

I have written a method that (given a passed list of elements, and a number), should recursively calculate the number of
occurrences of that number within the list. For example if the passed list is [2,2,2], it should print 2 appears 3 times in the list.

My code is:
 public static int counterR(LispList<Integer> list, int number)
    {
       int counter=0;
       if(list.isEmpty())
       {
           //When the list becomes empty, return value of counter
           return counter;
       }
       else
       {
           Integer head = list.head();
           if(head.equals(number))
           {
               counter++;
               return counterR(list.tail(),counter);
           }
           else
           {
               return counterR(list.tail(),counter);
           }
       }
    } 


However, it is printing out that 2 appears 0 times in the past list. I am able to create the method iteratively. I can't seem to see where I have gone wrong, it makes complete sense my code. I would appreciate any pointers.
Cheers

Is This A Good Question/Topic? 0
  • +

Replies To: Can't see the problem with my Recursive method

#2 ndc85430  Icon User is online

  • D.I.C Lover
  • member icon

Reputation: 588
  • View blog
  • Posts: 2,477
  • Joined: 13-June 14

Re: Can't see the problem with my Recursive method

Posted 29 October 2017 - 04:10 AM

Each time you call the method, you're getting a local variable counter that is set to 0. Your method needs to take counter as an argument that you set to 0 the first time you call it. When you're doing things recursively, this is how you store state - by passing it down through each of the calls.

This post has been edited by ndc85430: 29 October 2017 - 04:16 AM

Was This Post Helpful? 1
  • +
  • -

#3 chloeCodes  Icon User is offline

  • D.I.C Head

Reputation: 3
  • View blog
  • Posts: 125
  • Joined: 05-January 17

Re: Can't see the problem with my Recursive method

Posted 29 October 2017 - 05:05 AM

Brilliant. That is something so important. I also have been working on a method which accepts a list of numbers [2,2,2]
and the number 2. Then, should return the position of where all the 2 occur so should return a list [0,1,2] as the 2's are stored in position 0,1 and 2 respectively.

My code:
public static LispList<Integer> returnPositions(LispList<Integer> ls, int item, int position)
{  
    if(ls.isEmpty())
    {
        //eventually the list will become empty
        return LispList.empty();   
    }
    else
    {
        //newList will contain the positions of number 2
        LispList<Integer> newList = returnPositions(ls.tail(),item,position);
        Integer head = ls.head();
        //If element at head == item
        if(head.equals(item))
        {
             newList.cons(position); //add position to newList
             position++;
             return returnPositions(ls.tail(),item,position);
        }
        else
        {
            //If head element is not equal to item
            return returnPositions(ls.tail(),item,position);
        }
    }
}
   
public static LispList<Integer> parseIntLispList(String str)
{
    String line = str.trim();
    String contents = line.substring(1,line.length()-1).trim(); 
    if(contents.length()==0||line.charAt(0)!='['||line.charAt(line.length()-1)!=']')
    {
        //empty() method defined in the LispList class
        return LispList.empty(); //return an Empty LispList
    }
    String[] nums = contents.split(",");
    //Initialise the LispList list to an empty LispList
    LispList<Integer> list = LispList.empty();
    //Going backwards in the nums array (right to left)
    //For each String in array variable nums
    for(int i=nums.length-1; i>=0; i--)
      {
       //Remove all trailing ends from string nums[i]
       String num = nums[i].trim(); 
       list = list.cons(Integer.parseInt(num));
      }
    return list;
}


I did what you did previously declared the counter within the parameters of the method header. So each time the method
is called, it doesn't get back to 0. However, I'm a bit confused on the base case, eventually list ls will become empty,
once each header has been checked, and the resultant tail is passed. So of course the method is return the empty list.I
wanted to return newList when list becomes empty, but it cannot see the variable in the step case. Any ideas? I think it is
something subtle that I'm yet to see!

Thank you.

This post has been edited by chloeCodes: 29 October 2017 - 08:34 AM

Was This Post Helpful? 0
  • +
  • -

#4 chloeCodes  Icon User is offline

  • D.I.C Head

Reputation: 3
  • View blog
  • Posts: 125
  • Joined: 05-January 17

Re: Can't see the problem with my Recursive method

Posted 29 October 2017 - 10:58 AM

ublic static LispList<Integer> returnPositionPlus(LispList<Integer> ls, int item, int position)
{   
    if(ls.isEmpty())
    {
        return LispList.empty();
    }
    else
    {
      LispList<Integer> newList = returnPosition(ls.tail(),item,position+1);
      //is the head the first element of ls, or ls.tail().head()?
      Integer head = ls.head();
      //if head = 2
      if(head.equals(item))
      {
          position++; //record position
          //When this statement is called where does it go back to
          return newList.cons(position); //Add to list
      }
      return newList;
    } 
}


When this line: return newList.cons(position); of code is executed, where does it actually return to? What line does it
return to in the code?
Was This Post Helpful? 0
  • +
  • -

#5 macosxnerd101  Icon User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12148
  • View blog
  • Posts: 45,160
  • Joined: 27-December 08

Re: Can't see the problem with my Recursive method

Posted 29 October 2017 - 11:11 AM

Whichever line invoked the specific instance of the method. Perhaps it would be worth reviewing a tutorial on methods. You may also find my tutorial on recursion, stacks, and trees helpful to better understand how recursive methods are processed.
Was This Post Helpful? 0
  • +
  • -

#6 ndc85430  Icon User is online

  • D.I.C Lover
  • member icon

Reputation: 588
  • View blog
  • Posts: 2,477
  • Joined: 13-June 14

Re: Can't see the problem with my Recursive method

Posted 29 October 2017 - 11:34 AM

So, think again about what we said earlier: with recursion, you build up the answer by passing something through each of the recursive calls, so that when you reach the base case, you'll have the complete thing to return. For this problem, what is the thing you're trying to build up?
Was This Post Helpful? 1
  • +
  • -

#7 chloeCodes  Icon User is offline

  • D.I.C Head

Reputation: 3
  • View blog
  • Posts: 125
  • Joined: 05-January 17

Re: Can't see the problem with my Recursive method

Posted 29 October 2017 - 11:53 AM

Yeah, I understand when we call the method recursively, we call the actual method itself, passing the required parameters. However,
newlist.cons(position), adds the element position to the newlist. When we return it, what part of the method does it go to. I take your point, and I will try and review it. I'm really good and control/return with normal methods. Recursion really confuses me though.
Was This Post Helpful? 0
  • +
  • -

#8 macosxnerd101  Icon User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12148
  • View blog
  • Posts: 45,160
  • Joined: 27-December 08

Re: Can't see the problem with my Recursive method

Posted 29 October 2017 - 12:57 PM

As I mentioned in your previous thread, add a bunch of println() statements in your method to help you see what is going on. Or use a debugger. These are important and necessary debugging skills every programmer needs to know. There is no time like the present to practice with them!
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1