Recursion - do you use it in the real world?

[sasa]

...
I don't find this example particularly distasteful in any way:
...

Are you kidding? Definitely one of the worst code I ever seen! 
Thank you for sharing for my collection!

Instead, use this structural code:

Code: [Select]

void func(char filename, int buffer_size)
{
   FILE *file = NULL;
   void *buffer = NULL;

   file = fopen(filename,"rb")
   if(file == NULL)
      return FAILURE;

   buffer = malloc(buffer_size);
   if(buffer == NULL)
   {
      fclose(file);
      return FAILURE;
   }

   while(read_a_record(file, buffer))
   {

      if(record_matches(buffer))
        do_stuff_with_matching_records(buffer);

   }

   free(buffer);
   fclose(file);

   return SUCCESS;
}


[Cerebus]

Pretty much waste of time in this thread.

And yet, here you still are a day later, still banging on about it...

Are you kidding? Definitely one of the worst code I ever seen! 
Thank you for sharing for my collection!

You evidently have a lot of spare time to waste.

By the way, you might just care to note this from "man fclose":

NOTES
     The fclose() function does not handle NULL arguments; they will result in a segmentation violation.
     This is intentional - it makes it easier to make sure programs written under FreeBSD are bug free.
     This behaviour is an implementation detail, and programs should not rely upon it.

[hamster_nz]

Are you kidding? Definitely one of the worst code I ever seen! 
Thank you for sharing for my collection!

Instead, use this structural code:

Code: [Select]

void func(char filename, int buffer_size)
{
   FILE *file = NULL;
   void *buffer = NULL;

   file = fopen(filename,"rb")
   if(file == NULL)
      return FAILURE;

   buffer = malloc(buffer_size);
   if(buffer == NULL)
   {
      fclose(file);
      return FAILURE;
   }

   while(read_a_record(file, buffer))
   {

      if(record_matches(buffer))
        do_stuff_with_matching_records(buffer);

   }

   free(buffer);
   fclose(file);

   return SUCCESS;
}


Gosh... that fishing trip took a while. 

I always thought that dogmatic structural code only allowed for a single return statement (or none, if it is a void function) - https://hackerchick.com/religious-war-48293-single-vs-multiple/

I worked on one company where that was enforced, with the most often given reason being that you avoid multiple different blocks to release resources (the repeated fclose() calls in the above code)

And then there is also the mantra that conditional expressions shouldn't have any side effects. For example this pseudo-code might be buggy, depending on the target language semantics:

Code: [Select]

       WHILE timer_not_expired AND read_a_record(file, buffer) DO
         ...
       END WHILE

This is fine in C, but the Pascal equivalent would be buggy as all parts of the expression are guaranteed to be evaluated.

Surely the height of structural code correctness would be:

Code: [Select]

void func(char filename, int buffer_size)
{
   FILE *file = NULL;
   int rtn = SUCCESS;

   file = fopen(filename,"rb")
   if(file != NULL) {
     void *buffer = NULL;

     buffer = malloc(buffer_size);
     if(buffer != NULL)
     {
       int new_record;

       new_record = read_a_record(file, buffer);
       while(new_record)
       {
         if(record_matches(buffer))
           do_stuff_with_matching_records(buffer);
         new_record = read_a_record(file, buffer)
       }
       rtn = SUCCESS
       free(buffer);
     }
     fclose(file);
   }
   return rtn;
}

I am sure that we both agree that that is 'correct' but clunky.

[John Coloccia]

...
I don't find this example particularly distasteful in any way:
...

Are you kidding? Definitely one of the worst code I ever seen! 
Thank you for sharing for my collection!

Instead, use this structural code:

Code: [Select]

void func(char filename, int buffer_size)
{
   FILE *file = NULL;
   void *buffer = NULL;

   file = fopen(filename,"rb")
   if(file == NULL)
      return FAILURE;

   buffer = malloc(buffer_size);
   if(buffer == NULL)
   {
      fclose(file);
      return FAILURE;
   }

   while(read_a_record(file, buffer))
   {

      if(record_matches(buffer))
        do_stuff_with_matching_records(buffer);

   }

   free(buffer);
   fclose(file);

   return SUCCESS;
}


Searching through a function to see that resources have been properly released...just what I want.

hamster_nz:
FWIW, I would generally change the error cleanup to be inline with normal termination...something like

Code: [Select]

int ret = SUCCESS;

.
.
.
    if (ut_oh) {
        ret = ERROR;
        goto cleanup;
    }
.
.
.

cleanup:
    if (file != NULL) {
        fclose(file);
    }

    if (buffer != NULL) {
        free(buffer);
    }

    return ret;
}


This generally makes for a very clean implementation if you can structure it like this, though I still prefer yours as opposed to random returns and resource management scattered through the code. Simple to read, simple to test, and simple to document. I actively encourage this coding style, and wish more people would forget about misguided dogma of the past.

[hamster_nz]

FWIW, I would generally change the error cleanup to be inline with normal termination...something like

Code: [Select]

int ret = SUCCESS;

.
.
.
    if (ut_oh) {
        ret = ERROR;
        goto cleanup;
    }
.
.
.

cleanup:
    if (file != NULL) {
        fclose(file);
    }

    if (buffer != NULL) {
        free(buffer);
    }

    return ret;
}


This generally makes for a very clean implementation if you can structure it like this, though I still prefer yours as opposed to random returns and resource management scattered through the code. Simple to read, simple to test, and simple to document. I actively encourage this coding style, and wish more people would forget about misguided dogma of the past.

If you assume failure unless you succeed, it becomes even cleaner...

Code: [Select]

   int ret = ERROR; /* Assume we have failed */
.
.
.
    if (ut_oh) {
       goto cleanup;
    }
.
.
.
    ret = SUCCESS;  /* Only if we get here have we succeeded! */
cleanup:
    if (file != NULL) {
        fclose(file);
    }

    if (buffer != NULL) {
        free(buffer);
    }

    return ret;
}


This generally makes for a very clean implementation if you can structure it like this, though I still prefer yours as opposed to random returns and resource management scattered through the code. Simple to read, simple to test, and simple to document. I actively encourage this coding style, and wish more people would forget about misguided dogma of the past.

I too agree that it makes a reasonable framework for somebody to hang their hat on. It might be somewhat of an acquired taste, but as you point out it does have merits.

I think of it much like try/catch blocks in Java - it takes the exception handling out of the main flow of the code, and ensures consistency in managing resources.

[sasa]

I always thought that dogmatic structural code only allowed for a single return statement (or none, if it is a void function) - https://hackerchick.com/religious-war-48293-single-vs-multiple/

These are rather dogmatic opinions I never took helpful in C.  If have an alarm before loop block start and no extra to handle I see more than fine to handle it at beginning having several return/end points.

However, in OOP languages, that is more serious issue and thus that should basically be strict rule after object is created.

I worked on one company where that was enforced, with the most often given reason being that you avoid multiple different blocks to release resources (the repeated fclose() calls in the above code)

I suppose the same company allowed labels, goto, endless loops, multiple continue and breaks? That certainly break fundamental rule about structural programming, which is paradox. I would left that company immediately.

And then there is also the mantra that conditional expressions shouldn't have any side effects. For example this pseudo-code might be buggy, depending on the target language semantics:

Code: [Select]

       WHILE timer_not_expired AND read_a_record(file, buffer) DO
         ...
       END WHILE

This is fine in C, but the Pascal equivalent would be buggy as all parts of the expression are guaranteed to be evaluated.

In modern Pascal implementations, as Delphi, there is compiler directive for short-circuit evaluation. Specifically in Delphi, it is set to true by default.

In general, with unknown short-circuit evaluation status for language implementation and with one or more function call and/or even assigning (in C like languages), it is rather undefined what compiler will optimize to be evaluated first. Thus it is advisable to avoid that kind of expressions and handle inside the block.

I am sure that we both agree that that is 'correct' but clunky.

If that is the required rule, then generally yes.

However, you do not need new_record in this case and multiple assignments. Or can be used do-while loop when suitable. As well, initial value of  rtn should be FAILURE, but that is obviously unintentional mistake...

Then again, proper handling depends from situation to situation.

[NorthGuy]

Code: [Select]

       WHILE timer_not_expired AND read_a_record(file, buffer) DO
         ...
       END WHILE


In modern Pascal implementations, as Delphi, there is compiler directive for short-circuit evaluation. Specifically in Delphi, it is set to true by default.

In general, with unknown short-circuit evaluation status for language implementation and with one or more function call and/or even assigning (in C like languages), it is rather undefined what compiler will optimize to be evaluated first. Thus it is advisable to avoid that kind of expressions and handle inside the block.

How exactly would you handle this inside the block?

[hamster_nz]

I worked on one company where that was enforced, with the most often given reason being that you avoid multiple different blocks to release resources (the repeated fclose() calls in the above code)

I suppose the same company allowed labels, goto, endless loops, multiple continue and breaks? That certainly break fundamental rule about structural programming, which is paradox. I would left that company immediately.

No, they had other things like tight naming conventions (at least it wasn't Hungarian notation - phew), all variables had to be assigned initial values, and so on.

This was in the days before really good optimizing C compilers & linters (late 80s?), so the rules actually did make some sense. It made more sense ithose days of a 24-line screen, where even on short bits of code the allocating and releasing of resources were not likely to be on the screen at the same time.

It was some whack-ball proprietary OS, the name of which escapes me... it might have been CTOS (https://en.wikipedia.org/wiki/Convergent_Technologies_Operating_System)

[John Coloccia]

I suppose the same company allowed labels, goto, endless loops, multiple continue and breaks? That certainly break fundamental rule about structural programming, which is paradox. I would left that company immediately.

Who made these "rules?" Even MISRA-2012 has relaxed the rule banning gotos after it INCREASED the error rate. The goto rule comes from a horribly misunderstood paper by Dijkstra. Dijkstra was writing about people creating spaghetti code using C by misunderstanding how C was supposed to work, and simply using gotos to control their control flow. Somehow this got turned into the rule "you can't use gotos...gotos are bad." It's a STUPID rule and has caused countless extra lines of code, filled with countless extra bits of logic and countless more bugs. More than even just being a stupid rule, I'll go one step further and say that I believe the rule is simply wrong because it actively leads to code which is more complicated with more potential for bugs, more difficult to understand, and more difficult to test (higher complexity).

[bd139]

Not only that, Djikstra also said to Knuth: Please don't fall into the trap of believing that I am terribly dogmatic about [the go to statement]. I have the uncomfortable feeling that others are making a religion out of it, as if the conceptual problems of programming could be solved by a simple trick, by a simple form of coding discipline!

[Cerebus]

...
The goto rule comes from a horribly misunderstood paper by Dijkstra. Dijkstra was writing about people creating spaghetti code using C by misunderstanding how C was supposed to work, and simply using gotos to control their control flow.

Erm, no. The paper (strictly, not a paper, but a letter to the editor) was called "Go To Statement Considered Harmful" and was in Volume 11 No 3 of the Communications of the ACM in March 1968 - about 4 years before C saw the light of day.

You can Dijkstra's actual words here.

[sasa]

It's a STUPID rule and has caused countless extra lines of code, filled with countless extra bits of logic and countless more bugs.

Then you and the most of people here missing the point of using higher level languages - then better code all in pure assembler.

And greatly misunderstood words are: "should", "shall", "must", "except". Generally, you have to apply these rules to retain coding style consistent, however if justified or only possible otherwise, then use another approach.  Company with a tick book of strict rules allow no exceptions and which will require days to read, search only for mediocrity slave labor.

Even I never needed goto in C/Pascal, they probably may be helpful or only possible in some situation. The same with recursion - use it only when necessary or appropriate, not as common practice. Code example posted by hamster_nz (with goto, endless loop, continue, break...) is messy as can be - a gem to show students how not to code. And secondly, compiler expect expressions  with loops, then can make better code optimization.

Etc, already all mentioned. However,  it is evident that here is too much trolling and google-foo masters in order to see real purpose of fundamental rules and in general good practice in programming.

[HoracioDos]

I would suggest OP to add following in a pool:
"Use recursion only when necessary or appropriate."
That is the most correct answer.

I would add: I don't write code for any interesting project where recursion would be needed. 

[NorthGuy]

Then you and the most of people here missing the point of using higher level languages - then better code all in pure assembler.

What is the point? Why did you use C for your non-recursive example, not Assembler? You would get better execution time with the Assembler, wouldn't you? Wasn't that your goal? Then why C?

[John Coloccia]

...
The goto rule comes from a horribly misunderstood paper by Dijkstra. Dijkstra was writing about people creating spaghetti code using C by misunderstanding how C was supposed to work, and simply using gotos to control their control flow.

Erm, no. The paper (strictly, not a paper, but a letter to the editor) was called "Go To Statement Considered Harmful" and was in Volume 11 No 3 of the Communications of the ACM in March 1968 - about 4 years before C saw the light of day.

You can Dijkstra's actual words here.

Whatever. I've read it numerous times, and the fact that it's talking about structured programming instead of C specifically is beside the point.

[Cerebus]

...
The goto rule comes from a horribly misunderstood paper by Dijkstra. Dijkstra was writing about people creating spaghetti code using C by misunderstanding how C was supposed to work, and simply using gotos to control their control flow.

Erm, no. The paper (strictly, not a paper, but a letter to the editor) was called "Go To Statement Considered Harmful" and was in Volume 11 No 3 of the Communications of the ACM in March 1968 - about 4 years before C saw the light of day.

You can Dijkstra's actual words here.

Whatever. I've read it numerous times, and the fact that it's talking about structured programming instead of C specifically is beside the point.

It was just a point of information, largely for the benefit of those who have not read it, let alone "numerous times"; there's no need to be so dismissive.

[John Coloccia]

It was just a point of information, largely for the benefit of those who have not read it, let alone "numerous times"; there's no need to be so dismissive.

Sorry, Cerebus. You're right, and I apologize.

[westfw]

You can Dijkstra's actual words here.   

Hmmph.   You can BUY the article there :-(   I guess if you're behind the right .edu domain it might show up for free...
In 68, he would have been pushing the advantages of Algol over Fortran and BASIC, right?

Here's a copy: http://www.u.arizona.edu/~rubinson/copyright_violations/Go_To_Considered_Harmful.html

Huh.  The way I read that, he suggests that recursion (bring us back on topic) is superior to all forms of looping!

"Let us now consider repetition clauses (like, while B repeat A or repeat A until B). Logically speaking, such clauses are now superfluous, because we can express repetition with the aid of recursive procedures."

[Cerebus]

You can BUY the article there :-(   

Actually, that's just a DOI which identifies the article uniquely. Although the DOI web portal will send you to the original publisher (if there is one online) the DOI itself is just an persistent identifier, and if you stick it into the right search engine will usually find you somewhere to download it.

[brucehoult]

Even I never needed goto in C/Pascal, they probably may be helpful or only possible in some situation. The same with recursion - use it only when necessary or appropriate, not as common practice. Code example posted by hamster_nz (with goto, endless loop, continue, break...) is messy as can be - a gem to show students how not to code. And secondly, compiler expect expressions  with loops, then can make better code optimization.

I'm a professional compiler guy. What you say is ABSOLUTELY untrue of any modern production compiler. In particular it is untrue of gcc or llvm.

If you write this...

Code: [Select]

int sum(int *p){
    int i, t = 0;
    while ((i = *p++)) t += i;
    return t;
}

... then clang sends the following to the optimiser (obtain with "clang myloop.c -S -emit-llvm")...

Code: [Select]

define i32 @sum(i32* %p) #0 {
  %1 = alloca i32*, align 8
  %i = alloca i32, align 4
  %t = alloca i32, align 4
  store i32* %p, i32** %1, align 8
  store i32 0, i32* %t, align 4
  br label %2

; <label>:2                                       ; preds = %7, %0
  %3 = load i32*, i32** %1, align 8
  %4 = getelementptr inbounds i32, i32* %3, i32 1
  store i32* %4, i32** %1, align 8
  %5 = load i32, i32* %3, align 4
  store i32 %5, i32* %i, align 4
  %6 = icmp ne i32 %5, 0
  br i1 %6, label %7, label %11

; <label>:7                                       ; preds = %2
  %8 = load i32, i32* %i, align 4
  %9 = load i32, i32* %t, align 4
  %10 = add nsw i32 %9, %8
  store i32 %10, i32* %t, align 4
  br label %2

; <label>:11                                      ; preds = %2
  %12 = load i32, i32* %t, align 4
  ret i32 %12
}

The intermediate code consists of blocks. Every block except the function entry has a label. Every block ends with one of:

• a return from the function
• an unconditional goto a label
• a unconditional goto one of two labels

The order of thee blocks (except the first one) is completely irrelevant, and exactly the same code will be generated in the end (assuming some optimisation), no matter what order the blocks are presented in.

There is no concept of a "loop" in the original source language. Loops are discovered by the optimiser. You'll get exactly the same code in the end no matter whether you used labels and gotos or loops in your source code.

[brucehoult]

Huh.  The way I read that, he suggests that recursion (bring us back on topic) is superior to all forms of looping!

"Let us now consider repetition clauses (like, while B repeat A or repeat A until B). Logically speaking, such clauses are now superfluous, because we can express repetition with the aid of recursive procedures."

Certainly he does! He was a smart guy. He states the reason why earlier:

My second remark is that our intellectual powers are rather geared to master static relations and that our powers to visualize processes evolving in time are relatively poorly developed.

Iteration in a program requires the programmer to think explicitly about time: THIS happens, and then THIS.

Recursion expresses a static relation: if THIS is correct, then THIS is also correct. e.g. if fib(9) can be somehow relied upon (we don't need to care how) to produce the correct result, then 10 * fib(9) is certainly the correct result for fib(10). No notion of time is required, only correctness.


Here's another interesting bit in Dijkstra's letter:

Heinz Zemanek at the pre-ALGOL meeting in early 1959 in Copenhagen quite explicitly expressed his doubts whether the go to statement should be treated on equal syntactic footing with the assignment statement. To a modest extent I blame myself for not having then drawn the consequences of his remark

We have later come to realise that in fact the assignment statement causes *exactly* the same kinds of difficulties in reasoning about programs as the goto!

This is tied in again with whether you need the notion of time or not. If you say "now x has the value 10 .. and NOW x has a value one bigger than it had before" then you need to think about time to understand your program. If you make a rule that each name (like x) can only be defined or initialized in one place, and never redefined (assigned) then you can remove the idea of time from your program and it becomes much easier to think about.

Finite loops are possible only if you have assignment. The expression controlling the loop must be true at some moment in time, and then false later on for the loop to exit.

Recursion lets you do away with this, and only initialize variables, never reassign them.

[Cerebus]

Recursion lets you do away with this, and only initialize variables, never reassign them.

Did I just hear someone say "static single assignment form". 

[westfw]

This is tied in again with whether you need the notion of time or not.

That would neatly explain the way that embedded programmers tend to disagree with algorithm designers.
Arguably, real time and interactive programming (both relatively rare at the time of The Letter) always include a notion of time...

[NorthGuy]

Certainly he does! He was a smart guy. He states the reason why earlier:

My second remark is that our intellectual powers are rather geared to master static relations and that our powers to visualize processes evolving in time are relatively poorly developed.

Iteration in a program requires the programmer to think explicitly about time: THIS happens, and then THIS.

Recursion expresses a static relation: if THIS is correct, then THIS is also correct. e.g. if fib(9) can be somehow relied upon (we don't need to care how) to produce the correct result, then 10 * fib(9) is certainly the correct result for fib(10). No notion of time is required, only correctness.

If this premise was true, HDL languages (e.g. VHDL, Verilog) would be much easier to master than C. In reality, the exact opposite happens. People grasp time relationships and learn programming in C rather quickly, but HDL learning curve is usually much steeper and people find HDL concepts more confusing than C. Worse yet, Xilinx is now offering FPGA programming in C to ease the way.

[brucehoult]

Recursion lets you do away with this, and only initialize variables, never reassign them.

Did I just hear someone say "static single assignment form". 

It's something pretty close, though SSA requires special "PHI" instructions in place of assignments.

Also, of course, the llvm code I showed uses variables in "memory" to get around single-assignment. One of the first things the optimiser does is replace memory variables with SSA variables (and introduce PHIs)