C/++/# C# method question

10,334
3,865
I was thinking of this song when I wrote forever and a day

 

rcgldr

Homework Helper
8,546
461
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.

 
14,873
4,544
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
2,197
698
@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
523
102
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

Science Advisor
Gold Member
2018 Award
4,719
1,613
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
Science Advisor
Insights Author
8,337
2,510
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 :wink:
 

Paul Colby

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

Gold Member
840
287
523
215
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
874
179
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.
 
523
215
It is without equal at being the most annoying computer language ever devised IMO.
You haven't encountered Intercal, Maleboge, or Befunge? :oldeek: 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 :oldwink:
 

stevendaryl

Staff Emeritus
Science Advisor
Insights Author
8,337
2,510
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
874
179
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
Science Advisor
Insights Author
8,337
2,510
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
874
179

Paul Colby

Gold Member
874
179
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?
 
523
215
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]. 😉
 
523
215
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
874
179
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.
 
523
215
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
874
179
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?
 

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