PoeticAudio
asked on
Recursion... hard for me to grasp the concept fully... help! =)
Hey guys,
I understand that a recursive function is a function that calls itself... but for some reason i'm just not getting the full grasp of it... like a mental block of sorts. I have the book C# How to Program (From Dietel) and here is the first example of recursion that they give:
(I put in line numbers for a reason, see below)
public long Factorial (long number)
1:{
2: if (number <= 1 ) //base case
3: return 1;
4: else
5: return number * Factorial (number - 1)
6:}
private void showFactorialsButton_Click
{
outputLabel.Text = "";
for (long i = 0; i <= 10; i++)
outputLabel.Text += i + "! = " +
Factorial(i) + "\n";
}
I understand how this works, sorta, but there also I'm still confused. When I set a breakpoint at the top of the Factorial function and ran the program I stepped through the function one line at a time to see how everything was working... this is where I got thrown off. If you set a break point and say variable i (in the for loop) is on its 5th iteration (or really any iteration greater then 1) here is what it does (we willl just say 5 for this example):
line 2 to line 5
line 2 to line 5
line 2 to line 5
line 2 to line 5
line 2 to line 5
okay I can understand this... this is when the function is calling itself... but then it goes:
line 6 to line 5
line 6 to line 5
line 6 to line 5
line 6 to line 5
line 6 to line 5
this is where I get confused... why does it suddenly jump to the end of the method block and then back up to line 5 five times?
If I did a bad job of explaining this then just write this little program, set a breakpoint at the beginning of the Factorial function and step through it.
Any help or good explanation on how recursive functions work will be greatly appreciated! and if it's an exceptional explanation and I suddenly understand how everything works because of your explanation I will be more then happy to raise the points considerably!
I understand that a recursive function is a function that calls itself... but for some reason i'm just not getting the full grasp of it... like a mental block of sorts. I have the book C# How to Program (From Dietel) and here is the first example of recursion that they give:
(I put in line numbers for a reason, see below)
public long Factorial (long number)
1:{
2: if (number <= 1 ) //base case
3: return 1;
4: else
5: return number * Factorial (number - 1)
6:}
private void showFactorialsButton_Click
{
outputLabel.Text = "";
for (long i = 0; i <= 10; i++)
outputLabel.Text += i + "! = " +
Factorial(i) + "\n";
}
I understand how this works, sorta, but there also I'm still confused. When I set a breakpoint at the top of the Factorial function and ran the program I stepped through the function one line at a time to see how everything was working... this is where I got thrown off. If you set a break point and say variable i (in the for loop) is on its 5th iteration (or really any iteration greater then 1) here is what it does (we willl just say 5 for this example):
line 2 to line 5
line 2 to line 5
line 2 to line 5
line 2 to line 5
line 2 to line 5
okay I can understand this... this is when the function is calling itself... but then it goes:
line 6 to line 5
line 6 to line 5
line 6 to line 5
line 6 to line 5
line 6 to line 5
this is where I get confused... why does it suddenly jump to the end of the method block and then back up to line 5 five times?
If I did a bad job of explaining this then just write this little program, set a breakpoint at the beginning of the Factorial function and step through it.
Any help or good explanation on how recursive functions work will be greatly appreciated! and if it's an exceptional explanation and I suddenly understand how everything works because of your explanation I will be more then happy to raise the points considerably!
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
Okay, i'm getting good explanations here and I will raise the points another 100 for help on this exercise (This is exercise 7.7 in Deitels C# How to Program, in no way is this connected to any sort of school work, i'm just trying to learn on my own...and I tend to learn better by examples)
Okay here exercise 7.7 (they don't give answers on exercises)
"(Palindromes) A palindrome is a string that is speed the same forward and backwards. Some examples of palindromes are "radar," "able was i ere i saw elba" and, if blanks are ignored, "a man a plan a canal panama" Write a recursive method TestPalindrome that returns true if the string stored in the ARRAY is a palindrome and false otherwise. The method should ignore spaces and punctuation in the string."
Okay here exercise 7.7 (they don't give answers on exercises)
"(Palindromes) A palindrome is a string that is speed the same forward and backwards. Some examples of palindromes are "radar," "able was i ere i saw elba" and, if blanks are ignored, "a man a plan a canal panama" Write a recursive method TestPalindrome that returns true if the string stored in the ARRAY is a palindrome and false otherwise. The method should ignore spaces and punctuation in the string."
ASKER
sorry, it should say "A palindrome is a string that is spelled" not "speed" my fault.
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Exactly.
The key to getting recursion to work is knowing when to stop. The first example uses an arbitrary point of diminishing return. I explicitly gave two conditions for the palindrome stop test to highlight the need to consider all possibilities. In practice, you'd use just the single test for length<2
Note that most algorithms implemented recursively can also be implemented iteratively. Indeed, there are many who deprecate recursion for its poorer performance when compared to an iterative equivalent. Personally, if performance is not an issue, I tend to prefer recursion primarily forits clarity of purpose and ease of implementation and maintenance.
The key to getting recursion to work is knowing when to stop. The first example uses an arbitrary point of diminishing return. I explicitly gave two conditions for the palindrome stop test to highlight the need to consider all possibilities. In practice, you'd use just the single test for length<2
Note that most algorithms implemented recursively can also be implemented iteratively. Indeed, there are many who deprecate recursion for its poorer performance when compared to an iterative equivalent. Personally, if performance is not an issue, I tend to prefer recursion primarily forits clarity of purpose and ease of implementation and maintenance.
Just for fun, I decided to give it a go.
tbTextIn - text box for string to check
cbCheckIt - command button to run check
....
private void cbCheckIt_Click(object sender,System.EventArgs e)
{
if (tbTextIn.Text.Length<1)
{
MessageBox.Show("Aw c'mon - gimme text");
return;
}
if (IsPalindrome(tbTextIn.Tex
else MessageBox.Show("Nope");
tbTextIn.Text="";
tbTextIn.Refresh();
tbTextIn.Focus();
}
bool IsPalindrome(string Thing)
{
int ThingLen=Thing.Length;
if (Thing.Length<2) return true;
if (Thing[0]!=Thing[ThingLen-
return IsPalindrome(Thing.Substri
}
tbTextIn - text box for string to check
cbCheckIt - command button to run check
....
private void cbCheckIt_Click(object sender,System.EventArgs e)
{
if (tbTextIn.Text.Length<1)
{
MessageBox.Show("Aw c'mon - gimme text");
return;
}
if (IsPalindrome(tbTextIn.Tex
else MessageBox.Show("Nope");
tbTextIn.Text="";
tbTextIn.Refresh();
tbTextIn.Focus();
}
bool IsPalindrome(string Thing)
{
int ThingLen=Thing.Length;
if (Thing.Length<2) return true;
if (Thing[0]!=Thing[ThingLen-
return IsPalindrome(Thing.Substri
}
To write recursive function you need to write recursive definition. Recursive definition of factorial is:
n! is:
1, if n <= 1;
n * (n-1)!, if n > 1.
This definition is easily translated to C#:
public long Factorial (long number)
{
if (number <= 1 )
return 1;
else
return number * Factorial (number - 1)
}
There are tasks which may be solved both by recursion or loop - like factorial. Some tasks may be solved only by recursion - for example, operations with tree structures.