Can someone please explain recursion.

[JPHamlett]

Ok, so I've been staring at this code for a while and I just can not understand how it does it.



public static boolean isPalindrome(String s)
{
if (s.length() <= 1)
return true; // Base case
else
{
if (s.charAt(0) == s.charAt(s.length() - 1))
return isPalindrome(s.substring(1, s.length() - 1 ) );
else
return false;
}
}


Now I understand what it does, I just don't understand how it does it. If someone would be kind enough to explain this code to me I'd be very appreciative.


~JP

[Method]

In general, a recursive definition is one where the thing being defined refers to itself in the definition. For example, the Fibonacci sequence (http://mathworld.wolfram.com/FibonacciNumber.html) is defined in terms of the two previous terms. SRL is a recursive acronym, and there are many other instances of recursion out there.

In programming, a recursive function or method is one that calls itself. Each time a method or function is called, it has its own set of local variables and parameters that are unique to that call. In general, a recursive function will have at least two parts: a base case and a recursive case. The base case is generally the most simple input the function could receive, and the recursive case tries to work down to the base case while doing some operation(s) with the data as it goes. It's important to always remember to have a base case along with a recursive case, because infinite recursion isn't fun and will probably crash your program.

Anyway, let's get to the function you've posted. We'll try it with the simple palindrome "racecar". Let's see what the function does with it:

isPalindrome("racecar") => The length is seven, so the base case doesn't apply here. The first and the last characters are indeed the same, so we'll call isPalindrome("aceca") and return the result of that call.
isPalindrome("aceca") => Again, the length is not one, so the base case is skipped. The first and last characters are the same again, so we'll call isPalindrome("cec") and return the result of that call.
isPalindrome("cec") => Same as the last two cases. We'll call isPalindrome("e") and return that result.
isPalindrome("e") => Looks like we have reached the base case! Return true, since a single character is a palindrome.

Since isPalindrome("e") returned true, so will isPalindrome("cec"), and so on. The true value will work its way back up the recursion tree until isPalindrome("racecar") returns true.

Hopefully this helps.

[anonymity]

I will start off with a very basic example (copied from wikipedia).
unsigned int factorial(unsigned int n)
{
if (n <= 1)
return 1;
else
return n * factorial(n-1);
}
^ On call of the function factorial, an integer of some sort is passed in. You [always] start off with the base case. In this function the bare minimum (base, or what should happen at the end) is if the integer is one. If it is not, it continues on to the recursive part of the function. Now, recursion, in terms of coding, is a function that calls itself. So, if it is not the base case it call ( n * factorial(n-1) ), which is one less than what the number currently is. This would look like:



4 * (4-1) * (4-1-1) * (4-1-1-1 = 1)

Starting with 4 ( not 1 ) it returns factorial(n-1) or factorial(3)
Next with 3 ( not one ) it returns factorial(n-1) or factorial(2)
Next with 2 ( not one ) it returns factorial(n-1) or factorial(1)
Next with 1 (which is one) it returns 1

Now, the Above cascade up to look like : 1 * 2 * 3 * 4

E: I was beaten to the punch line... but I will keep my example..

[Zyt3x]

He said he understood what it did, but not how it did it.

Like in Simba, when you do function M: String; begin Result := M; end; what is it that Simba does?

E: Nvm, misunderstood the question.