# Recursion Problems. Pls Help!

• 06-14-2010, 09:00 AM
ferdzz
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.
• 06-14-2010, 09:38 AM
m00nchile
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.
• 06-14-2010, 09:44 AM
ferdzz
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:
• 06-14-2010, 09:44 AM
r035198x
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
Code:

```if(a[start] != a[start +1])     return false;```
• 06-14-2010, 02:13 PM
m00nchile
The exit condition
Code:

```if(start == end)   return true;```
can only be used to determine if the run was sucessfull, because every call to the method except the last one will have different values for start and end.
Also, your method would loop infinitely because of this:
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; }```
This is equal to:
Code:

```int recursive(int n) {   return recursive(n); //no modification of n variable before recursive call }```
To make it more understandable:
Code:

```int n = 10, sum = 0; while(n != 0) {   sum += n; }```
in the example with the while loop, you don't modify the n variable and produce an infinite loop.
I'll give you the solution, but in pseudocode, you translate it into valid 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```
Try to write down the pseudocode for your other problem as well, it usually makes a problem much clearer.
• 06-14-2010, 03:02 PM
JosAH
Maybe my schizophrenic example applies here as well: suppose there's me, the big mouthed mr Know-It-All 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:

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); }```
Here's where the schizophrenic part hits: I don't have a friend, my friend is me and I am my friend and I am schizophrenic; that method should actually read:

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); }```
A more sensible person might name this method 'allEqual' or similar ...

kind regards,

Jos
• 06-14-2010, 04:27 PM
ferdzz
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!
• 06-14-2010, 04:43 PM
JosAH
Quote:

Originally Posted by ferdzz
And the schizophrenic analogy is simply genius .

Well, I won't call it 'genius' but it does make the quarter drop for a lot of people struggling with the concept of recursion.

kind regards,

Jos
• 06-14-2010, 05:58 PM
ferdzz
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

?
• 06-14-2010, 06:05 PM
m00nchile
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.
• 06-14-2010, 06:16 PM
ferdzz
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!
• 06-14-2010, 06:35 PM
m00nchile
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.
• 06-14-2010, 07:01 PM
JosAH
Quote:

Originally Posted by ferdzz
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!

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
• 06-15-2010, 08:21 AM
m00nchile
The way I explain how thick computers are to my friends who aren't tech-savvy 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.
• 06-17-2010, 01:26 AM
ferdzz
in that case... i'll just get the beer myself haha