Solved

# Recursion... hard for me to grasp the concept fully... help! =)

Posted on 2004-09-20
882 Views
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
Question by:PoeticAudio
[X]
###### Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

• Help others & share knowledge
• Earn cash & points
• 3
• 2
• 2
• +2

LVL 48

Assisted Solution

AlexFM earned 50 total points
ID: 12102457
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

LVL 48

Expert Comment

ID: 12102505
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

LVL 19

Accepted Solution

drichards earned 100 total points
ID: 12102516
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

LVL 6

Author Comment

ID: 12102693
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

LVL 6

Author Comment

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

LVL 22

Assisted Solution

cookre earned 20 total points
ID: 12104022
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

LVL 15

Assisted Solution

praneetha earned 30 total points
ID: 12106218
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

LVL 22

Expert Comment

ID: 12106799
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

LVL 22

Expert Comment

ID: 12107214
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

## Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

This article describes a simple method to resize a control at runtime.  It includes ready-to-use source code and a complete sample demonstration application.  We'll also talk about C# Extension Methods. Introduction In one of my applications…
This article aims to explain the working of CircularLogArchiver. This tool was designed to solve the buildup of log file in cases where systems do not support circular logging or where circular logging is not enabled
Six Sigma Control Plans
Attackers love to prey on accounts that have privileges. Reducing privileged accounts and protecting privileged accounts therefore is paramount. Users, groups, and service accounts need to be protected to help protect the entire Active Directory …
###### Suggested Courses
Course of the Month7 days, 3 hours left to enroll