• Post Reply Bookmark Topic Watch Topic
  • New Topic

Struggling with a Recursion Question  RSS feed

 
Greenhorn
Posts: 10
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
hello everyone~

so i have this question where it wants me to create a recursion method that takes ONLY THE ARRAY as a parameter, and without using loops or static variables inside the method, and then the method returns the smallest value in that array.
However, i tried making the simple if statements where i compare the first element of the array with the second element using the length of the array and decreasing it to get the next elements and compare it again by calling the recursion method, but the problem is when i call the method again, the length does not
decrease, even if i store it in a variable, the variable will initialize itself again, and the length wont change, so yea..
any ideas or if there is any possible solutions for this question ?
 
Sheriff
Posts: 4289
127
Chrome Eclipse IDE Java Postgres Database VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Can you use Arrays.copyOf() to shorten the array?
 
Marshal
Posts: 56600
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
How are you decreasing the size of the array?
 
Campbell Ritchie
Marshal
Posts: 56600
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Knute Snortum wrote:Can you use Arrays.copyOf() to shorten the array?
Yes he can, but doesn't that always shorten the array at its end? That would require a different approach where you look at the last element.
 
Wisam Siya
Greenhorn
Posts: 10
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
No i cant use Array.copyOf() either, and sorry for my bad English, i didn't mean to decrease the size of the array and it is impossible anyways, i meat to store it in a variable for example int length= array.length -1;
 
Campbell Ritchie
Marshal
Posts: 56600
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
And you can't pass the length of the array as a parameter?
No loops, no passing of index or length, no methods to copy the array? No storing of those as fields? Please check your instructions carefully because I am wondering whether that is possible at all.
 
Wisam Siya
Greenhorn
Posts: 10
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
yea i can't pass the length as a parameter too, and only the things that i mentioned you can't use. My teacher told me there is a way to solve it, and one of my classmates did it, but he won't show us.
 
Sheriff
Posts: 4931
334
BSD
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hang on, Wisam, I do agree, that method could take an argument only an array, but recursive call has to have a chance to take some extra parameters, otherwise i'm afraid would be an infinite.
At least I don't have other ideas in my mind.

Would you like to post your current solutions, might someone would come up with instant solution then.
 
Knute Snortum
Sheriff
Posts: 4289
127
Chrome Eclipse IDE Java Postgres Database VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Campbell Ritchie wrote:
Knute Snortum wrote:Can you use Arrays.copyOf() to shorten the array?
Yes he can, but doesn't that always shorten the array at its end? That would require a different approach where you look at the last element.


Well, I was thinking of something like this:



But if you can't use java.util.Arrays, that's not going to work.
 
Campbell Ritchie
Marshal
Posts: 56600
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
That looks exactly like what I thought you meant; you can do the same with System#arraycopy, but that way you can start from either end. I presume that arrayCopy would be prohibited just like copyOf.
You can create a Stream with Arrays#stream and truncate the Stream with limit(myArray.length - 1), but that is hardly going to get round the prohibition on using copyOf, and also it isn't going to be recursive.
 
Ranch Hand
Posts: 211
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Not sure if its cheating or not but I think the trick is to pass the least value, along with an index, through indices of the array which were already checked. For example if the first two numbers in your array are 5 and 4 respectively, you would change the values of the array to 4 and 2 (the 2 being the new index you're going to check). Then if array[2] == 7, your new array beginning will be 4,3

The problem with that however is you still need to signify that you're in a recursive mode instead of an initial mode where the first two values are 4 and 2. So you need at least one more slot to pass something that acts like a boolean value to tell the computer what mode you're in. So you need to check at least 3 slots initially. This gets tricky because depending on what data structure you use and the what the range of possible values are, you can't differentiate your signal from possible initial values. If you're given numbers that are always positive, its easy and you can just stick a negative number in for your signal. But if what you're given can take up the entire range of possible values, it can get tricky (and maybe impossible) to create a signal that is never confused for an initial value. But there should be a way to at least make it almost impossible that an initial set of of values is equivalent to your signal. For example with integers you can have your signal take up 3 slots instead of 1, so after the initial method call, your array would look something like

3 (lowest value),5 (next index), 2140483041 (part of signal) ,-2047483601 (part of signal) ,2142483641 (part of signal), 12 (this number will be compared next), ...

The chances that you're given input equivalent to your signal will be extremely low.
 
Campbell Ritchie
Marshal
Posts: 56600
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Unless you are supposed to swap the last pair of elements so the last element shows the index of the smallest element (found to date). Then you can return the value found when the last number is 0. You can probably just as easily do the same starting the swaps from the first index.
You have a second base case, where a one‑element array is passed as an argument.
 
Campbell Ritchie
Marshal
Posts: 56600
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Tyson Lindner wrote: . . . The chances that you're given input equivalent to your signal will be extremely low.
Maybe, but your signal is in the form of three ints, so that will fall down occasionally.

I did not know about your post when I posted my previous post. I do not think my last suggestion will work either, for the same reason.
 
Liutauras Vilda
Sheriff
Posts: 4931
334
BSD
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Wisam,

Which year of course, and which University? It could answer to some of the questions how to approach this problem.
Because at the moment all suggestions given by the guys it looks too complicated to me. You must be not telling us something, or misunderstanding the quest.
 
Bartender
Posts: 1840
10
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
With a recursive solution, you have to split it into a trivial comparison, and a recursive call on a 'smaller' problem.

The obvious split in this case is to take the 'head' of the array (e.g. first item), and run the process on the 'tail' of the array (all remaining items)

If you had a method signature findMinimumInArray(String[] array; int startingAtIndex) it would be trivial.
You can compare array[startingAtIndex] and findMinimumInArray(array, startingAtIndex +1)


Given the constraint that you are only allowed to pass the array as a parameter, then that array would have to convey somehow which items to be ignored.
For some reason I was assuming this was an array of int (habit I suppose), but Knute's answer is using String, and the OP doesn't mention that constraint.
How about if we have an array of Objects? Why not use null as a placeholder for 'a value I have already looked at'?

Pseudocode would be something like:


Base case: If only one non-null value in the array, return it.
Otherwise
find the first non-null value in the array.
Store this value in a local variable, and then 'null' it out of the array.
Make your recursive call on the array.
Compare your stored value vs the result of the recursive call.
restore the value to the array (so at the end, it should be as you originally got it)

 
Campbell Ritchie
Marshal
Posts: 56600
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Stefan Evans wrote: . . .
find the first non-null value in the array.
. . .
How? It says you are not allowed to use loops.

I am still wondering whether this is possible at all according to the description we have been given.
 
Sheriff
Posts: 11494
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I think you have to shift to functional programming thinking: An array can be treated as having a "head" element and the rest of the array is the "tail" - then you just reduce recursively:



or something like that. OP must really clarify what operations on an array are allowed because if you can't break the array down into head and tail, I don't see how it's possible to do this. There might be a way to structure the checks so you can do tail recursion.
 
Ranch Hand
Posts: 789
C++ Linux Python
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Sort the array recursively and return the first element.
 
Knute Snortum
Sheriff
Posts: 4289
127
Chrome Eclipse IDE Java Postgres Database VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Guillermo Ishi wrote:Sort the array recursively and return the first element.


And you do this without loops or indices or copying the array how?
 
Guillermo Ishi
Ranch Hand
Posts: 789
C++ Linux Python
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Well, it is a sorting problem. If there's no sort that meets the criteria, then the problem is impossible.

One or the other is true

P.S. Stooge sort might be a candidate. Nyuk, Nyuk.
http://en.wikipedia.org/wiki/Stooge_sort

 
Liutauras Vilda
Sheriff
Posts: 4931
334
BSD
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Guillermo Ishi wrote:P.S. Stooge sort might be a candidate.

Problem not in the sorting itself, problem is in the way of achieving that by passing only the array as an argument.
Beside that, Stooge sort is not even the good candidate in sorting.
 
Guillermo Ishi
Ranch Hand
Posts: 789
C++ Linux Python
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Liutauras Vilda wrote:
Guillermo Ishi wrote:P.S. Stooge sort might be a candidate.

Problem not in the sorting itself, problem is in the way of achieving that by passing only the array as an argument.
Beside that, Stooge sort is not even the good candidate in sorting.


It's a terribly bad sort in fact, but it's recursive and uses no loops. Now if you can just modify it work you can be a hero instead of a complainer


 
Liutauras Vilda
Sheriff
Posts: 4931
334
BSD
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Guillermo Ishi wrote:It's a terribly bad sort in fact, but it's recursive.

Any other sort algorithm can be written in recursive way with no loops at all, so nothing is special here.

Do you know how to modify your Stoogesort to take an argument ONLY the array, with no indexes and array length in order to accomplish the task?
 
Guillermo Ishi
Ranch Hand
Posts: 789
C++ Linux Python
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Any other? ANY other?

I wish I could oblige but I have too many other wastes of time going on. Basically I say let him do his own homework.

 
Don't get me started about those stupid light bulbs.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!