# C/++/# C# method question

#### jedishrfu

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

#### rcgldr

Homework Helper
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.

#### phinds

Gold Member
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.

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

Homework Helper
@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.

#### harborsparrow

Gold Member
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

Gold Member
2018 Award
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

Staff Emeritus
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

Gold Member
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

Gold Member
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

Gold Member
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

Staff Emeritus
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

Gold Member
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

Staff Emeritus
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

Gold Member
You haven't encountered Intercal, Maleboge, or Befunge?
I was restricting, excluding parody languages.

#### Paul Colby

Gold Member
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

Staff Emeritus
How many device drivers have you written in Haskell?
Certainly Haskell isn't the right language for that.

#### sysprog

Paul Colby said:
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

Gold Member
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

Paul Colby said:
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

Gold Member
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?

"C# method question"

### 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