Can't see the problem with my Recursive method

Page 1 of 1

7 Replies - 423 Views - Last Post: 29 October 2017 - 12:57 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=407248&amp;s=76405edaffa65c0c0d45b5593e03e97d&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

#1 chloeCodes

Reputation: 4
• Posts: 178
• 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
{
{
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

• I think you'll find it's "Dr"

Reputation: 785
• Posts: 3,191
• 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

#3 chloeCodes

Reputation: 4
• Posts: 178
• 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);
//If element at head == item
{
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

#4 chloeCodes

Reputation: 4
• Posts: 178
• 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);
{
position++; //record position
//When this statement is called where does it go back to
}
return newList;
}
}
```

When this line: return newList.cons(position); of code is executed, where does it actually return to? What line does it

#5 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12276
• Posts: 45,364
• 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.

#6 ndc85430

• I think you'll find it's "Dr"

Reputation: 785
• Posts: 3,191
• 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?

#7 chloeCodes

Reputation: 4
• Posts: 178
• 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.

#8 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12276
• Posts: 45,364
• 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!