Solved

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

Posted on 2004-09-20
9
873 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
 
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
Find Ransomware Secrets With All-Source Analysis

Ransomware has become a major concern for organizations; its prevalence has grown due to past successes achieved by threat actors. While each ransomware variant is different, we’ve seen some common tactics and trends used among the authors of the malware.

 
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

Better Security Awareness With Threat Intelligence

See how one of the leading financial services organizations uses Recorded Future as part of a holistic threat intelligence program to promote security awareness and proactively and efficiently identify threats.

Join & Write a Comment

Introduction This article series is supposed to shed some light on the use of IDisposable and objects that inherit from it. In essence, a more apt title for this article would be: using (IDisposable) {}. I’m just not sure how many people would ge…
This article is for Object-Oriented Programming (OOP) beginners. An Interface contains declarations of events, indexers, methods and/or properties. Any class which implements the Interface should provide the concrete implementation for each Inter…
This demo shows you how to set up the containerized NetScaler CPX with NetScaler Management and Analytics System in a non-routable Mesos/Marathon environment for use with Micro-Services applications.
When you create an app prototype with Adobe XD, you can insert system screens -- sharing or Control Center, for example -- with just a few clicks. This video shows you how. You can take the full course on Experts Exchange at http://bit.ly/XDcourse.

708 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

Need Help in Real-Time?

Connect with top rated Experts

16 Experts available now in Live!

Get 1:1 Help Now