Understanding C# Method for Calculating Factorials

[Chestermiller]

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.

         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?

 

[anorlunda]

Yes, that is a "recursive" call. Computer scientists love recursive algorithms because they are so elegant. FORTRAN did not support recursive calls.

 

[jedishrfu]

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!)

 

[Mark44]

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.

         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]

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.

 

[Chestermiller]

Thanks so much guys. WOW. Can't wait to learn more about this.

 

[jedishrfu]

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:

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;
   }
}

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]

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.

(That joke never gets old - it just overflows the stack)

 

[phinds]

@Chestermiller you might be interested to Google the derivation of "GNU"

 

[sysprog]

(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.

         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]

I would make a few small tweaks:

         ulong factorial (uint dataValue)
            {
                if (dataValue == 0)
                {
                    return 1;
                }
                else
                {
                    return dataValue * factorial(dataValue - 1);
                }
           
            }

(Hmmm...anyone know to to highlight insider code tags?

 

[sysprog]

(Hmmm...anyone know to to highlight insider code tags?

/* ##\TeX \mathtt{\ can\ show\ \textbf{bold},\ \underline{underline}, \ and\ \textit{italic}\ inside\ code\ tags.} ## */

 

[jedishrfu]

I would make a few small tweaks:

         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.

 

[sysprog]

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:

[b]bold[/b] [spoiler]hidden text[/spoiler][code=c]    printf("text");

[/code]

 

[sysprog]

Oops. This worked before the upgrade.

/* ##\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.}$ */

 

[Greg Bernhardt]

Oops. This worked before the upgrade.

Why would you want rendered equations inside a code tag?

 

[sysprog]

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.

 

[Greg Bernhardt]

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.

 

[sysprog]

My immediately preceding post in that thread would appear to indicate otherwise. Inside code tags, the bbcode tags get treated as literals.

 

[sysprog]

Is there a new prescribed method for highlighting inside code tags?

 

[Greg Bernhardt]

Is there a new prescribed method for highlighting inside code tags?

Click the code button in the editor. There is an option.

 

[Vanadium 50]

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.

 

[sysprog]

This is a test.

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 something 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.

 

[rcgldr]

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.

 

[Vanadium 50]

otherwise you will recurse forever and a day

I think you'd be surprised how quickly this crashes.

 

[jedishrfu]

I was thinking of this song when I wrote forever and a day

 

[rcgldr]

Historical trivia - although early versions of Fortran did not support recursion, the somewhat unusual mathematical language APL, which dates back to the 1960's, did.

https://en.wikipedia.org/wiki/APL_(programming_language)

 

[phinds]

Historical trivia - although early versions of Fortran did not support recursion, the somewhat unusual mathematical language APL, which dates back to the 1960's, did.

https://en.wikipedia.org/wiki/APL_(programming_language)

Fortran's development was, apparently, a bit scattershot and not academically rigorous. It was supported by IBM computers.

At the same time (more or less) ALGOL was developed as an academically rigorous language and it was supported by Burroughs computers. It allowed recursion. ALGOL was at that time the only acceptable language for submitting sample code / algorithms to the Association for Computing Machinery

 

[.Scott]

@Chestermiller
As many have already replied, this is an example of recursion. You will also get recursion when funcA calls funcB and funcB calls funcA - hopefully with some check that prevents the process from continuing ad infinitum. As @rcgldr explained, each time a function is called, it allocates a block of memory on the stack for the local variables.

Most computer languages support recursion. If you write a program with functions that are recursive and without a check to keep the recursion finite, the compiler might catch it and give you a warning. More typically, it will make it to runtime where a "stack overflow" will be generated and reported.

The concept of separating the compiled program (code) from the data has become the norm - so much so that some of the terminology related to this is rarely used anymore. For example, a "pure code" block is a section of memory that contains only code and no data - once execution begins, it is in essence read-only. But nowadays, programmers seldom refer to a code block as "pure" because the alternative is considered absurd.

There was a day when every byte of memory was precious and parameters were always passed to a function by writing them to memory that was within the code block. Or, worse yet (by today's standards) instructions within a function would be modified before the function was called. The HP2100 series minicomputers stored the return address (from the calling routine) at the word before the function. This made their code blocks inherently impure.

There is a related term: reentrancy - whether a function can be called again before it has completed. Recursion requires reentrancy. But any routine that is shared among separate concurrent execution threads must also be reentrant.

 

[sysprog]

This is a good tutorial on recursion, beginning with factorials: http://web.mit.edu/6.031/www/fa17/classes/14-recursion/

 

[harborsparrow]

Many good responses so far.

A classic programming exercise is to have students solve a problem using recursion (which extends the "stack" automatically), and then also solve the same program without recursion, which requires the student arduously to store the state of the calculation after each step by manual coding in arrays.

Once you understand how to do that, then it is time to learn about tail recursion, a clever trick that prevents stack overflow absolutely. This following example is for Scala (an extension of Java). The example contains an excellent description of tail recursion:

https://www.scala-exercises.org/scala_tutorial/tail_recursion

 

[FactChecker]

The factorial is a simple example of a problem that recursion can be used to solve, but not the best because it is so easy to do in a loop. A better example is the Tower of Hanoi puzzle. Trying to do that in a loop would require a lot of effort to keep track of each step so that the information of the different steps does not get mixed up. The recursion approach allows the computer to keep track of it all with little effort on the programmer's part.

 

[stevendaryl]

I never studied compiler theory, so I don't actually know how recursion is implemented, at the machine level. I can understand it at the level of "rewrite rules". If you have a definition of $f(x)$ such as:

f(x) = if (x=0) then 1 else x * f(x-1)

then you could eventually turn, say, f(17) into an answer by continually doing one of two things:

1. Evaluate the "if-then-else" to replace it by the "then" or the "else" branch.
2. Replace expressions involving f by its definition

So for example, an evaluation sequence might be

f(17)
if (17 = 0) then 1 else 17 * f(17-1)
17*f(17-1)
17*f(16)
17*(if (16 = 0) then 1 else 16*f(16-1))
etc.

How it's actually done is something involving stacks

 

[Paul Colby]

Thanks so much guys. WOW. Can't wait to learn more about this.

I first ran across recursion in programming in the 80's using c. It was like a religious experience. Newer flavors of FORTRAN support recursion (and much much more)

 

[rbelli1]

a clever trick that prevents stack overflow absolutely

This trick only fixes the stack issue if your optimizer knows the trick.

BoB