• Status: Solved
• Priority: Medium
• Security: Public
• Views: 905

# 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 (object sender...etc)
{
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!
0
PoeticAudio
• 3
• 2
• 2
• +2
4 Solutions

Commented:
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

These happens when function calls itself.

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 happens when function returns to it's previous instance.

Every function called from some place is allocated on stack. When function calls itself, new instance of the same function is allocated on stack. When this new instance returns, it is released from stack and program execution moves to the place where it was called. In this sample there are 6 instances of Factorial:

line 2 to line 5           1 calls 2  (instance N 1 if Factorial calls instance N 2)
line 2 to line 5           2 calls 3
line 2 to line 5           3 calls 4
line 2 to line 5           4 calls 5
line 2 to line 5           5 calls 6

After last instance is called, it returns 1 without calling additional instance. Calling stack is released:

line 6 to line 5          6 returned to 5
line 6 to line 5          5 returned to 4
line 6 to line 5          4 returned to 3
line 6 to line 5          3 returned to 2
line 6 to line 5          2 returned to 1

0

Commented:
This may help you to understand how recursive function works. It is important also to understand how recursive function may be written.
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.
0

Commented:
As the function calls back into itself repeatedly (at line 5), what you are seeing is a trail of "line 2 to line 5 to line 2 to line 5 ..." until the base condition evaluates to true in which case you hit line 3 at which point all the nested calls start returning (they all got rerouted at line 5 initially).  At that point you start to see the trail "line 6 to line 5 to line 6 to line 5 ... to line 6" as the nested call return.  The first line 6 is triggered by line 3.

Graphically, it looks like this for Factorial 3:

2
5   -->     2
6  <--      5   -->      2
|<--  6  <--       3
|<--  6

The return arrows coming back up the stack return at line 5 in the debugger because it returns where the Factorial call was made.
0

Author Commented:
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."

0

Author Commented:
sorry, it should say "A palindrome is a string that is spelled" not "speed" my fault.
0

Commented:
To simplify, first smoosh out all the blanks, then call the recursive procedure:

bool IsPalindrome(thing)
1) if thing is empty, return true
2) if thing is one letter, return true
3) if first and last letters are different, return false
4) call self with first and last letters removed.
0

Commented:
code for what cookre said ...
private bool IsPalindrome(string temp) // assuming temp is without spaces...
{
if(temp.Length==0)
return true;
if(temp.Length==1)
return true;
//this.label1.Text=temp[0].ToString()+temp[temp.Length-1].ToString();
if(temp[0].ToString()==temp[temp.Length-1].ToString())
{
string temp1="";
for(int i=1;i<=temp.Length-2;i++)
{
temp1+=temp[i];
}
this.IsPalindrome(temp1);
return true;
}
else
return false;
}

will return true if it is a palindrome...

note temp is assumed to be with out spaces...

0

Commented:
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.
0

Commented:
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.Text.Replace(" ","").ToUpper())) MessageBox.Show("Yup");
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-1]) return false;
return IsPalindrome(Thing.Substring(1,ThingLen-2));
}
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.