C# Understanding C# Method for Calculating Factorials

[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

 

[sysprog]

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

BoB

Presumably, @harborsparrow was well aware of that when citing Scala as an example. Scala compiles to JVM byte codes, and was designed with tail recursion in mind. From the wikipedia Scala article:

Tail recursion

Functional programming languages commonly provide tail call optimization to allow for extensive use of recursion without stack overflow problems. Limitations in Java bytecode complicate tail call optimization on the JVM. In general, a function that calls itself with a tail call can be optimized, but mutually recursive functions cannot. Trampolines have been suggested as a workaround.[32] Trampoline support has been provided by the Scala library with the object scala.util.control.TailCalls since Scala 2.8.0 (released 14 July 2010). A function may optionally be annotated with @tailrec, in which case it will not compile unless it is tail recursive.[33]

 

[Paul Colby]

Since the mean topic of this thread is recursion I would mention Lisp or it's simpler more modern dialect, Scheme. Lisp is an ancient language appearing at or before FORTRAN. Tail recursion is explicitly called out in the Scheme spec. One free implementation I would recommend is Chicken Scheme which has the option of compiling into c or running interactively.

Like lisp, scheme has a very minimal syntax. The factorial function is coded

(define (factorial N)

(if (< N 1) 1 (* N (factorial (- N 1)))))​

I just now computed (factorial 3000) with no issues. Chicken Scheme implements unlimited integer and rational arithmetic. Rational numbers like 1/2 are 1/2 not 0.49999999.. Which is nice when needed. Of course I recommend Scheme for recreational programming purposes only.

Haskell is another more modern functional language which embraces both recursion and lazy function evaluation. It is without equal at being the most annoying computer language ever devised IMO. It makes programming like talking to dolphins or space aliens. Even so, many interesting programming concepts are exposed.

 

[sysprog]

It is without equal at being the most annoying computer language ever devised IMO.

You haven't encountered Intercal, Maleboge, or Befunge? You can find those, and other languages, that make Haskell, by comparison, seem straightforward, clean, tidy, perspicuous, and even soothing, at https://esolangs.org/wiki/Language_list

 

[stevendaryl]

Haskell is another more modern functional language which embraces both recursion and lazy function evaluation. It is without equal at being the most annoying computer language ever devised IMO. It makes programming like talking to dolphins or space aliens. Even so, many interesting programming concepts are exposed.

Why do you find Haskell annoying? It's certainly a very different way of thinking about programming.

The problem with slick programming languages with recursion is that it is very easy to write a program that will take the lifetime of the universe to complete. Of course, you can do that in any language, but if you don't use recursion, it's a little more obvious that you've done something suspicious.

 

[Paul Colby]

Why do you find Haskell annoying? It's certainly a very different way of thinking about programming.

Well, programming is a means to an end for a major segment of the population. Anything that keeps one from that end is annoying. Haskell is more of an obstruction than a solution for the types of problems I typically encounter. Hence, it's annoying.

 

[stevendaryl]

Well, programming is a means to an end for a major segment of the population. Anything that keeps one from that end is annoying. Haskell is more of an obstruction than a solution for the types of problems I typically encounter. Hence, it's annoying.

I guess I was asking why do you feel it is more of an obstruction than a solution.

 

[Paul Colby]

You haven't encountered Intercal, Maleboge, or Befunge?

I was restricting, excluding parody languages.

 

[Paul Colby]

I guess I was asking why do you feel it is more of an obstruction than a solution.

How many device drivers have you written in Haskell?

 

[stevendaryl]

How many device drivers have you written in Haskell?

Certainly Haskell isn't the right language for that.

 

[sysprog]

I was restricting, excluding parody languages.

Mais, bien sûr, Monsieur [but of course, Sir]; c'était une blague [that was a joke].

 

[sysprog]

Certainly Haskell isn't the right language for that.

Might that qualify as an understatement?

 

[sysprog]

How many device drivers have you written in Haskell?

The same implicit criticism is applicable to any other languages that are not readily capable of low-level machine-specific operations. As functional languages go, I think Haskell is pretty good. Why single it out as the most annoying language?

 

[Paul Colby]

Why single it out as the most annoying language?

Here, I was joking...

Well, I hadn't yet touched on Haskells many typographical failings. These are a clear matter of personal preference. But then I find indentation in python egregious but quickly put that irritant aside for its many many strong points. Haskell hates side effects and for me a computer is a side effect.

 

[sysprog]

Haskell hates side effects and for me a computer is a side effect.

You appear to be using the term 'side effect' in a manner other than to denote its functional-language-specific meaning whereby it refers to local functions modifying things that are global or otherwise outside their pre-designated scope.

 

[Paul Colby]

You appear to be using the term 'side effect' in a manner other than to denote its functional-language-specific meaning whereby it refers to local functions modifying things that are global or otherwise outside their pre-designated scope.

Cool, so the ADF435 frequency synthesizer chip has 6 hardware registers that are set by serial toggling various GPIO lines in the proper sequence. How is this done in Haskell?

 

[sysprog]

Cool, so the ADF435 frequency synthesizer chip has 6 hardware registers that are set by serial toggling various GPIO lines in the proper sequence. How is this done in Haskell?

What does that have to with the term 'side effects' as used in functional languages? Haskell can operate entirely inside a VM. Mediation of peripheral devices is up to the VM control program.

 

[Paul Colby]

What does that have to with the term 'side effects' as used in functional languages?

That's the bit I don't understand. Register values are not local as far as I can tell. Hardware has a state which needs to changed. Printing is a similar problem. Clearly language constructs exist to print, and one needed a special IO thingy to do it. How does this make Haskell less annoying?

 

[sysprog]

That's the bit I don't understand. Register values are not local as far as I can tell. Hardware has a state which needs to changed. Printing is a similar problem. Clearly language constructs exist to print, and one needed a special IO thingy to do it. How does this make Haskell less annoying?

Obviously register values are not available directly at Haskell's level of abstraction. The purveyors of Haskell don't tout it as well-adapted for low-level hardware interfacing. Apparently your purposes are better served by imperative languages.

 

[wle]

Think the idiomatic way to write a factorial function in Scheme would look more like this:

(define (factorial n)
  (let loop ((k n) (acc 1))
    (if (<= k 1)
        acc
        (loop (- k 1) (* k acc)))))

This version is tail recursive so it won't blow the stack if n is large. It uses a feature called "named let" to define a local helper function (called "loop" here) with parameters k and acc and immediately call it with k = n and acc = 1.

(Common) Lisp doesn't have tail call elimination as part of the language. Many implementations support it but (unlike Scheme) it isn't required by the language standard and some implementations don't or only partially support it. So you can't rely on tail recursion in portable Lisp code. But this isn't a problem because Lisp has perfectly good loops:

(defun factorial (n)
  "Compute the factorial of non-negative integer N."
  (check-type n (integer 0 *))
  (loop for result = 1 then (* result k)
        for k from 2 upto n
        finally (return result)))

 

[Paul Colby]

Obviously register values are not available directly at Haskell's level of abstraction. The purveyors of Haskell don't tout it as well-adapted for low-level hardware interfacing. Apparently your purposes are better served by imperative languages.

Okay, so I've said as much, right? Correct me if I'm in error. Machine state is a "side effect" in Haskell's level of abstraction, right? Machine state is very much the equivalent of setting a global variable in a program from a pure function. The language designers had to add a special IO thingy to the language to even operate on a printer.

Again, I also concede that important programming constructs, design patterns and concepts are present in Haskell. As a toy the language is fine IMO.

 

[Paul Colby]

This version is tail recursive so it won't blow the stack if n is large.

According to R5RS tail recursion is done if the last expression evaluated is a call to the function being recursed. AFAIK that's true for the version I gave as well.

(if condition <tail expression> <tail expression>)

 

[PeterDonis]

I don't actually know how recursion is implemented, at the machine level.

As far as the function call itself, it's just an ordinary function call, which at the machine level is just a jump instruction to the top of the function. The key is that the function itself has to be reentrant--i.e., you have to be able to have multiple calls to it active at the same time without one call clobbering another. That means that, ideally, function parameters and local variables should be stored on the stack, not in registers. For languages which insist on having those things in registers, every recursive call to the function needs to save registers on the stack before making the call, and then restore the registers from the stack after the call.

 

[FactChecker]

It's in the nature of computer languages that the more they are designed for a specific use, the worse they tend to become for other uses. If Haskell is not a good language in general for device handlers, it joins the ranks of Cobol, SQL, OpenGL, MATLAB, SLAM, SimScript, etc., which are good languages for their intended purpose.

 

[wle]

According to R5RS tail recursion is done if the last expression evaluated is a call to the function being recursed. AFAIK that's true for the version I gave as well.

The last expression evaluated in your version is (* N (factorial (- N 1))), which is a multiplication. Your function has to evaluate the sub-expression (factorial (- N 1)) before it can evaluate the product with N.

 

[sysprog]

Machine state is a "side effect" in Haskell's level of abstraction, right?

The short answer to that question is yes, but in this context it's in my view kind of a loaded question. Haskell uses monadic constructs for such things as IO, clock, and emulation of
(Haskell-specific) finite state machines The real machine state in a computer running Haskell is not available unmediatedly to a program written in the Haskell language.

Here's a page which may provide a charitably good-humored perspective on Haskell:
The Evolution of a Haskell Programmer

[I recommend using the following bookmarklet (copy it and paste it into the address bar to fix the page colors; save it as a bookmark to use it on other similarly annoying pages) to fix the obnoxious color scheme on that page]

javascript:(function(){var newSS, styles='* { background: white ! important; color: black !important } :link, :link * { color: #0000EE !important } :visited, :visited * { color: #551A8B !important }'; if(document.createStyleSheet) { document.createStyleSheet("javascript:'"+styles+"'"); } else { newSS=document.createElement('link'); newSS.rel='stylesheet'; newSS.href='data:text/css,'+escape(styles); document.getElementsByTagName("head")[0].appendChild(newSS); } })();