C/++/# C# method question

18,840
3,652
I've been studying C# programming, and I came across the following method for calculating factorials that I find confusing. It looks like, in the body associated with "else," the method calls on itself. As a guy with a lot of Fortran coding experience, I've never seen anything like this. I ran the program that contains this method, and it executed fine.

Code:
         long factorial (int dataValue)
            {
                if (dataValue == 1)
                {
                    return 1;
                }
                else
                {
                    return dataValue * factorial(dataValue - 1);
                }
               
            }
But I find all this very strange. Do C# methods really allow for internal calls to themselves and, if so, what is the logical sequence of operations and values that ensues?
 
Last edited by a moderator:

anorlunda

Mentor
Insights Author
Gold Member
6,296
3,501
Yes, that is a "recursive" call. Computer scientists love recursive algorithms because they are so elegant. FORTRAN did not support recursive calls.
 
10,334
3,866
This recursive programming at its finest.

You write the method to handle the n=0 case and then for all others you defer to calling it again for the n-1 case.

Its cool but more costlier than a for loop. However there are some problems where the recursive case wins the day for understandability.

(editted per @pasmith comment -- lowest case is 0! not 1!)
 
Last edited:
32,346
4,131
I've been studying C# programming, and I came across the following method for calculating factorials that I find confusing. It looks like, in the body associated with "else," the method calls on itself. As a guy with a lot of Fortran coding experience, I've never seen anything like this. I ran the program that contains this method, and it executed fine.

Code:
         long factorial (int dataValue)
            {
                if (dataValue == 1)
                {
                    return 1;
                }
                else
                {
                    return dataValue * factorial(dataValue - 1);
                }
             
            }
But I find all this very strange. Do C# methods really allow for internal calls to themselves and, if so, what is the logical sequence of operations and values that ensues?
This is an example of a recursive function, something that's available in C, C++, C#, Java, and even Fortran from F90 on. See if you can follow the logic for an easy example, say dataValue == 3.

Keep in mind that either return statement returns to the point in the code that called the factorial function, which is not necessarily some other code outside of the factorial function itself.
 

pasmith

Homework Helper
1,667
369
This recursive programming at its finest.

You write the method to handle the n=1 case and then for all orhers you defer to calling it again for the n-1 case.
For the factorial function one must define expressly 0! = 1. This implementation does not return 1 for this case, but instead overflows.
 
10,334
3,866
The key point is to handle the terminating case otherwise you will recurse forever and a day.

Old fortran couldn't do recursion because function arguments were often retrieved by registers and not via a stack scheme. Recursion works because we now use stacks internally. I once did recursion in Radioshack Basic where the subs could be called recursively but you had to use arrays and a "stack pointer" index to reference the right data based on the recursion level.

In the factorial case above, its cool to place a print statement at the start to show recursing into and one where you return to show it exitting and you will see something like this:
C:
unsigned int fact(unsigned int n) {
    printf("\nentering fact() n=%d",n);

   if (n == 0) {
       return 1;
   } else {
        int nf = n*fact(n-1);
        printf("\nreturning fact() --> %d",nf);
       return nf;
   }
}
Code:
entering fact()  n=3
entering fact()  n=2
entering fact()  n=1
entering fact()  n=0

returning fact()  --> 1
returning fact()  --> 1
returning fact()  --> 2
returning fact()  --> 6
 

Ibix

Science Advisor
Insights Author
4,686
3,031
Thanks so much guys. WOW. Can't wait to learn more about this.
Just one warning - before understanding recursive functions you need to understand recursive functions. o0)

(That joke never gets old - it just overflows the stack)
 
523
215
(I think this is somewhere in a math humor thread at the eigenlounge)

Q: What does the 'M' stand for in 'Benoit M. Mandelbrot'?
A: Benoit M. Mandelbrot

I've been studying C# programming, and I came across the following method for calculating factorials that I find confusing. It looks like, in the body associated with "else," the method calls on itself. As a guy with a lot of Fortran coding experience, I've never seen anything like this. I ran the program that contains this method, and it executed fine.

Code:
         long factorial (int dataValue)
            {
                if (dataValue == 1)
                {
                    return 1;
                }
                else
                {
                    return dataValue * factorial(dataValue - 1);
                }
              
            }
But I find all this very strange. Do C# methods really allow for internal calls to themselves and, if so, what is the logical sequence of operations and values that ensues?
Factorial calculation is often used for an instructive illustration of recursion. As @jedishrfu noted, when calculating a simple factorial, recursion is costlier than a for loop. You can check that by running the different methods presented at https://rosettacode.org/wiki/Factorial#C.23
 

Vanadium 50

Staff Emeritus
Science Advisor
Education Advisor
22,591
4,869
I would make a few small tweaks:

C:
         ulong factorial (uint dataValue)
            {
                if (dataValue == 0)
                {
                    return 1;
                }
                else
                {
                    return dataValue * factorial(dataValue - 1);
                }
           
            }
(Hmmm...anyone know to to highlight insider code tags?
 
Last edited:
523
215
Vanadium 50 said:
(Hmmm...anyone know to to highlight insider code tags?
C:
/* ##\TeX \mathtt{\ can\ show\ \textbf{bold},\ \underline{underline}, \ and\ \textit{italic}\ inside\ code\ tags.} ## */
 
Last edited:
10,334
3,866
I would make a few small tweaks:

C:
         uong factorial (uint dataValue)
            {
                if (dataValue == 0)
                {
                    return 1;
                }
                else
                {
                    return dataValue * factorial(dataValue - 1);
                }
           
            }
(Hmmm...anyone know to to highlight insider code tags?
You could make three code blocks with the middle block your code and the outer blocks their code.

Can code tags be nested? I haven’t tried it but maybe you could use spoiler tags inside the code tags as it seems that code tags can be inside quotes as above.
 
523
215
jedishrfu said:
Can code tags be nested? I haven’t tried it but maybe you could use spoiler tags inside the code tags as it seems that code tags can be inside quotes as above.
The current PF implementation of bbcode treats bbcode tags as literals if they are inside code tags, and attempting to nest code tags gets the inner opening code tag treated as a literal, and the inner closing code tag closes the code tag block, with the outer closing code tag orphaned outside the block and treated as a literal, like other unmatched closing tags.

Like this:
Code:
[b]bold[/b] [spoiler]hidden text[/spoiler][code=c]    printf("text");
[/code]
 
523
215
Oops. This worked before the upgrade.

C:
/* ##\TeX \mathtt{\ can\ show\ \textbf{bold},\ \underline{underline}, \ and\ \textit{italic}\ inside\ code\ tags.} ## */
The exact same ##\TeX## still works outside code tags:

/* ##\TeX \mathtt{\ can\ show\ \textbf{bold},\ \underline{underline}, \ and\ \textit{italic}\ inside\ code\ tags.} ## */
 
523
215
You can't use bbcode inside code tags, so being able to use TeX for highlighting when you want to comment on code, via bolding, underlining, strikethrough, is a worthy alternative.
 
You can't use bbcode inside code tags, so being able to use TeX for highlighting when you want to comment on code, via bolding, underlining, strikethrough, is a worthy alternative.
You are able to highlight lines in the code tags now.
 
523
215
My immediately preceding post in that thread would appear to indicate otherwise. Inside code tags, the bbcode tags get treated as literals.
 
523
215
Is there a new prescribed method for highlighting inside code tags?
 

Vanadium 50

Staff Emeritus
Science Advisor
Education Advisor
22,591
4,869
Ah...one can highlight entire lines. But what I wanted to highlight were:

unsigned int and longs (i.e. the u's) and the factorial having a value of 0.

The zero is there so that 0! correctly returns 1 rather than getting into an infinite loop. The "unsigned' is there more as a reminder than anything else. factorial(negative integer) will still cause problems, and these problems will be implementation-dependent, so this serves as a reminder not to do that.
 
523
215
This is a test.
Code:
This is a [B]test[/B] (highlighted, word "test" bolded)
this is another test (unhighlighted)
The highlight= option in the opening code tag, allowing line number specification, is not as flexible as allowing ##\TeX##, as the pre-upgrade system did. That was a viable substitute for bbcode, compared to only the ability to highlight lines. When someting is bolded inside code tags, it shows up in the rich text editor as bold, but when it's translated into bbcode bold tags, the tags are treated as literals. If there were an escape sequence that could tell the system to process particular bbcode tags within code tags, that would suffice, but without something like that, it seems to me that the ##\TeX## double hashtag parsing should still occur within code tags, as it did previously.
 
Last edited:

rcgldr

Homework Helper
8,547
461
None of the responses explain how this is done. A stack is used to save the "state" of the computer, registers and the return address. Parameters may be passed in registers or also on the stack. A typical stack is an array of memory with a pointer to the "end" of the stack, where each time a value is "pushed" onto the stack the pointer is decremented ("pre-decrement"), and the value stored using the pointer and where each time a value is "popped" from the stack, the value is loaded using the pointer, and then the pointer is incremented ("post-increment"). The return value is typically returned in a register, or in some cases, space is "allocated" (a constant subtracted from the stack pointer) on the stack before pushing parameters to call a function if needed.

A typical call to a function with 3 parameters on the stack would look like: "push parameter 3", "push parameter 2", "push parameter 1", "call function" (this pushes the return address). Inside the function, the value stored at "stack_pointer" = return address, the value at "stack_pointer + 1" = parameter 1, and so on. If the function calls itself, another set of pushes are done. When the function returns, the return address is "popped" from the stack. The calling code would then need to add 3 to the stack pointer for the 3 pushed parameters. In some cases, the called function can use a return instruction that combines popping the return address and adding what is needed (in this example 3) to the stack_pointer.

For the factorial example, there is only one parameter, so if using the stack for parameter, its "push n", "call factorial", then inside factorial, if it is going to call itself, it pushes "n" onto the stack to save it, then pushes "n-1" to be used as a parameter, then calls itself. When it the nested call returns, "stack_pointer" is incremented by 1 to remove the "n-1" that was pushed onto the stack. Then "n" is popped from the stack and multiplied by the value returned from the nested call, the product of n * (returned value from nested call) is returned to whatever code called the factorial function.
 
Last edited:

Want to reply to this thread?

"C# method question" You must log in or register to reply here.

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving
Top