# Thread: Recursion Problems. Pls Help!

1. Member
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.

2. Senior 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.

3. Member
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:

4. Senior Member
Join Date
Aug 2009
Posts
2,388
Rep Power
10
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;```

5. Senior Member
Join Date
Feb 2010
Location
Ljubljana, Slovenia
Posts
470
Rep Power
7
The exit condition
Java 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:
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;
}```
This is equal to:
Java Code:
```int recursive(int n) {
return recursive(n); //no modification of n variable before recursive call
}```
To make it more understandable:
Java 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:
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.

6. 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:

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);
}```
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:

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

kind regards,

Jos

7. Member
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!

8. 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

9. Member
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

?

10. Senior 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.

11. Member
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!

12. Senior 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.

13. 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

14. Senior 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 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.

15. Member
Join Date
Jun 2010
Posts
12
Rep Power
0
in that case... i'll just get the beer myself haha

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•