Recursion Question

I have the following simple recursion and as I unwind the call stack
(stepping through it), I am trying figure out where the eventual
return value is being stored. Any help is appreciated.
Thanks
Mike

namespace Factorial
{
    public partial class Form1 : Form
    {
        public Form1()
        {
            InitializeComponent();
        }

        private void button1_Click(object sender, EventArgs e)
        {
            label1.Text = Factorial(5).ToString();
        }

        public int Factorial(int n)
            {
                if(n==0) return 1;
                return n * Factorial(n-1);
            }
    }
}
0
AMP
1/9/2010 2:58:55 AM
dotnet.languages.csharp 1931 articles. 0 followers. Follow

4 Replies
1091 Views

Similar Articles

[PageSpeed] 13

On 08-01-2010 21:58, AMP wrote:
> I have the following simple recursion and as I unwind the call stack
> (stepping through it), I am trying figure out where the eventual
> return value is being stored. Any help is appreciated.

>          private void button1_Click(object sender, EventArgs e)
>          {
>              label1.Text = Factorial(5).ToString();
>          }
>
>          public int Factorial(int n)
>              {
>                  if(n==0) return 1;
>                  return n * Factorial(n-1);
>              }

The C# compiler and the CLR JIT compiler may do all kinds
of optimizations.

But before the optimization it will use the stack
to store the n's and a register for function result.

Arne

0
ISO
1/9/2010 3:16:34 AM
AMP wrote:
> I have the following simple recursion and as I unwind the call stack
> (stepping through it), I am trying figure out where the eventual
> return value is being stored. Any help is appreciated.
> Thanks
> Mike
> 
> namespace Factorial
> {
>     public partial class Form1 : Form
>     {
>         public Form1()
>         {
>             InitializeComponent();
>         }
> 
>         private void button1_Click(object sender, EventArgs e)
>         {
>             label1.Text = Factorial(5).ToString();
>         }
> 
>         public int Factorial(int n)
>             {
>                 if(n==0) return 1;
>                 return n * Factorial(n-1);
>             }
>     }
> }

At the time the call to the next inner nesting is made there is no result yet 
from the current invocation - said result depends on the value returned from the 
next nested recursive call, after all.  And as function results are typically 
returned in registers, there is not necessarily a need for a place on the stack 
(or heap) to store it.

In any case, any work space allocated by the runtime during the function 
execution, including storage for intermediate results, would not have a symbolic 
name that the debugger would know anything about.  Your best bet for tracing the 
entire execution flow so as to see the generation and disposition of the final 
result might be to disassemble your program to MSIL and trace through that.  It 
is a good exercise if, as I gather, you are just curious about how it 
(recursion) manages to work at all.


HTH,
-rick-
0
Rick
1/9/2010 12:04:56 PM
On Jan 9, 7:04=A0am, Rick Lones <Wrlon...@YcharterZ.net> wrote:
> AMP wrote:
> > I have the following simple recursion and as I unwind the call stack
> > (stepping through it), I am trying figure out where the eventual
> > return value is being stored. Any help is appreciated.
> > Thanks
> > Mike
>
> > namespace Factorial
> > {
> > =A0 =A0 public partial class Form1 : Form
> > =A0 =A0 {
> > =A0 =A0 =A0 =A0 public Form1()
> > =A0 =A0 =A0 =A0 {
> > =A0 =A0 =A0 =A0 =A0 =A0 InitializeComponent();
> > =A0 =A0 =A0 =A0 }
>
> > =A0 =A0 =A0 =A0 private void button1_Click(object sender, EventArgs e)
> > =A0 =A0 =A0 =A0 {
> > =A0 =A0 =A0 =A0 =A0 =A0 label1.Text =3D Factorial(5).ToString();
> > =A0 =A0 =A0 =A0 }
>
> > =A0 =A0 =A0 =A0 public int Factorial(int n)
> > =A0 =A0 =A0 =A0 =A0 =A0 {
> > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 if(n=3D=3D0) return 1;
> > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 return n * Factorial(n-1);
> > =A0 =A0 =A0 =A0 =A0 =A0 }
> > =A0 =A0 }
> > }
>
> At the time the call to the next inner nesting is made there is no result=
 yet
> from the current invocation - said result depends on the value returned f=
rom the
> next nested recursive call, after all. =A0And as function results are typ=
ically
> returned in registers, there is not necessarily a need for a place on the=
 stack
> (or heap) to store it.
>
> In any case, any work space allocated by the runtime during the function
> execution, including storage for intermediate results, would not have a s=
ymbolic
> name that the debugger would know anything about. =A0Your best bet for tr=
acing the
> entire execution flow so as to see the generation and disposition of the =
final
> result might be to disassemble your program to MSIL and trace through tha=
t. =A0It
> is a good exercise if, as I gather, you are just curious about how it
> (recursion) manages to work at all.
>
> HTH,
> -rick-- Hide quoted text -
>
> - Show quoted text -

Rick and Arne,
Great explanations.
Thanks
0
AMP
1/9/2010 2:05:02 PM
To continue your investigation of recursion, look into "tail recursion":
http://en.wikipedia.org/wiki/Tail_recursion


"AMP" <ampeloso@gmail.com> wrote in message 
news:4348e056-16b5-4e46-9f58-f492d7ac33ae@f6g2000vbp.googlegroups.com...
> On Jan 9, 7:04 am, Rick Lones <Wrlon...@YcharterZ.net> wrote:
>> AMP wrote:
>> > I have the following simple recursion and as I unwind the call stack
>> > (stepping through it), I am trying figure out where the eventual
>> > return value is being stored. Any help is appreciated.
>> > Thanks
>> > Mike
>>
>> > namespace Factorial
>> > {
>> >     public partial class Form1 : Form
>> >     {
>> >         public Form1()
>> >         {
>> >             InitializeComponent();
>> >         }
>>
>> >         private void button1_Click(object sender, EventArgs e)
>> >         {
>> >             label1.Text = Factorial(5).ToString();
>> >         }
>>
>> >         public int Factorial(int n)
>> >             {
>> >                 if(n==0) return 1;
>> >                 return n * Factorial(n-1);
>> >             }
>> >     }
>> > }
>>
>> At the time the call to the next inner nesting is made there is no result 
>> yet
>> from the current invocation - said result depends on the value returned 
>> from the
>> next nested recursive call, after all.  And as function results are 
>> typically
>> returned in registers, there is not necessarily a need for a place on the 
>> stack
>> (or heap) to store it.
>>
>> In any case, any work space allocated by the runtime during the function
>> execution, including storage for intermediate results, would not have a 
>> symbolic
>> name that the debugger would know anything about.  Your best bet for 
>> tracing the
>> entire execution flow so as to see the generation and disposition of the 
>> final
>> result might be to disassemble your program to MSIL and trace through 
>> that.  It
>> is a good exercise if, as I gather, you are just curious about how it
>> (recursion) manages to work at all.
>>
>> HTH,
>> -rick-- Hide quoted text -
>>
>> - Show quoted text -
>
> Rick and Arne,
> Great explanations.
> Thanks 

0
Fred
1/9/2010 6:44:12 PM
Reply:

Similar Artilces: