Hello all,
This is the ole reverse a string classroom assignment.
Recursion is soemthing I never quite understood till now but as I
perceive it, for a method to be considered recursive, it MUST have a
base case and a recursive step.
Fine, with this in mind, I wrote a simple program that reverses a word
that doesn't have a base step but it calls itself. Would this be
considered by the formal defintion of recursion?
To me, I see the base step as implied by doing nothing while you
decrease the parameter by one when you call the method again and THEN
you stop calling it recusively when you get to the last element of the
string. For example, consider the code:
public class StringReversal {
public static void main(String[] args) {
String aWord = "hello";
System.out.print ("\nReversing " + aWord + " to ");
reversal(aWord,aWord.length()-1);
} // end main
/**reverses a string of characters
* @param string is the string passed */
public static void reversal(String aWord,int position){
System.out.print(aWord.substring(position,position+1));
if (position != 0) {
reversal(aWord,position-1);
}
} // end Reversal method
}
I have a feeling the professor is probably not going to like this
because it doesn't fit the 'model' recursion defintion...no base case
and recursive step defined. I'm just wondering what other ppl
think. It's clear to me and it works! :p
Any thoughts appreciated.
Gordon Beaton - 30 Jan 2007 12:01 GMT
> I wrote a simple program that reverses a word that doesn't have a
> base step but it calls itself. Would this be considered by the
> formal defintion of recursion?
You claim that it works correctly, so I claim there is in fact a base
case (without which it would continue recursing forever).
In your code, you only recurse conditionally (when position != 0).
What happens otherwise? That's your base case.
/gordon

Signature
[ don't email me support questions or followups ]
g o r d o n + n e w s @ b a l d e r 1 3 . s e
Patricia Shanahan - 30 Jan 2007 13:52 GMT
> Hello all,
>
[quoted text clipped - 41 lines]
>
> Any thoughts appreciated.
The recursive step is the "reversal(aWord,position-1)" call.
The base case is position equal to 0, which is handled differently from
non-zero. Specifically, the recursive step is not done in the base case.
They have the correct relation to each other, if position is initially
non-negative. The recursive step then uses a function of position,
position-1, that ensures that it must reach the base case, position==0.
Incidentally, you should look at your handling for empty strings.
Perhaps you are confused by having some code that is common to the base
case and the recursive case? That happens quite often. For example, a
depth-first tree scans do recursive calls for non-leaf nodes, followed
by processing for the current node that is done regardless of whether it
is a leaf.
Patricia
Marion - 30 Jan 2007 16:17 GMT
> The recursive step is the "reversal(aWord,position-1)" call.
>
[quoted text clipped - 8 lines]
>
> Patricia
Thanks Patricia and Gordon,
I thought my base case was there but U wasn't confident about my
reasoning until you two explained it a bit to me.
Patricia, I learned from Gordon in another program that strings were
compared using ".equal" and not "==". I'm afraid I will never forget
this even after I am 101 years old . . . with senility. It's been
burned into my brain, permanently. :p)
In the simplified example code I provided, the empty string does not
exist since the program initialized before calling the recursive
method. I understand that calling a recursive method when a negative
number condition exists is not a happy event. In my current code that
is not shown here, I do check for the empty string condition before
proceeding.
Thanks very much for your analysis, Patricia and Gordon, btw. Much
appreciated!
Patricia Shanahan - 31 Jan 2007 00:48 GMT
>> The recursive step is the "reversal(aWord,position-1)" call.
>>
[quoted text clipped - 18 lines]
> this even after I am 101 years old . . . with senility. It's been
> burned into my brain, permanently. :p)
True, but I don't see the relevance, because there were no string
compares in your code.
> In the simplified example code I provided, the empty string does not
> exist since the program initialized before calling the recursive
> method. I understand that calling a recursive method when a negative
> number condition exists is not a happy event. In my current code that
> is not shown here, I do check for the empty string condition before
> proceeding.
Calling a recursive method with negative input does not have to be a
problem. The key condition is that the recursion process should always
reach a base case in a finite number of steps, when starting from any
permitted input.
Patricia
Chris Smith - 31 Jan 2007 17:36 GMT
In addition to the other two responses, which are fine. If you need to
format your recursive function call according to the form it's normally
expressed in, then you can do so by making a small modification to your
code. (Incidentally, this also makes empty strings work.)
Just think of your existing example as "inlining" the base case. Then
undo the inlining. You'll end up with:
public static void reversal(String aWord,int position)
{
if (position < 0)
{
return; // base case
}
else
{
// inductive case
System.out.print(aWord.charAt(position));
reversal(aWord,position-1);
}
}
I made this modification mechanically, just by noting that instead of
only calling reversal on (position != 0), one could always call it
anyway, and then just have it do nothing if (position < 0). You get the
empty string for free.
By comparison, here was your original code (modifications for formatting
and to make the non-structural stuff clearer:
public static void reversal(String aWord,int position)
{
System.out.print(aWord.charAt(position);
if (position != 0)
{
reversal(aWord,position-1);
}
}
> I have a feeling the professor is probably not going to like this
> because it doesn't fit the 'model' recursion defintion...
Note that I point this out only because it might help you understand
what's going on in terms of this model definition. It may also help you
out if your professor is him/herself shaky on the subject and is likely
to grade formulaically. As much as I'd like to think that's impossible,
experience teaches otherwise.
Your previous answer (except for the empty string case, as Patricia
pointed out) is just fine as a recursive definition.

Signature
Chris Smith