Solved

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

Posted on 2004-09-20
9
880 Views
Last Modified: 2008-02-26
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
Comment
Question by:PoeticAudio
  • 3
  • 2
  • 2
  • +2
9 Comments
 
LVL 48

Assisted Solution

by:AlexFM
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

by:AlexFM
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

by:
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
Networking for the Cloud Era

Join Microsoft and Riverbed for a discussion and demonstration of enhancements to SteelConnect:
-One-click orchestration and cloud connectivity in Azure environments
-Tight integration of SD-WAN and WAN optimization capabilities
-Scalability and resiliency equal to a data center

 
LVL 6

Author Comment

by:PoeticAudio
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

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

Assisted Solution

by:cookre
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

by:praneetha
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

by:cookre
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

by:cookre
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

Active Directory Webinar

We all know we need to protect and secure our privileges, but where to start? Join Experts Exchange and ManageEngine on Tuesday, April 11, 2017 10:00 AM PDT to learn how to track and secure privileged users in Active Directory.

Question has a verified solution.

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

Introduction Although it is an old technology, serial ports are still being used by many hardware manufacturers. If you develop applications in C#, Microsoft .NET framework has SerialPort class to communicate with the serial ports.  I needed to…
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 video shows how to quickly and easily add an email signature for all users on Exchange 2016. The resulting signature is applied on a server level by Exchange Online. The email signature template has been downloaded from: www.mail-signatures…
Established in 1997, Technology Architects has become one of the most reputable technology solutions companies in the country. TA have been providing businesses with cost effective state-of-the-art solutions and unparalleled service that is designed…

821 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question