Results 1 to 15 of 15
Thread: Recursion Problems. Pls Help!
 06142010, 09:00 AM #1Member
 Join Date
 Jun 2010
 Posts
 12
 Rep Power
 0
Recursion Problems. Pls Help!
Hi there,
I'm currently having difficulties in implementing fully recursive methods (those which do not use loops at all) and was wondering if anyone can give me a hand since i can't seem to grasp this topic.
the first method to implement is
boolean allEqual(int[] a, int start, int end) that checks if all elements in the array a from start to end are equal.
my code is as follows as I cannot seem to understand how to implement it.
public static boolean allEqual(int[] a, int start, int end){
if (start==end) return true;
boolean success = allEqual(a,start,end);
if (success) return true;
success = allEqual(a,start+1,end);
return success;
I'm not entirely sure if my base case is correct, so if someone can point that out it would be great. Returning a boolean from a recursive method confuses me. :confused:
the other method is
boolean linearSearch(int[] a, int x, int start, int end) that checks if the array a contains the element x anywhere between the indices start and end.
and what i have done is
public static boolean linearSearch(int[] a, int x, int start, int end){
if (start==end) return a[start]==x;
if (a[start]>a[end])
return linearSearch (a, x, start+1, end);
else return false;
}
again sorry, if my implementation looks like non sense. I have only recently started to understand how to implement basic recursive methods  ones that don't deal with arrays such as factorials and harmonicSums.
 06142010, 09:38 AM #2Senior Member
 Join Date
 Feb 2010
 Location
 Ljubljana, Slovenia
 Posts
 470
 Rep Power
 7
About the equality checker, if you think about it, you have two base cases, or as I prefer to call them, exit conditions. Either all elements are equal and you return true, or an element is not equal to all the others and you return false. Currently, your method can't return a false.
Ever seen a dog chase its tail? Now that's an infinite loop.
 06142010, 09:44 AM #3Member
 Join Date
 Jun 2010
 Posts
 12
 Rep Power
 0
Ohhh alright, so for every recursive boolean method, you'd need to have two exit conditions? I tried adding in
if (!(start==end)) return false;
this seems to make every case return false now though :confused:
 06142010, 09:44 AM #4Senior Member
 Join Date
 Aug 2009
 Posts
 2,388
 Rep Power
 9
Your equality checker doesn't have the body that actually does the comparison for elements in the passed in array a.
You need an if that looks something like
Java Code:if(a[start] != a[start +1]) return false;
 06142010, 02:13 PM #5Senior Member
 Join Date
 Feb 2010
 Location
 Ljubljana, Slovenia
 Posts
 470
 Rep Power
 7
The exit condition
Java Code:if(start == end) return true;
Also, your method would loop infinitely because of this:
Java Code:public static boolean allEqual(int[] a, int start, int end){ if (start==end) return true; boolean success = allEqual(a,start,end); //this calls the method with the //same parameters if (success) return true; success = allEqual(a,start+1,end); return success; }
Java Code:int recursive(int n) { return recursive(n); //no modification of n variable before recursive call }
Java Code:int n = 10, sum = 0; while(n != 0) { sum += n; }
I'll give you the solution, but in pseudocode, you translate it into valid Java:
Java Code:if start and end are equal return true if variable with index start doesn't equal variable with index end return false call method again with start incremented by 1
Ever seen a dog chase its tail? Now that's an infinite loop.
 06142010, 03:02 PM #6
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,290
 Blog Entries
 7
 Rep Power
 24
Maybe my schizophrenic example applies here as well: suppose there's me, the big mouthed mr KnowItAll who claims he can check array elements for being all equal and there's my intelligent, a bit shy friend who is highly intelligent. When I'm given an array and a start and end index I can do the simple stuff: when both start and end are equal I assume there are no elements to be checked so I return true. I can also check two elements (one at the start and one at the end); when they're not equal I return false; otherwise I give the rest of the array to my shy and intelligent friend; here goes:
Java Code:boolean me(int[] a, int start, int end) { if (start == end) return true; if (a[start] != a[end]) return false; return friend(a, start+1, end); }
Java Code:boolean me(int[] a, int start, int end) { if (start == end) return true; if (a[start] != a[end]) return false; return me(a, start+1, end); }
kind regards,
Jos
 06142010, 04:27 PM #7Member
 Join Date
 Jun 2010
 Posts
 12
 Rep Power
 0
Wow! Thanks r035198x, m00nchile, and JosAH
All your tips helped out A LOT. I never thought about writing it in pseudocode beforehand, that in turn makes this a whole lot easier, seeing how I don't think recursively yet. So it doesn't come naturally to me yet.
And the schizophrenic analogy is simply genius . If that was the way we were taught in school. Instead of out of the book verbatim. University would be a whole heck of a lot easier!
Now i can tackle the rest of these 8 methods with more understanding about recursion. Thanks everyone!
 06142010, 04:43 PM #8
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,290
 Blog Entries
 7
 Rep Power
 24
 06142010, 05:58 PM #9Member
 Join Date
 Jun 2010
 Posts
 12
 Rep Power
 0
Would the pseudocode for this method
boolean linearSearch(int[] a, int x, int start, int end) that checks if the array a contains the element x anywhere between the indices start and end.
be
if a[start] equals to x , a[start] is x
therefore return true
if end doesn't equal to x
return false
increment start by 1
?
 06142010, 06:05 PM #10Senior Member
 Join Date
 Feb 2010
 Location
 Ljubljana, Slovenia
 Posts
 470
 Rep Power
 7
Almost.
If start equals end and a[start] does not equal x
return false
If a[start] equals x
return true
call function with start incremented by 1
If you simply define your exit condition if a[end] doesn't equal x, you'll get a false even if the array contains the element, but not at the index end.Ever seen a dog chase its tail? Now that's an infinite loop.
 06142010, 06:16 PM #11Member
 Join Date
 Jun 2010
 Posts
 12
 Rep Power
 0
Thanks a lot. I'm starting to get the hang of it now, just gotta pay attention to minor details so I can get rid of logical errors such as that one. Thanks!
 06142010, 06:35 PM #12Senior Member
 Join Date
 Feb 2010
 Location
 Ljubljana, Slovenia
 Posts
 470
 Rep Power
 7
Exactely, well put. Now, the best way to get the hang of recursion is with a few simple mathemtacial algorithms, like calculating x to the y, the factorial of n, the fibonacci sequence etc.
Ever seen a dog chase its tail? Now that's an infinite loop.
 06142010, 07:01 PM #13
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,290
 Blog Entries
 7
 Rep Power
 24
Don't write down your pseudo code and think wham, bam, ready; because you have written down your intentions, not the instructions that have to be executed by an extremely dumb thing. Read your own pseudo code as if you were that dumb thing (I'm extremely good at that). Be extremely dumb but awfully exact and try to interpret that pseudo code. You'd be surprised at the outcome and then it's time to rewrite your pseudo code.
kind regards,
Jos
 06152010, 08:21 AM #14Senior Member
 Join Date
 Feb 2010
 Location
 Ljubljana, Slovenia
 Posts
 470
 Rep Power
 7
The way I explain how thick computers are to my friends who aren't techsavvy is like this: say you're sitting on the couch with a friend, and you ask him to bring you a beer. If your friend is a computer, this becomes quite complicated. First, you have to specify the location of the beer, then instruct him to get up, rotate towards the door, take a number of steps, rotate towards the kitchen (again, you have to specify where and what kitchen is), take a number of steps again, open the fridge door, identify the beer, extend the arm, grab the beer, retract the arm, track back on the previous path, give you the beer, then sit down again.
In short, you have to tell the computer exactely what you want it to do, include every minor detail and pay attention to the minutia that can produce erroneous behavior.Ever seen a dog chase its tail? Now that's an infinite loop.
 06172010, 01:26 AM #15Member
 Join Date
 Jun 2010
 Posts
 12
 Rep Power
 0
Similar Threads

Recursion.
By Cruncher in forum Advanced JavaReplies: 30Last Post: 05102010, 01:06 PM 
Recursion assignment problems
By tfitz666 in forum New To JavaReplies: 11Last Post: 01242010, 10:18 PM 
Recursion
By mp0667 in forum New To JavaReplies: 1Last Post: 01202010, 08:49 AM 
recursion and tailrecursion differences
By OptimusPrime in forum New To JavaReplies: 2Last Post: 12282009, 07:26 PM 
recursion
By ravian in forum New To JavaReplies: 2Last Post: 12032007, 06:15 PM
Bookmarks