Re: Is this recursion?
- From: Patricia Shanahan <pats@xxxxxxx>
- Date: Tue, 30 Jan 2007 13:52:05 GMT
Marion wrote:
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.
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
.
- Follow-Ups:
- Re: Is this recursion?
- From: Marion
- Re: Is this recursion?
- References:
- Is this recursion?
- From: Marion
- Is this recursion?
- Prev by Date: Re: Is this recursion?
- Next by Date: Re: Is there an easy way to find the right class?
- Previous by thread: Re: Is this recursion?
- Next by thread: Re: Is this recursion?
- Index(es):
Relevant Pages
|
