Recursion - do you use it in the real world?

[Howardlong]

While debugging some customer code in production last week that kept crashing, I came across a recursive function. While it wasn't the recursiveness in itself that caused the problem on its own, it exacerbated the problem (memory allocated but not released).

I could see why the programmer chose to use recursion, but to me it seemed like they'd used it "because you can" rather than for readability reasons. Had the programmer remembered to release all his initialised variables as they dropped out of scope I might have given him more credence. Those initialised heap variables were arrays of strings that never changed  so should've been constants anyway, and never used either heap or stack. (The heap grew to... wait for it... 50GB before the process broke.)

I think that in over 30 years I can count on the digits of one hand the number of times I've come across recursion used outside the classroom, and this was one of them. Most of those times have been when looking at the C runtime library, such as qsort.

[boffin]

I use it quite often, check out this thread.  Recursion - do you use it in the real world?
(sorry, couldn't resist)

[stmdude]

I use recursion quite often actually. Usually when parsing fileformats that either have chunked sections, or simply formats such as XML.

However, this is on PCs, which tons of VM-space and RAM, so I just make sure I keep what I need on the stack, and I should be good.

However, I would never do recursion on an embedded system. It kind of goes against the whole "don't dynamically allocate memory" and "the system should behave the same the first time it's run as when it has been running for 100 days straight" rules.

[legacy]

It depends on the purpose! Algorithms in AI use recursion, e.g. if you have to implement A* or A*++ you have to deal with recursion (and backtracking)

[bd139]

I only use it if I can benefit from tail recursion (64-bit .net CLR and Common Lisp!). Read The Structure and Interpretation of Computer Programs (SICP) for why: https://mitpress.mit.edu/sicp/full-text/book/book-Z-H-4.html#%_toc_start but fundamentally tail recursion is readable but executes in one stack frame.

Warning: book messes with your head.

Oh use cases I have used: compilers, parsers, optimisers, various algorithms etc

The main reason we don't seem to see it often is that everything in C languages punishes you by kicking you in the nuts (stack overflows, heap usage etc).

50Gb is smaller than some of the working sets I've seen using recursive code. We've got a few 512Gb nodes that run a matching engine that use 300Gb of RAM on a bad day. You don't want to have to minidump that fucker though. Even with several TiB of enterprise SSD it takes a day.

[legacy]

well trees need recursion, thus a shell on a filesystem need recursion, as well as some tool which need to operate on filesystem, but also compilers need recursion when they have to deal with AST.

A lot of algorithms in motion planning need recursion!

[rstofer]

One of the largest examples I have seen is the Pascal Compiler by Niklaus Wirth.  Recursive descent is an elegant way to structure a compiler.  We can go straight from the syntax graph to code!  Algol might have done the same thing but I haven't looked at the compiler code.

A more simple example might be evaluating an expression.  It is common to define an expression in terms of expressions and operators.

The trivial example is using recursion to compute factorials.

[Bruce Abbott]

Microchip MPLAB XC8 C Compiler (Free Mode) V1.42
Build date: Apr 12 2017
Part Support Version: 1.42
Copyright (C) 2017 Microchip Technology Inc.
License type: Node Configuration

Warning [1273] ; . Omniscient Code Generation not available in Free mode
Error   [1089] C:\code\PIC\test\16F630 blinky.c; 17. recursive function call to "_foo"
(908) exit status = 1

[sasa]

Microchip MPLAB XC8 C Compiler (Free Mode) V1.42
...

IIRC, only 13 sub calls are allowed in most of small PICs, thus it is anyway pointless to do any recursion here.

[sasa]

I could see why the programmer chose to use recursion, but to me it seemed like they'd used it "because you can" rather than for readability reasons.
...

There is several problems here...

1. Some problems can be solved without recursion, but usually is used recursion. One of it is mentioned searching a file in directory tree I have made and use my own class decades ago without recursion. Second one I can remember is Huffman tree, which also can be searched without recursion. And original QSort  have  O(N*N) only in worst case scenarios, however, all that scenarios can be easily bypassed in algorithm... Similar with A* and chosen method searching the shortest path...

2. Every recursive algorithm can be converted to non-recursive, simulating stack. A bit of more complex, however absolute control over memory usage.

Plain recursion is usually used because that is easier and clearer, often inappropriate, especially for embedded systems.

[fourtytwo42]

In my experience heavily used in traffic "classification" algorithms in data communications and decryption
Just by way of a partial explanation you dont know the extent of the problem nor the number of branches so unless you have infinite memory recursion is a sensible way to handle it.

[SimonR]

I'm with stmdude on this

I use recursion for parsing trees, mostly XML but often my own.
But would never use it in a C based embedded project.
All my recursive projects are PC based in C# which should catch any problems which have never happened yet.

[Cerebus]

The time you suddenly realise how often you use recursion is when you use some dumb programming language that doesn't support recursion, like older variants of FORTRAN.

Remember too, that recursion is not always obvious and in your face, such as tail recursion or tree walks, but often lurks a layer or two away in mutual recursion in some very everyday programming.

[Howardlong]

50Gb is smaller than some of the working sets I've seen using recursive code. We've got a few 512Gb nodes that run a matching engine that use 300Gb of RAM on a bad day. You don't want to have to minidump that fucker though. Even with several TiB of enterprise SSD it takes a day.

Funnily enough, this isn't a million miles away from the functionality I was debugging. There's another bit of the system that deals with this, dev guys keep telling me to throw more RAM at the problem, and I assure them that they're welcome to it, once they can tell me how much, how they derived the figure, and why they have an algorithm that needs so much memory. Sometimes, occasionally, it's justified, matching engines are just such an example. Most of the time in my experience it's programmers not being concerned enough about non-functionals such as performance, how much that RAM will cost across multiple environments, and whether we will need to throw even more tin at the problem, and the costs of that.

[bd139]

Agree entirely. In this case it was definitely justified. Three of us pulled two weeks of lates hammering at visual studio to move it off an IBM z9 EC that had the consultant vultures waiting to swoop on a renewal and hardware refresh. Efficiency was a low priority. Make the big blue consultants bugger off was priority. We had a few mid-range HP DL560 chassis lying around idling on load standby so we just used them. The dataset was crudely piped entirely into RAM daily and processed there with LINQ because we didn't understand the model very well on the z9.

Now we understand it, it's all being carefully rearchitected with SQS/EC2/ElastiCache Redis on AWS now powered by glorious C++11 via clang/LLVM on CentOS. Finally something that isn't a corn filled turd to play with

[janoc]

There is several problems here...

2. Every recursive algorithm can be converted to non-recursive, simulating stack. A bit of more complex, however absolute control over memory usage.

Actually it goes both ways - any iteration can be expressed as a (tail) recursion and any recursion can be expressed using an iteration + counter or stack. There is actually a theorem on this (paper from 1966):

https://academic.oup.com/comjnl/article-pdf/9/1/45/997564/9-1-45.pdf

Now whether to use one or the other depends on the problem and things like constraints of the technology you are using - if the compiler doesn't do tail call optimization, then recursion could be an expensive option vs iteration. On the other hand,  algorithms on some more complex data structures, such as the already mentioned trees or graphs are much more naturally expressed using recursion. They can be implemented iteratively but the code will be a pain to read and debug ...

Also it depends a lot on the programming language - in some high level languages, especially functional ones, recursion is the thing to use and loops are frowned upon (or even impossible because the language doesn't have the construct - tail recursion can do all that a loop can!)

People doing low level embedded programming won't see it that much, because recursive algorithms in C++ or C on an MCU are pain due to the small stack and lack of tail call optimization. But there are ports of e.g. Scheme to small MCUs if someone wants to try that.

[MrTurk]

 In DSP, IIR filter design is a recursive computation of inpulse responses but nobody uses IIR filters IMO

Nexus 5 cihaz?mdan Tapatalk kullan?larak gönderildi

[nctnico]

I'm using IIR filters exclusively  But no real-time calculation of coefficients.

[hamster_nz]

I could see why the programmer chose to use recursion, but to me it seemed like they'd used it "because you can" rather than for readability reasons.
...

There is several problems here...

1. Some problems can be solved without recursion, but usually is used recursion. One of it is mentioned searching a file in directory tree I have made and use my own class decades ago without recursion. Second one I can remember is Huffman tree, which also can be searched without recursion. And original QSort  have  O(N*N) only in worst case scenarios, however, all that scenarios can be easily bypassed in algorithm... Similar with A* and chosen method searching the shortest path...

2. Every recursive algorithm can be converted to non-recursive, simulating stack. A bit of more complex, however absolute control over memory usage.

Plain recursion is usually used because that is easier and clearer, often inappropriate, especially for embedded systems.

Completely agree - recursion is usually suited only to quick hacks, and in cases when resource usage cannot be a problem.

The classic text-book example used to be a 'factorial' function:

Code: [Select]


int factorial(int i) {
   return (i == 1) ? 1 : i*factorial(i-1);
}

So I now compute factorial 300,000, and watch my program segfault....

[brucehoult]

Code: [Select]


int factorial(int i) {
   return (i == 1) ? 1 : i*factorial(i-1);
}

So I now compute factorial 300,000, and watch my program segfault....

Hmmmm. Let me try that...

Code: [Select]

$ gcc recfact.cpp -c -Os -o recfact.o
$ objdump -d recfact.o

recfact.o:     file format elf64-littleriscv


Disassembly of section .text:

0000000000000000 <_Z9factoriali>:
   0: 4785                li a5,1
   2: 873e                mv a4,a5

0000000000000004 <.L3>:
   4: 00e50663          beq a0,a4,10 <.L1>
   8: 02a787bb          mulw a5,a5,a0
   c: 357d                addiw a0,a0,-1
   e: bfdd                j 4 <.L3>

0000000000000010 <.L1>:
  10: 853e                mv a0,a5
  12: 8082                ret

Yeah, nah .. no segfault there, your stack will be fine.

*Arithmetic* overflow, however ,,, for sure.

[sasa]

I have seen quite a few catastrophically losing code in my professional career, no matter is it free or commercial software.

Programming language can learn (conditionally) anyone in a weekend or few, but the difference between pure and good programmer is to have algorithms in his little finger using appropriate for the task, have ability to make a suitable corrections in it if needed, perform appropriate optimization and finally, as a result, it will have optimal solution for the task.

Take for example mentioned sorting. Everybody know that original QSort is one of the fastest in-place sorting algorithms (except in worst case scenarios), however his recursive nature may be extremely dangerous. If there is maximally 100's of data to sort, the most optimal solution may be to use Shell or even Insertion...

Proper decision depends on precisely defined requirements, according to complete software design. Often is much more beneficial if CEO have no grasp about programming, instead to know a bit, combining with a "God complex", including as well working environment with junior software engineers. That is a nightmare for any skilled and experience programmer.

[brucehoult]

2. Every recursive algorithm can be converted to non-recursive, simulating stack. A bit of more complex, however absolute control over memory usage.

Plain recursion is usually used because that is easier and clearer, often inappropriate, especially for embedded systems.

Completely agree - recursion is usually suited only to quick hacks, and in cases when resource usage cannot be a problem.

I agree that recursion is clearer.

Probably any complex loop can be rewritten more clearly using recursion, especially if there are multiple continues or breaks or multiple state variables to update when you loop. Each "continue" (or goto the start/end) becomes a recursive call, with the updated state variables as the arguments. And each recursive call will be tail-recursive, so with a decent compiler will cost absolutely nothing compared to writing it as a loop.

Even many things that don't *look* tail recursive can be transformed into tail recursive by a modern compiler. Your  factorial code, for example.

Transforming a naturally recursive function into iteration with an explicit stack saves virtually nothing. You might manage to use an 8 or 16 bit enum as the state to return to in your switch in your loop, instead of a 32 bit or 64 bit return PC, but that's *it*. Ok, maybe a frame pointer too if your compiler sucks or your ABI requires it (i.e. sucks). All the rest of the state saved will be identical (and identical size) in either case. The only excuse is if you're using a processor with a very limited size hardware stack.

Assuming you're processing some actual data structure in memory, and not just some abstract math function, the size required for the stack is usually no more than the number of items in your data structure, and usually it's the log of the size of your data structure. e.g. if you've got a million items of data then your recursion is probably on the order of 20 levels deep if you avoid pathological cases. For a billion items of data, 30 levels deep. Even with a fair bit of state to save on each call you're probably talking something like a KB or two of stack.

[T3sl4co1l]

2. Every recursive algorithm can be converted to non-recursive, simulating stack. A bit of more complex, however absolute control over memory usage.

Plain recursion is usually used because that is easier and clearer, often inappropriate, especially for embedded systems.

Correct.  Syntactic recursion in code is syntactic sugar, another (usually inefficient) way to implement it.  One can implement the same thing with a software stack (or queue, if you're perverted like that).

Or a loop with fixed state variables, for special cases (that really shouldn't ever be recursive).  The trivial-but-please-don't-ever-do-this examples: the factorial and Fibonacci functions, aren't even deserving of O(N) loops!

I voted "new practical solution with recursion about once a year", because although it's a lie, that's mainly because I don't do much programming.

Recursion is a useful and powerful tool, that like all tools, must be used responsibly.  If you ever have a question about your program: quantify it.  Add flags or timers, to record the execution time of a function.  Add bounds checking and limits, especially for recursive functions that can potentially use unlimited stack space!  And check your inputs and outputs.  At least fuzz the inputs.  It's utterly practical, these days, to test the entire 32-bit input space of a two-parameter, 16-bit function (only 4.some billion possible inputs).  Why deprive yourself of such cheap security?

Tim

[sasa]

I would suggest OP to add following in a pool:

"Use recursion only when necessary or appropriate."

That is the most correct answer.

[BillyD]

Well in order to define recursion, one must first define recursion.


I agree with the view that you should use it if you must, and not if you can. In terms of clarity and maintainability it can sometimes be the best approach, but if resources or scalability are an issue it's usually a non runner.

[hamster_nz]

Code: [Select]


int factorial(int i) {
   return (i == 1) ? 1 : i*factorial(i-1);
}

So I now compute factorial 300,000, and watch my program segfault....

Hmmmm. Let me try that...

Code: [Select]

$ gcc recfact.cpp -c -Os -o recfact.o
$ objdump -d recfact.o

recfact.o:     file format elf64-littleriscv


Disassembly of section .text:

0000000000000000 <_Z9factoriali>:
   0: 4785                li a5,1
   2: 873e                mv a4,a5

0000000000000004 <.L3>:
   4: 00e50663          beq a0,a4,10 <.L1>
   8: 02a787bb          mulw a5,a5,a0
   c: 357d                addiw a0,a0,-1
   e: bfdd                j 4 <.L3>

0000000000000010 <.L1>:
  10: 853e                mv a0,a5
  12: 8082                ret

Yeah, nah .. no segfault there, your stack will be fine.

*Arithmetic* overflow, however ,,, for sure.

(Sigh - nobody trusts anybody on the interweb any more)

Code: [Select]

$ cat factorial.c
#include <stdio.h>

int factorial(int i) {
   return (i == 1) ? 1 : i*factorial(i-1);
}

int main(int argc, char *argv[]) {
   int i;

   i = 4;
   printf("Factorial(%i) is %i \n", i, factorial(i));
   fflush(stdout);

   i = 300000;
   printf("Factorial(%i) is %i \n", i, factorial(i));
   fflush(stdout);
}
$ gcc -o factorial factorial.c -Wall -pedantic
$ ./factorial
Factorial(4) is 24
Segmentation fault (core dumped)
$

So a technique that gives fatal runtime errors if you level the optimizations turned off???  Nice!

Recursion? Yeah nah...

...and it doesn't matter about the overflow - it could just as well be any algorithm that can be expressed recursively. e.g. Daily interest. I was just using factorial() as it is the 'textbook' recursion example, and complex functions would bomb out sooner as they would have larger stack frames.

[brucehoult]

Take for example mentioned sorting. Everybody know that original QSort is one of the fastest in-place sorting algorithms (except in worst case scenarios), however his recursive nature may be extremely dangerous. If there is maximally 100's of data to sort, the most optimal solution may be to use Shell or even Insertion...

The danger with quicksort isn't it's recursive nature, but that it can degenerate to iteration!

If you do even the absolute minimal thing of checking the size of each half of the partition and recursing on the smaller one first then you limit the stack to at most O(log n), as the second call is a tail-call. That's at most 30 or so for any practical example. The worst case scenarios (in terms of time) are then the ones that use the *least* stack.

Quicksort's worst case time is the same as Insertion sort's best case, so it's fairly pointless recommending insertion sort as a better replacement :-)

Shell sort has short and simple code, which may be useful in some cases, but it's critically dependent on the distance sequence used. Shell's original sequence has a worst case of O(N^2) (no better than insertion sort or degenerate quicksort), but several other simple sequences can give O(N^(4/3)) (five times worse than quicksort or heapsort or mergesort for a million elements) or O(N * log^2 N) (twenty times worse than quicksort or heapsort or mergesort for a million elements).

Heapsort is the best general purpose sort if you're worried about worst case. It's twice slower than quicksort on average, but always O(N * log N) and needs only about fifteen lines of code:

Code: [Select]

void siftDown(int *v, int *end, int *p){
  int *left = v + 2*(p-v) + 1, *right = left+1;
  if (left >= end) return;
  int *branch = right >= end | *left > *right ? left:right;
  if (*p >= *branch) return;
  swap(branch, p);
  siftDown(v, end, branch);
}

void heapSort(int *v, int *end){
  for (int *i = v+(end-v-1)/2; i>=v; --i) siftDown(v, end, i);
  while (--end > v){
    swap(v, end);
    siftDown(v, end, v);
  }
}


[brucehoult]

So a technique that gives fatal runtime errors if you level the optimizations turned off???  Nice!

Why on earth would you turn the best half of the compiler off? You might as well program in assembly language then. The compiler is your friend. With modern ones, optimisation doesn't even hurt the debugger.

[hans]

If you're doing any kind of real-time systems I certainly hope you're not surrending to compiler optimisations to make code predictable in it's execution time. Giving some meaningful statements about worst case timing will become hard, so better avoid recursion at all costs.
And yes, you want the program to work without optimisations. Try debugging your code with -O1, half of the breakpoints and locals will be unresolvable.

Stack usage is also a common reason to avoid recursion.

I think recursion can be useful in meta programming, which is more a thing in C++ than in just plain C. Especially if you use recursion in some kind of constants derivation, it can be OK if you can trick the compiler to evaluate as much as possible during compilation time (e.g. use constexpr effectively). The problem is that also these kind of tricks have their limits, e.g. GCC has it's max recursion depth set to 512 as default.

In college we have been demonstrated how to use recursoin also in languages like VHDL. You certainly don't want to do data dependent recursion there, as each recursion depth will generate new hardware. However recursion depending on data structures is possible, but often it's easier and more clear to write the iterative variant.

[hamster_nz]

So a technique that gives fatal runtime errors if you level the optimizations turned off???  Nice!

Why on earth would you turn the best half of the compiler off? You might as well program in assembly language then. The compiler is your friend. With modern ones, optimisation doesn't even hurt the debugger.

It is simple - because I can.

One of the basic tenets of optimizing compilers is that the program should give the same output for the same input, the only thing is that it should be different is the performance or code size, or whatever metric you are optimizing for.

When developing code, I turn optimizations all the way up - I get far better reporting of errors, warning and any crappy code (like uninitialzed variables). It gives me more insight (and faster code, of course)

When debugging particularly hard bugs I quite often turn optimizations down for the module concerned, and check the bug is still there. Usually it is still there, so I can debug it with the state of the system always matching the state that is implied by the code.

[T3sl4co1l]

If you're doing any kind of real-time systems I certainly hope you're not surrending to compiler optimisations to make code predictable in it's execution time. Giving some meaningful statements about worst case timing will become hard, so better avoid recursion at all costs.
And yes, you want the program to work without optimisations. Try debugging your code with -O1, half of the breakpoints and locals will be unresolvable.

And, of course, anywhere the run time is critical, learn your target machines's instruction set, and inspect the compiler's assembler output!  This is also a useful pre-debugging step when the code the compiler is generating doesn't seem to make sense.

Stack usage is also a common reason to avoid recursion.

I think recursion can be useful in meta programming, which is more a thing in C++ than in just plain C. Especially if you use recursion in some kind of constants derivation, it can be OK if you can trick the compiler to evaluate as much as possible during compilation time (e.g. use constexpr effectively). The problem is that also these kind of tricks have their limits, e.g. GCC has it's max recursion depth set to 512 as default.

The downside may be the generation of a crapload of executable code, much like the VHDL case with hardware.  This can be helpful on machines with GB of RAM (cellphones maybe, PCs usually), but watch carefully for bloat on embedded systems.

An extreme example might be integrating a JIT compiler with your application, say to solve a particular instance of a combinatorially prohibitive execution tree.  A realization of this: Abrash's UT2k3 software render pipeline (search to find the series of articles).

For 99.9999% of all programs, such extremes are neither necessary nor desirable (JS does this constantly, I guess, and look at how much overhead is spent on that!) -- again, it's just another tool to be aware of; another way of thinking about programming that can inspire you in simpler cases.

Tim

[sasa]

The danger with quicksort isn't it's recursive nature, but that it can degenerate to iteration!
..

I'm not sure I following you... If any of conditions is not satisfied, new recursion call is executed and thus risk for resource. In any worst case scenario, we will have N nested recursion calls.

In the past I have modified original QSort algorithm in such manners that have no single worst-case scenario. Without much lose in speed in random data distribution (few percents only, regardless N) and as a benefit, if there is small number of different elements it is much faster (speed is comparable to Radix)... I honestly wonder how Hoare misses that...

Heap is not in-place sorting algorithm and if you are limited with memory, it is pointless. And as any binary tree, worst case scenario is known.

If you have small enough N, it is enough even Bubble...  The best solution is hybrid algorithm, which will use suitable algorithm regarding N, type of data and available resources.

As mentioned, all depends on exact requirements.

[Bruce Abbott]

If you have small enough N, it is enough even Bubble...

The only time I ever needed to sort something was when displaying a list of filenames, and then Bubble sort was plenty fast enough. 

[brucehoult]

The danger with quicksort isn't it's recursive nature, but that it can degenerate to iteration!
..

I'm not sure I following you... If any of conditions is not satisfied, new recursion call is executed and thus risk for resource. In any worst case scenario, we will have N*N recursions.

That's not correct.

The worst case for quicksort is when a partitioning step chooses the minimum or maximum element as the "pivot" and therefore ends up with partitions [0 elements; the pivot; N-1 elements]

You make a recursive call on the 0 element partition, which will be rather quick and use next to no stack. Then you make a tail-recursive call to sort the N-1 element partition. This reuses the same stack frame as you are already in and therefore uses no memory resources.

Heap is not in-place sorting algorithm and if you are limited with memory, it is pointless. And as any binary tree, worst case scenario is known.

Certainly heap sort is an in-place sorting algorithm! Read the code I posted here a few hours ago.

[NorthGuy]

The worst case for quicksort is when a partitioning step chooses the minimum or maximum element as the "pivot" and therefore ends up with partitions [0 elements; the pivot; N-1 elements]

It also might be [N-1 elements; the pivot; 0 elements] on every iteration, in which case your tail call will be wasted on the 0-element case, so you will get N levels of recursion - N*16 stack size on a 32-bit machine.

[helius]

It also might be [N-1 elements; the pivot; 0 elements] on every iteration, in which case your tail call will be wasted on the 0-element case, so you will get N levels of recursion - N*16 stack size on a 32-bit machine.

So conditionally swap L and U before making the two recursive calls. Isn't that obvious?

Your respondent already wrote

If you do even the absolute minimal thing of checking the size of each half of the partition and recursing on the smaller one first then you limit the stack to at most O(log n), as the second call is a tail-call.

(emphasis added)

[NorthGuy]

So conditionally swap L and U before making the two recursive calls. Isn't that obvious?

IMHO, it is easier to achieve the same effect by avoiding the tail recursion call altogether. Not to mention it wouldn't rely on complier optimisation.

The original:

Code: [Select]

void sort(int a, int b) {
   ...
   sort(a,j);
   sort(i,b);
}
You suggest:

Code: [Select]

void sort(int a, int b) {
   ...
   if ((j - a) > (b - i)) {
     a1 = i;
     b1 = b;
     a2 = a;
     b2 = j;
   } else {
     a1 = a;
     b1 = j;
     a2 = i;
     b2 = b;
   }
   sort(a1,b1);
   sort(a2,b2);
}
Without tail recursion:

Code: [Select]

void sort(int a, int b) {
  while (1) {
     ...
     if ((j - a) > (b - i)) {
       sort(i,b);
       b = j;
     } else {
       sort(a,j);
       a = i;
     }
  }
}

[Feynman]

I never use recursion. I'm developing embedded C and every decent coding standard forbids recursion for good reason

[brucehoult]

So conditionally swap L and U before making the two recursive calls. Isn't that obvious?

IMHO, it is easier to achieve the same effect by avoiding the tail recursion call altogether. Not to mention it wouldn't rely on complier optimisation.

As you say, a tail call is exactly equivalent to a loop. But it's easier to understand. Why not rely on the compiler to convert it instead of you? Unless you're writing your own compiler, the people at gcc or llvm implemented this optimisation many years ago -- and got it correct.

Code: [Select]

void sort(int a, int b) {
  while (1) {
     ...
     if ((j - a) > (b - i)) {
       sort(i,b);
       b = j;
     } else {
       sort(a,j);
       a = i;
     }
  }
}

Congratulations on your infinite loop :-)

Try "while (a < b)".

Or, better, use "while ((b - a) > 10)" and leave the array not quite sorted, and follow the quicksort up with an insertion sort on the whole array. That's even faster, overall. (of course that's an "if" not a "while" in the recursive formulation)

[brucehoult]

I never use recursion. I'm developing embedded C and every decent coding standard forbids recursion for good reason

No. For bad, superstitious reasons.

If you understand your algorithm and there are maximum bounds on the depth of recursion then it's absolutely fine to use it. If there aren't bounds on the depth of recursion then rewriting it as an iteration isn't going to help you. If you don't know the bounds then you shouldn't be let loose near an embedded system.

[bd139]

Indeed. You can blow the stack simply with deep abstractions. Look at the shit the java dudes throw out. I got a 2500 line stack once with no recursion!

[EntropyWizard]

It's a bit subtle, but you should google recursion.

[Cerebus]

It's a bit subtle, but you should google recursion.

As the third person to make a recursive recursion joke in this thread you win the grand prize - a free trip to a Siberian re-education camp.

[Sal Ammoniac]

My answer to this question would have to be in two parts:

On PCs and other general purpose computers: Yes, I use it whenever it makes sense.

On embedded systems: Never.

[NorthGuy]

Code: [Select]

void sort(int a, int b) {
  while (1) {
     ...
     if ((j - a) > (b - i)) {
       sort(i,b);
       b = j;
     } else {
       sort(a,j);
       a = i;
     }
  }
}

Congratulations on your infinite loop :-)

Try "while (a < b)".

Or, better, use "while ((b - a) > 10)" and leave the array not quite sorted, and follow the quicksort up with an insertion sort on the whole array. That's even faster, overall. (of course that's an "if" not a "while" in the recursive formulation)

It's not quite infinite. The "..." part represents quicksort actually sorting things. It'll return when it's nothing more to sort.

[ehughes]

  int *branch = right >= end | *left > *right ? left:right;

 sigh....

[Sal Ammoniac]

  int *branch = right >= end | *left > *right ? left:right;

 sigh....

That looks more like part of an entry in the Obfuscated C Contest.

[brucehoult]

  int *branch = right >= end | *left > *right ? left:right;

 sigh....

That looks more like part of an entry in the Obfuscated C Contest.

Simple C, unchanged in 40 years. Which part do you not approve of?

[Cerebus]

  int *branch = right >= end | *left > *right ? left:right;

 sigh....

That looks more like part of an entry in the Obfuscated C Contest.

Simple C, unchanged in 40 years. Which part do you not approve of?

For a start, it violates my rule that you shouldn't have to know, with certainty, the operator precedences to be able to understand what a line of code does. If you're going to write a line of code like that, at least throw some brackets in so that: 1) a human will understand it, 2) the compiler will do what you intend if you've mis-remembered an operator precedence.

Also, just on a correctness issue, what happens if the condition (right > end) is true? Hint: there's a reason C has a || operator as well as a | operator.

Moreover, if you're going to do pointer arithmetic, as you do two lines above, sprinkle a few sizeof()s around or your code will crash and burn hard on the first machine it hits that doesn't agree with your assumptions on word size (which in this case appears to be (sizeof(int) == 1)). Better still, don't do pointer arithmetic unless it is absolutely forced on you, I know of nothing that creates fragile code faster than using pointer arithmetic. This doesn't mean you can't pass pointers around, just use '&' and '[]' to safely do all the address manipulation on your behalf.

[NorthGuy]

Also, just on a correctness issue, what happens if the condition (right > end) is true? Hint: there's a reason C has a || operator as well as a | operator.

Since both operands are either 0 or 1, "|" will produce the same result as "||".

The distinction is that "||" creates a sequencing point, and if the operand on the left is "true", then the complier must not evaluate the operand on the right. With "|", the order of evaluation is not defined (determined by the compiler) and the compiler may decide to evaluate the operand on the right first. Should this happen, evaluation of "*right" may cause a crash.

[westfw]

There are some algorithms that become extremely cleanly expressed when you use recursion.  Anything based on trees or graphs, for example.

I "grew up" with factorial, Towers of Hanoi, and maybe sort, as example recursive jobs, and I never really understood what was the point.  Then, much more recently, I took a modern class in algorithms that covered tree algorithms (that didn't EXIST when I was in school!) and had one of those "ah hah!" moments where recursion suddenly made a lot more sense.

Now, most of us here are EE types and write pretty deeply embedded code.  In fact, we don't often come across cases that benefit much from the sort of algorithms that recursion makes easier - A typical microcontroller with 128k of RAM can bubble-sort or linear search any possibly-contained set of data in reasonable time.  Work on something like a packet router with tens of thousands of routes (and enough memory not to worry about THAT restriction), and you start to worry about finding those N*log(N) algorithms instead of the N² (or worse algorithm.)  And that "log(n)" part typically comes from something that can be implemented with recursion...  (after a ~35y career, I had the somewhat depressing realization that I had spent nearly all of it improving the implementation of algorithms, or finessing my way around them, rather than developing BETTER algorithms.  Not "Computer Science" at all, really...)  (Heh.  I took another class recently that pointed out  that using the simple recursive algorithm to generate tables of Fibonacci numbers or Factorials is particularly silly, because you're constantly re-calculating intermediate numbers that you've already calculated.)

Now, A well-designed embedded program will keep careful track of recursion depth and resource consumption.  Or use algorithms that are well bounded and understood.  (I used to like a recusive decimal output function, even on moderately small systems.  And using some form of recursion for parsing user input is very common...)

[brucehoult]

  int *branch = right >= end | *left > *right ? left:right;

 sigh....

That looks more like part of an entry in the Obfuscated C Contest.

Simple C, unchanged in 40 years. Which part do you not approve of?

For a start, it violates my rule that you shouldn't have to know, with certainty, the operator precedences to be able to understand what a line of code does. If you're going to write a line of code like that, at least throw some brackets in so that: 1) a human will understand it, 2) the compiler will do what you intend if you've mis-remembered an operator precedence.

I'd say something is pretty wrong with your understanding of C if you don't know that ?: is lower precedence than everything except assignment operators. C is the simplest language out there. Learn it!

Also, just on a correctness issue, what happens if the condition (right > end) is true? Hint: there's a reason C has a || operator as well as a | operator.

Yes, and the other version of the code a few lines below (which I didn't post) uses || and arrays. This version is to demonstrate that the speed is the same in either case.

Either | or || will work in this case, as there are no side effects, and in fact the compiler will freely convert between them depending on how cheap a conditional branch is, and whether the instruction set has a convenient "set boolean based on compare" instruction. As we already tested that left points inside the array, right can be no more than one past the end (and then only if the array has odd size). The caller makes sure the array is (at least) one bigger than actually required, so all is well.

Moreover, if you're going to do pointer arithmetic, as you do two lines above, sprinkle a few sizeof()s around or your code will crash and burn hard on the first machine it hits that doesn't agree with your assumptions on word size (which in this case appears to be (sizeof(int) == 1)).

You misunderstand C. Subtracting two pointers returns an integer of the number of *objects* between them (ints in this case) not the number of bytes between them. Adding an integer to a pointer multiplies the integer by the size of objects the pointer points to first.

The code is perfectly correct and safe C.

[brucehoult]

Now, A well-designed embedded program will keep careful track of recursion depth and resource consumption.  Or use algorithms that are well bounded and understood.  (I used to like a recusive decimal output function, even on moderately small systems.  And using some form of recursion for parsing user input is very common...)

Exactly!

And conversion between binary and decimal is a good example. You know how many bits are in your int, so you know how many decimal digits deep the maximum recursion can be. The alternative is to generate the digits in the wrong order and use a temporary array to store them, and then use an extra loop to print them in the correct order afterwards. Between the array and the code for the extra loop the recursive version is simpler and cleaner and the memory use is little different.

[brucehoult]

Moreover, if you're going to do pointer arithmetic, as you do two lines above, sprinkle a few sizeof()s around or your code will crash and burn hard on the first machine it hits that doesn't agree with your assumptions on word size (which in this case appears to be (sizeof(int) == 1)). Better still, don't do pointer arithmetic unless it is absolutely forced on you, I know of nothing that creates fragile code faster than using pointer arithmetic. This doesn't mean you can't pass pointers around, just use '&' and '[]' to safely do all the address manipulation on your behalf.

A lot of people seem not to be aware or the properties of C arrays and pointers.

If you have...

T arr[sz];
int i;

... then all the following mean *exactly* the same thing in C:

arr  ==  *(arr+i)  ==  *(i+arr)  ==  i[arr]

That last one is probably a shock to most people reading, but it's perfectly true.

And therefore, taking the address:

&arr  ==  &*(arr+i)  == arr+i  == i+arr  ==  &*(i+arr)  ==  &i[arr]

Doing &arr is no more and no less safe than arr+i no matter what the type T is.

The only time you have to or should muck about with sizeof() is if you've converted the T* to a char* for some reason (or no good reason).

[sasa]

A lot of people seem not to be aware or the properties of C arrays and pointers.
If you have...

I'm starting to have a headache here - from advanced algorithms and recursion you are back to explain elementary C stuff...  There is no point - if somebody do not like or do not understand the code, it is not obligated to use it.

The main point is that almost any solved non trivial problem can be solved in several different ways and in minimum and maximum predicted time/steps. If time is relatively small according to other tasks, it can be used algorithm which allow optimal solution.

[T3sl4co1l]

And conversion between binary and decimal is a good example. You know how many bits are in your int, so you know how many decimal digits deep the maximum recursion can be. The alternative is to generate the digits in the wrong order and use a temporary array to store them, and then use an extra loop to print them in the correct order afterwards. Between the array and the code for the extra loop the recursive version is simpler and cleaner and the memory use is little different.

If you're in assembler, you can even push/pop that "array" yourself (probably not needing any other stacks for storing registers during the loop).  Otherwise, the only sure way* to make the compiler emit push and pop is: call a function!

*Hmm, aside from asm() and compiler internals, is there anything else known to cause this?  Perhaps reserving a register for multiple variables somehow?  Certainly nothing target-independent?

Tim

[Cerebus]

For a start, it violates my rule that you shouldn't have to know, with certainty, the operator precedences to be able to understand what a line of code does. If you're going to write a line of code like that, at least throw some brackets in so that: 1) a human will understand it, 2) the compiler will do what you intend if you've mis-remembered an operator precedence.

I'd say something is pretty wrong with your understanding of C if you don't know that ?: is lower precedence than everything except assignment operators.

Oh, I know the precedence. You completely miss the point. It's about error-proneness and human readability. I think the point is quite clearly made above

C is the simplest language out there. Learn it!

I probably learned C before you were born, and certainly with enough background to know that it is not "the simplest language out there", for example LOGO and smalltalk-80 are much, much simpler. In 1985 or 1986 I wrote (in C as it happens) a trivial* smalltalk-80 compiler (that spat out smalltalk-80 bytecode) literally in a day; I imagine that I'd probably have still been working 3 months later if I'd set out to write any kind of C compiler instead.

I don't think there's much point in addressing the rest of your comments point by point. The fact that a handful of people recognised the problem from:

  int *branch = right >= end | *left > *right ? left:right;

 sigh....

would suggest to a humble man that there might be a well recognised problem here and something to learn. The fact that you, quite clearly, want to argue about it suggests that trying to get you to mend your ways is a pointless exercise. Code being nominally correct is not a complete and sufficient condition for it being good code, indeed nominally correct code can still be bad code. A nominally correctly assembled big-box flat pack table might well work, but will it still be around and functioning after 400 years of use and maintenance like a carpenter's well crafted table will? Home Depot or Chippendale**? It's your choice, but I know which I'd rather be.

*Trivial in the sense that it could only compile a single method at a time. It was part of a (later abandoned) effort to bootstrap a smalltalk-80 system from the PARC books.

**Feel free to substitute Charles Rennie Mackintosh or any other well known furniture maker to your personal taste. Personally I can't stand Chippendale but his is probably the best known name in furniture and hence a useful touchstone example.

[brucehoult]

I probably learned C before you were born

ahahahaha.

I was born well before BCPL was developed, let alone B or C.

example LOGO and smalltalk-80 are much, much simpler. In 1985 or 1986 I wrote (in C as it happens) a trivial* smalltalk-80 compiler (that spat out smalltalk-80 bytecode) literally in a day

LOGO and smalltalk are simple languages to use, but complex in the implementation. Converting smalltalk to bytecode is a trivial operation (as it is for Java too) -- all the complexity is in the interpreter.

I was programming in all three of the languages you mention well before 1985. In 1985 and 1986 I was employed full time programming in PL/I (and PostScript, which earned me considerable consulting income over the next 10 or 15 years) and wishing the machine in question supported C, which I'd already been using for a few years -- or better "C with Classes" but I wasn't able to get my hands on an implementation of that until Zortech in 1988, and then a cfront in 1989.

You appear to believe that because someone disagrees with you they are young and inexperienced.
What was that about "a humble man"?

[Cerebus]

You appear to believe that because someone disagrees with you they are young and inexperienced.
What was that about "a humble man"?

"Young and inexperienced" is a more charitable interpretation, in the absence of knowing your age, than would be "Is old enough that he ought to know better".

You've clearly been around as long as I have. How can you not have learned what I'm talking about? Surely you've seen enough disaster ridden code to recognise that style as dangerous?

[bd139]

Indeed. I wrote a C compiler when I was young. Universe ending paradox!

Incidentally, C is a horrible horrible language full of non determinism and stupidity ergo you can never be experienced enough not to be hurt by it occasionally.

[legacy]

Incidentally, C is a horrible horrible language full of non determinism and stupidity ergo you can never be experienced enough not to be hurt by it occasionally.

I agree!

[X]

While debugging some customer code in production last week that kept crashing, I came across a recursive function. While it wasn't the recursiveness in itself that caused the problem on its own, it exacerbated the problem (memory allocated but not released).

I could see why the programmer chose to use recursion, but to me it seemed like they'd used it "because you can" rather than for readability reasons. Had the programmer remembered to release all his initialised variables as they dropped out of scope I might have given him more credence. Those initialised heap variables were arrays of strings that never changed  so should've been constants anyway, and never used either heap or stack. (The heap grew to... wait for it... 50GB before the process broke.)

I think that in over 30 years I can count on the digits of one hand the number of times I've come across recursion used outside the classroom, and this was one of them. Most of those times have been when looking at the C runtime library, such as qsort.

I've used recursion a few times in ordinary C code (not embedded) only in situations where I can control the depth of the recursion to reasonable limits (eg. searching through a very small tree that I know will be very small). It often makes for a nice solution that is simple to implement, if you can control the depth and keep stack usage in check.

If a non-recursive solution proves to be only slightly more painful than a recursive solution (eg. DFS), I will endure the pain as the end-result will not require me to control the inputs as strictly, and will not use up a lot of stack space.

One trap people fall into is not cleaning up before exiting the function thinking "the OS will do it anyway!" or "memory is cheap let's waste it bro!" As the 50GB heap usage in your example demonstrates, this is highly necessary. Once a process of mine crashed having exceeded the allowable per-process limit set by the OS (1GB I think) because I forgot to free() in one small function that is called thousands of times.

Incidentally, C is a horrible horrible language full of non determinism and stupidity ergo you can never be experienced enough not to be hurt by it occasionally.

The biggest problem with C is the standards committee. They have enough rules to compare with the entire Australian federal tax legislation, and many of these C rules are vague enough as to require a Master's Degree to understand them. Many features (eg. variable length arrays in C11) are stupidly made optional. Many of the rules are "implementation-defined" and seem to defeat the purpose of having a standard in the first place. It is not a surprise some compilers can't implement all the features of C.

The second biggest problem is working on code that was written by developers who think C hasn't improved from the 1980s or refuse to use certain features (eg. postponed declarations, inline functions, stdint.h/stdbool.h etc) that would significantly improve the code just because Microsoft didn't support them until recently.

[Cerebus]

Indeed. I wrote a C compiler when I was young. Universe ending paradox!

Incidentally, C is a horrible horrible language full of non determinism and stupidity ergo you can never be experienced enough not to be hurt by it occasionally.

Can't argue with that, even though I probably write more C than everything else put together. I deeply mourn the loss, for all practical purposes, of Algol 68. Brian Kernighan said that some of the features of C were influenced by Algol 68, so why, oh why, did ":=" get abandoned in favour of "=" for assignment? The one C 'feature' that has bitten me more times than any other is accidentally typing something like

Code: [Select]

if (fred = bert) ...when I meant to type

Code: [Select]

if (fred == bert) ....

[aside] I was highly tempted, just for the obvious in joke, to create a second account under the name "bd140" and post the single and only message "I disagree with everything you've said, I think the exact opposite" as a comment to your message. For some reason, this idea hadn't occurred to me before today. Still, if I ever really disagree with you vehemently I can just threaten to walk over to my parts box and reach for the high voltage power supply.

[NorthGuy]

Back to the recursion.

There seems to be an opinion that there's a great value in tail recursion because it can be optimized by the compiler. And the other cases of recursion are "dangereous" and should be avoided.

I have opposite opinion. Tail recursion is a rudimentary form of recursion - mostly syntax than substance, and it relies on compiler optimization, which is undocumented feature that shouldn't be relied upon. Aside of that, recursion is very useful.

Really, if you're walking a linked list, why is the recursive walking:

Code: [Select]

void process_node(node_t *node) {
   if (node == NULL) return;
   do_something(node);
   process_node(node->next); // assuming compiler will optimize the tail call
}
is superior to a simple loop:

Code: [Select]

node_t *node = something;
while (node != NULL) {
   do_something(node);
   node = node->next;
}
?

There's really no difference, and there's no benefit of recursion because the recursive process doesn't use any memory and therefore can be easily re-written as a loop,

But recursion becomes really useful, not to mention very efficient, if there's a need to store something at every node. Why? Because it uses the stack memory as a storage. Without recursion, this memory would have to be somehow allocated/reserved.

For example, walking a tree (especially when you need to process children/siblings before the current node):

Code: [Select]

void process_node(node_t *node) {
   if (node == NULL) return;
   process_node(node->child); // process children
   process_node(node->next); // process siblings
   do_something(node); // process this node
}
Try to re-write this as a loop and you will see how useful the recursion is.

[bd139]

The second biggest problem is working on code that was written by developers who think C hasn't improved from the 1980s or refuse to use certain features (eg. postponed declarations, inline functions, stdint.h/stdbool.h etc) that would significantly improve the code just because Microsoft didn't support them until recently.

Those humans are what we refer to in the office as, and excuse the language, cunts. In context "Holy crap someone wrote DoSomethingEx(PARAM1_DEFAULT, PARAM2_DEFAULT, PARAM3_DEFAULT, &somethingAnnoying); ... cunt!"

Can't argue with that, even though I probably write more C than everything else put together. I deeply mourn the loss, for all practical purposes, of Algol 68. Brian Kernighan said that some of the features of C were influenced by Algol 68, so why, oh why, did ":=" get abandoned in favour of "=" for assignment? The one C 'feature' that has bitten me more times than any other is accidentally typing something like

Code: [Select]

if (fred = bert) ...when I meant to type

Code: [Select]

if (fred == bert) ....

Go is Algol 68 in a shirt and tie. The shirt has pizza stains down it but you still wear it in a nightclub because the lights are down. It's also an acknowledgement that C was a silly idea all along as it was written by two toked up hippies on an ASR33 and PDP8 trying to write games and accidentally ending up with an OS and compiler and now we need to be serious because the CVE list is make it look like it was a bad idea.

I hope they have "use after free" chiseled on their gravestones.

[aside] I was highly tempted, just for the obvious in joke, to create a second account under the name "bd140" and post the single and only message "I disagree with everything you've said, I think the exact opposite" as a comment to your message. For some reason, this idea hadn't occurred to me before today. Still, if I ever really disagree with you vehemently I can just threaten to walk over to my parts box and reach for the high voltage power supply.

If you were a BD140 I would have thought you'd be complementary 

[Sal Ammoniac]

Oh, I know the precedence. You completely miss the point. It's about error-proneness and human readability. I think the point is quite clearly made above

That particular line of code would not have made it past any code review I've ever been involved in. Our coding standards favor clear, easily understandable code over clever and/or complex code that tempts the precedence Gods.

[sasa]

That particular line of code would not have made it past any code review I've ever been involved in...

One notable benefit of the compact way of coding is to force compiler to make much more optimized code than usually. Otherwise, indeed they are mysterious ways how compiler will actually perform optimization. That could be crucial in speed critical parts of code, however most of the code should have to be clear, if used in large company with many employers.

[janoc]

If you have small enough N, it is enough even Bubble...

The only time I ever needed to sort something was when displaying a list of filenames, and then Bubble sort was plenty fast enough.

Ehm, try that with a directory containing a few thousands files. 

You may come to appreciate some other sorts than bubble sorts, which is pretty much the worst one in existence (most have a quadratic worst case, bubble sort is quadratic even in the average case).

[Mr. Scram]

I've used recursion for an Euclidean type algorithm without any trouble. I made sure to test how far I could take it before the program would throw a fit, and that was well beyond the realm of what it would ever be used for.

[janoc]

I have opposite opinion. Tail recursion is a rudimentary form of recursion - mostly syntax than substance, and it relies on compiler optimization, which is undocumented feature that shouldn't be relied upon. Aside of that, recursion is very useful.

Would disagree with that but then we would have to go into the theory of computability and formal reasoning about programs. In short, tail recursion allows to simplify reasoning about what the code does because such code is trivially mapped to mathematical induction. If you have arbitrary recursion, this doesn't work and you need to first massage the code to convert it to tail form (which isn't always possible).

Also the tail call optimization is certainly documented if the compiler/language supports it (both LLVM/CLANG and GCC do, for ex.). For GCC this has been around since 2002 or so, just don't forget to turn on -O2 optimization level (or higher).

Tail calls permit to eliminate the entire stack frame because the compiler knows that the variables stored there will not be used anymore (since the only thing following the tail call is return). This eliminates problems with overflowing stacks, for example. It is certainly not only syntactic sugar! Non-tail recursion cannot be optimized like this and you will blow out of RAM sooner or later, given sufficient amount of data. It is very rare that a recursive algorithm cannot be expressed in tail form, so I would say that a lot of people complaining about recursion don't use it properly.

And to add something to your comparison with iteration - another advantage of recursion is that there many many algorithms which can be naturally expressed as:

• Do something with the first/one/first few element(s)
• Apply this function to the rest

Processing lists, trees, graphs, sorting, merging, various filters, etc. - all of these things can be (and commonly are) naturally expressed in this way. If there is some recurrent math formula behind then recursion is a great tool, leading to natural implementation. Just make sure it finishes - there is a good rule of thumb for that: Something needs to decrease with every step.

[NorthGuy]

And to add something to your comparison with iteration - another advantage of recursion is that there many many algorithms which can be naturally expressed as:

• Do something with the first/one/first few element(s)
• Apply this function to the rest

Translating what you have into "machine" language, I would naturally do something like:

Code: [Select]

do_something(x[0]); // Do something with the first/one/first few element(s)
for (i = 1; i < n; i++) {
  do_something(x[i]); // Apply this function to the rest
}
or simply

Code: [Select]

for (i = 0; i < n; i++) {
  do_something(x[i]);
}
I don't see how recursion is "natural" here.

There's no reason to use recursion where it is not needed (e.g. where you necessarily want to use tail recursion because you feel it's cool). Similarly, there's no reason not to use recursion where the recursion helps (e.g. no reason to avoid recursion because you're scared of how dangerous it is). This is just as with everything else - forget the rules and use your brain cells instead.

[bd139]

Just to reply to a comment about tail recursion, this isn't represented in the machine as a recursion operation but a continuation via tail call optimisation which is a thoroughly different concept. It suits recursive algorithms nicely where the final call is the calling function. At that point you don't need to create a new stack frame and futz the stack. That's perfectly deterministic to optimise out. Hell if you have a test case you can even make sure it doesn't shit the stack. LLVM at least has a half decent optimiser that can actually handle this well  (unlike GCC which is a hairy testicle).

You C guys really need to go on a mental excursion and write some Haskell, Scheme or Erlang or something and come back having licked the toad of glory even if you never touch it again.

Also to note, the stack and stack frames are a compromise in the machine model which happens to leak into the language abstraction, not a required part of the machine or the language. There doesn't have to be turtles all the way down until they topple with a stack overflow; there can be one well defined turtle. Some embedded systems guys may recognise this if they have dirty assembly fingers. There was another thread on that where all the C programmers whinged about goto (or JMP as it used to be called)

[sasa]

If there is some recurrent math formula behind then recursion is a great tool, leading to natural implementation.

That is exactly where fresh university graduated youngsters may break they tooths when start to bite that simple challenge...

They may use blindly as an axiom that if recurrent math formula is defined in such matter, it is "natural" to do that in code. Certainly, that is not the general rule at all.

Take for instance continued fractions. Dealing with finite and infinite expression makes fundamental difference in approach for implementation - no recursion is necessary. Not a single computational process is infinite if approximate or accurate result is expected in reasonable time.

[Bruce Abbott]

But recursion becomes really useful, not to mention very efficient, if there's a need to store something at every node. Why? Because it uses the stack memory as a storage. Without recursion, this memory would have to be somehow allocated/reserved.

Stack is not allocated/reserved?

Using stack may be a more efficient use of memory if you have enough of it, but what if you don't? And how do you know that you have enough? Oh right - you just give your task plenty of stack, to (hopefully) ensure that it won't run out. So now all that memory isn't available to anything that can't go on the stack. How is that efficient?

[NorthGuy]

Using stack may be a more efficient use of memory if you have enough of it, but what if you don't? And how do you know that you have enough? Oh right - you just give your task plenty of stack, to (hopefully) ensure that it won't run out. So now all that memory isn't available to anything that can't go on the stack. How is that efficient?

Stack is the most efficient storage. Getting memory from the stack very quick and there's no gaps (so memory is not wasted). the memory is automatically freed when the function quits and is subsequently re-used.

How do you know how much is enough? You estimate. It is not very hard.

Typically, in the embedded app, all the unallocated memory goes to stack - no other use for it. If you don't have enough stack, you must conserve memory somehow or get a bigger part. Moving the memory from the stack to static allocation or to heap (if you have one) won't solve the problem.

[janoc]

I don't see how recursion is "natural" here.

Because you took a trivial example of an iteration over an array/list. Try something a bit more involved, such as searching for a given file in a directory hierarchy.

You can either futz with the stack by hand (in each directory push all subdirectories onto stack, compare files, if not found start popping subdirectories from the stack and repeating the procedure for each of them until the stack is empty) or you write a simple recursive function where you compare the files (the "first elements") and if the file isn't found you call the same procedure on each of the subdirectories (the "rest") ...

I dare to say that the recursive solution will be much shorter and more readable, plus you don't need to implement a stack data structure.

Same if you want to build an expression evaluator (e.g. for a calculator). You can do it with stack, but unless you are building an RPN calculator, it is not a particularly natural fit - the infix notation is more naturally represented as a tree and tree traversal is easier done recursively again.

There's no reason to use recursion where it is not needed (e.g. where you necessarily want to use tail recursion because you feel it's cool). Similarly, there's no reason not to use recursion where the recursion helps (e.g. no reason to avoid recursion because you're scared of how dangerous it is). This is just as with everything else - forget the rules and use your brain cells instead.

Sure, no dispute with that. I am merely pointing out that recursion is far from an useless concept that has no use in embedded programming.

[janoc]

Hell if you have a test case you can even make sure it doesn't shit the stack. LLVM at least has a half decent optimiser that can actually handle this well  (unlike GCC which is a hairy testicle).

GCC  had tail call optimization from before LLVM even existed. I am not going to claim to know which one performs better, but the feature is there since a long time.

You C guys really need to go on a mental excursion and write some Haskell, Scheme or Erlang or something and come back having licked the toad of glory even if you never touch it again.

This. I have started with imperative programming (Basic, Z80 assembly, Pascal, C/C++ ...) as most people but getting exposed to the ideas behind languages like Lisp or (more recently) Haskell certainly did make me a much better programmer. Not because I am trying to write Lisp/Haskell in every project but simply because it teaches techniques that are super useful even when writing assembly code or C. For example pure functions, writing code that doesn't do side effects -> super helpful when dealing with multithreaded code (if a code doesn't have internal state/side effects it is implicitly thread safe). Such code also tends to be easier to maintain, because its effects are easier to test and verify.

Or that tail recursion - it is usually taught as a concept with Scheme or Lisp but it is very useful even in C. Or declarative programming in the style of Prolog - again a concept that is very useful even if you never touch Prolog in your life.

Also to note, the stack and stack frames are a compromise in the machine model which happens to leak into the language abstraction, not a required part of the machine or the language. There doesn't have to be turtles all the way down until they topple with a stack overflow; there can be one well defined turtle. Some embedded systems guys may recognise this if they have dirty assembly fingers. There was another thread on that where all the C programmers whinged about goto (or JMP as it used to be called)

Yep. On the other hand, stack is pretty essential for implementing many things, such as function calls or interrupts. You can do without, but it is usually not fun. So it helps having support for it.

[NorthGuy]

I don't see how recursion is "natural" here.

Because you took a trivial example of an iteration over an array/list. Try something a bit more involved, such as searching for a given file in a directory hierarchy.

But searching the directory is not the case where the recursion cannot be removed through the tail call optimization. Here recursion greatly simplifies things.

At the same time, nearly any case where the recursion can be removed through the end call optimization will be more or less trivial. So, not much need for recursion in such cases.

This is exactly the distinction I wanted to make here:

Back to the recursion.

[bd139]

Also to note, the stack and stack frames are a compromise in the machine model which happens to leak into the language abstraction, not a required part of the machine or the language. There doesn't have to be turtles all the way down until they topple with a stack overflow; there can be one well defined turtle. Some embedded systems guys may recognise this if they have dirty assembly fingers. There was another thread on that where all the C programmers whinged about goto (or JMP as it used to be called)

Yep. On the other hand, stack is pretty essential for implementing many things, such as function calls or interrupts. You can do without, but it is usually not fun. So it helps having support for it.

As an experiment, I wrote a code generator (compiler is a bit too advanced a word!) for the pic16 architecture around 2000 that used coroutines for multi tasking and multi threading. It had a bastardisation of basic and pascal as a language. I got bored of it and never finished it but the approach is definitely viable and not terribly inflexible. If you have a complex system, you will have hundreds of coroutines though which makes a debugging nightmare. Synchronisation was a bitch as well.

[westfw]

Quote from: brucehoult on Yesterday at 11:11:51 PM>Quote from: westfw on Yesterday at 09:17:57 PM

I used to like a recusive decimal output function, even on moderately small systems.

Between the array and the code for the extra loop the recursive version is simpler and cleaner and the memory use is little different.


Actually, the memory use is a little depressing on most modern processors.  The "temporary array" would require N bytes for an N digit number.  A typical 32bit CPU will required at least 8*N bytes of stack space: word-wide pushes of each digit plus word-wide pushes of the PC for each recursive call.  And it's harder to add formatting to the recursive version.
But it is cute and simple for basic conversion.  (OTTH a typical 32bit CPU will usually have several KBytes (or much more) of stack, so...)

[hamster_nz]

Actually, the memory use is a little depressing on most modern processors.  The "temporary array" would require N bytes for an N digit number.  A typical 32bit CPU will required at least 8*N bytes of stack space: word-wide pushes of each digit plus word-wide pushes of the PC for each recursive call.  And it's harder to add formatting to the recursive version.
But it is cute and simple for basic conversion.  (OTTH a typical 32bit CPU will usually have several KBytes (or much more) of stack, so...)

You can usually add saving the base pointer to that stack too, so make that 12*N - so that is more memory for one level pf recursion than it takes to buffer the the entire output.

More instructions to make the new stack frame, more time....

Suddenly

Code: [Select]

void print_dec(int n) {
  int i;
  unsigned int u;
  char digits[10];
  if(n < 0) {
    u = -n;
    putchar('-');
  } else {
    u = n;
  }

  for(i = 0; i < 10; i++) {
    digits[9-i] = u%10+'0';
    u/=10;
  }

  for(i = 0; i < 9; i++) {
    if(digits[i] != '0')
      break;
  }

  for(; i < 10; i++) {
    putchar(digits[i]);
  }
}
isn't looking so terrible.

[brucehoult]

Actually, the memory use is a little depressing on most modern processors.  The "temporary array" would require N bytes for an N digit number.  A typical 32bit CPU will required at least 8*N bytes of stack space: word-wide pushes of each digit plus word-wide pushes of the PC for each recursive call.  And it's harder to add formatting to the recursive version.
But it is cute and simple for basic conversion.  (OTTH a typical 32bit CPU will usually have several KBytes (or much more) of stack, so...)

You can usually add saving the base pointer to that stack too, so make that 12*N - so that is more memory for one level pf recursion than it takes to buffer the the entire output.

More instructions to make the new stack frame, more time....

Suddenly

Code: [Select]

void print_dec(int n) {
  int i;
  unsigned int u;
  char digits[10];
  if(n < 0) {
    u = -n;
    putchar('-');
  } else {
    u = n;
  }

  for(i = 0; i < 10; i++) {
    digits[9-i] = u%10+'0';
    u/=10;
  }

  for(i = 0; i < 9; i++) {
    if(digits[i] != '0')
      break;
  }

  for(; i < 10; i++) {
    putchar(digits[i]);
  }
}
isn't looking so terrible.

Let's try, shall we?

Using arm-linux-gnueabihf-gcc 5.4.0 20160609 compiling for ARMv7 Thumb2 with -Os (what I almost always use for everything) your code compiles to 140 bytes of code and uses 20 bytes of stack, for 160 total.

My recursive code (below) compiles to 52 bytes of code and uses 8 bytes of stack per digit printed, for a maximum of 80 bytes of stack. That's 132 bytes total.

My code+stack is less than your code! I need 60 bytes more of stack than you do.

Incidentally, both versions happen to use one 2-byte NOP for alignment...

I've tested both versions against printf on x86 for all 2^32 input values (takes about 5 min). All ok.

Code: [Select]

void print_dec(int n) {
    unsigned u = n;
    if (n < 0) {
        putchar('-');
        u = -n;
    }
    unsigned d = u/10, ch = u - d*10 + '0';
    if (d != 0) print_dec(d);
    putchar(ch);
}


Code: [Select]

00000000 <print_dec>:
   0: b510      push {r4, lr}
   2: 1e04      subs r4, r0, #0
   4: da03      bge.n e <print_dec+0xe>
   6: 202d      movs r0, #45 ; 0x2d
   8: 4264      negs r4, r4
   a: f7ff fffe bl 0 <putchar>
   e: 4a08      ldr r2, [pc, #32] ; (30 <print_dec+0x30>)
  10: fba4 2302 umull r2, r3, r4, r2
  14: 3430      adds r4, #48 ; 0x30
  16: 08d8      lsrs r0, r3, #3
  18: 230a      movs r3, #10
  1a: fb03 4410 mls r4, r3, r0, r4
  1e: b108      cbz r0, 6 <print_dec+0x6>
  20: f7ff fffe bl 0 <print_dec>
  24: 4620      mov r0, r4
  26: e8bd 4010 ldmia.w sp!, {r4, lr}
  2a: f7ff bffe b.w 0 <putchar>
  2e: bf00      nop
  30: cccccccd .word 0xcccccccd


[brucehoult]

Just for yuks I tried the same code on 32 bit RISCV. It compiles to 66 bytes of code. Unfortunately, the ABI says the stack pointer must always be 16 byte aligned, so it uses 16 bytes per level or 160 maximum even though it's storing less data than that. So my worst case total is 226 bytes of code+stack.

Using riscv32-unknown-elf-gcc 6.1.0 with -Os

Your function compiles to 146 bytes of code, and uses 32 bytes of stack, total 178 bytes.

Code: [Select]

00010222 <print_dec>:
   10222:       1141                    addi    sp,sp,-16
   10224:       c422                    sw      s0,8(sp)
   10226:       c226                    sw      s1,4(sp)
   10228:       c606                    sw      ra,12(sp)
   1022a:       842a                    mv      s0,a0
   1022c:       00055a63                bgez    a0,10240 <print_dec+0x1e>
   10230:       8581a503                lw      a0,-1960(gp) # 1b910 <_impure_ptr>
   10234:       02d00593                li      a1,45
   10238:       40800433                neg     s0,s0
   1023c:       4510                    lw      a2,8(a0)
   1023e:       3f55                    jal     101f2 <__sputc_r>
   10240:       45a9                    li      a1,10
   10242:       02b45533                divu    a0,s0,a1
   10246:       02b47433                remu    s0,s0,a1
   1024a:       03040413                addi    s0,s0,48
   1024e:       c111                    beqz    a0,10252 <print_dec+0x30>
   10250:       3fc9                    jal     10222 <print_dec>
   10252:       8581a503                lw      a0,-1960(gp) # 1b910 <_impure_ptr>
   10256:       85a2                    mv      a1,s0
   10258:       40b2                    lw      ra,12(sp)
   1025a:       4422                    lw      s0,8(sp)
   1025c:       4492                    lw      s1,4(sp)
   1025e:       4510                    lw      a2,8(a0)
   10260:       0141                    addi    sp,sp,16
   10262:       bf41                    j       101f2 <__sputc_r>

One reason for the 14 bytes more of code is this toolchain inlined putchar to putc, which needs to load stdout from a global and then pass it. I didn't look closely enough to figure it out, but I think that might also be the reason for saving three registers not just two (not that it makes any difference with mandated 16 byte alignment)

[hamster_nz]

Let's try, shall we?

If you are not adverse to 'compact & unreadable' code this is most likely the same size as the recursive code, and most likely quicker too - but fudging ugly:

Code: [Select]

void print_dec_2(int n) {
  unsigned int u = n, i = 0;
  char digits[10];
  if(n < 0) {
    u = -u;
    putchar('-');
  }

  do {
    unsigned int t = u/10;
    digits[i++] = u-t*10;
    u            = t;
  } while(i<10 && u != 0);

  while(i) {
    putchar(digits[--i]+'0');
  }
}

It could be made smaller by removing the "i<10 &&" test, which traps overflows if ints need greater than  10 characters - e.g. a 64 bit int - but better safe than sorry.

[brucehoult]

Let's try, shall we?

If you are not adverse to 'compact & unreadable' code this is most likely the same size as the recursive code, and most likely quicker too - but fudging ugly:

Code: [Select]

void print_dec_2(int n) {
  unsigned int u = n, i = 0;
  char digits[10];
  if(n < 0) {
    u = -u;
    putchar('-');
  }

  do {
    unsigned int t = u/10;
    digits[i++] = u-t*10;
    u            = t;
  } while(i<10 && u != 0);

  while(i) {
    putchar(digits[--i]+'0');
  }
}

It could be made smaller by removing the "i<10 &&" test, which traps overflows if ints need greater than  10 characters - e.g. a 64 bit int - but better safe than sorry.

Congratulations, that's better at 96 bytes of code only 44 more than the recursive version. I took out the i<10 test as that's really better done at compile time with a test on sizeof(int)*CHAR_BIT or UINT_MAX or some such.

I do agree that's less easily understandable than the recursive version, but for me at least it's much more quickly understandable than your first version!

Code: [Select]

00000000 <print_dec_2>:
   0: b57f      push {r0, r1, r2, r3, r4, r5, r6, lr}
   2: 1e04      subs r4, r0, #0
   4: 4b14      ldr r3, [pc, #80] ; (58 <print_dec_2+0x58>)
   6: 681a      ldr r2, [r3, #0]
   8: 461e      mov r6, r3
   a: 9203      str r2, [sp, #12]
   c: da03      bge.n 16 <print_dec_2+0x16>
   e: 202d      movs r0, #45 ; 0x2d
  10: 4264      negs r4, r4
  12: f7ff fffe bl 0 <putchar>
  16: 4811      ldr r0, [pc, #68] ; (5c <print_dec_2+0x5c>)
  18: 2500      movs r5, #0
  1a: fba4 2300 umull r2, r3, r4, r0
  1e: 3501      adds r5, #1
  20: eb0d 0205 add.w r2, sp, r5
  24: 08db      lsrs r3, r3, #3
  26: eb03 0183 add.w r1, r3, r3, lsl #2
  2a: eba4 0441 sub.w r4, r4, r1, lsl #1
  2e: f802 4c01 strb.w r4, [r2, #-1]
  32: 461c      mov r4, r3
  34: 2b00      cmp r3, #0
  36: d1f0      bne.n 1a <print_dec_2+0x1a>
  38: 3d01      subs r5, #1
  3a: f81d 0005 ldrb.w r0, [sp, r5]
  3e: 3030      adds r0, #48 ; 0x30
  40: f7ff fffe bl 0 <putchar>
  44: 2d00      cmp r5, #0
  46: d1f7      bne.n 38 <print_dec_2+0x38>
  48: 9a03      ldr r2, [sp, #12]
  4a: 6833      ldr r3, [r6, #0]
  4c: 429a      cmp r2, r3
  4e: d001      beq.n 54 <print_dec_2+0x54>
  50: f7ff fffe bl 0 <__stack_chk_fail>
  54: b004      add sp, #16
  56: bd70      pop {r4, r5, r6, pc}
  58: 00000000 .word 0x00000000
  5c: cccccccd .word 0xcccccccd


[bd139]

MY EYES!!! 

[sasa]

My recursive code (below) compiles to 52 bytes of code and uses 8 bytes of stack per digit printed, for a maximum of 80 bytes of stack. That's 132 bytes total.

Code: [Select]

void print_dec(int n) {
    unsigned u = n;
    if (n < 0) {
        putchar('-');
        u = -n;
    }
    unsigned d = u/10, ch = u - d*10 + '0';
    if (d != 0) print_dec(d);
    putchar(ch);
}
...

This is as well proper example why should not force recursion even that is "naturally" obvious.

1. You always send unsigned value in every call but first time. Internal conversion from signed to unsigned all the time.
2. You always check value is negative. As known from point 1, that is possible only once. Lost time for useless check.
3. Every recursion put on stack all variables. You spend more of the memory

Not only it waste resources, but it is as well extremely slow. Printing on screen or file is anyway slow, but try to convert millions of numbers to memory stream and you will notice difference.

Connected example: "Print reversed entered text and check it is a palindrome. Naturally, everybody will put a finger on last letter and start to copy each letter from right to the  left. No recursion! It is the same principle with resulted string from converting number to string, thus recursion is only more complicated thing.

Challenge 2 (MCU related): "Assume there is no memory for additional temporary string nor stack for recursion. Convert integer and send result through serial port."

I will immediately reject every youngster application for the job if fail to see solution in 1 second. As well, the best for him and any company is that burn his diploma out...

[brucehoult]

My recursive code (below) compiles to 52 bytes of code and uses 8 bytes of stack per digit printed, for a maximum of 80 bytes of stack. That's 132 bytes total.

Code: [Select]

void print_dec(int n) {
    unsigned u = n;
    if (n < 0) {
        putchar('-');
        u = -n;
    }
    unsigned d = u/10, ch = u - d*10 + '0';
    if (d != 0) print_dec(d);
    putchar(ch);
}
...

This is as well proper example why should not force recursion even that is "naturally" obvious.

1. You always send unsigned value in every call but first time. Internal conversion from signed to unsigned all the time.
2. You always check value is negative. As known from point 1, that is possible only once. Lost time for useless check.
3. Every recursion put on stack all variables. You spend more of the memory

Not only it waste resources, but it is as well extremely slow. Printing on screen or file is anyway slow, but try to convert millions of numbers to memory stream and you will notice difference.

You're looking at the trees and missing the forest!

I'm fully aware of your three points. They make no difference. Try it!

Code: [Select]

#define N 10000000

char buf[N*24]; // more than enough
char *p = buf;

__attribute__ ((noinline))
void myputchar(char ch) {
  *p++ = ch;
}

void print_dec(int n) {
  unsigned u = n;
  if (n < 0) {
    myputchar('-');
    u = -n;
  }
  unsigned d = u/10, ch = u - d*10 + '0';
  if (d != 0) print_dec(d);
  myputchar(ch);
}

int main() {
  for (int i=-N; i<=N; ++i) print_dec(i);
  return 0;
}

On a Raspberry Pi 3, compiled gcc -std=c99 -Os -mthumb -march=armv7

real   0m5.996s
user   0m5.680s
sys   0m0.310s

With hamster_nz's most recent code substituted:

real   0m6.312s
user   0m6.020s
sys   0m0.290s

Whose code is faster?

There are a lot of people here with assumptions and prejudices about what is fast, what is slow, what is efficient, what is wasteful.

It would be good to check them sometimes :-)

[brucehoult]

Btw, on an Odroid XU4 (2.0 GHz ARM A15):

hamster_nz's iterative code:

real   0m2.197s
user   0m1.860s
sys   0m0.325s

My recursive code:

real   0m2.128s
user   0m1.770s
sys   0m0.355s

Closer, but the recursive is faster.

On an i7 3770:

hamster_nz's iterative code:

real   0m0.898s
user   0m0.876s
sys   0m0.020s

My recursive code:

real   0m0.856s
user   0m0.848s
sys   0m0.008s

Close, but again recursive has the edge.

[Mechatrommer]

hmmm 4 pages about recursive function... here's my take... recursion is a tool. if you think you need it, then you use it. if you think you dont, then dont forbid others from using it... if you are taboo about recursion, you can replace recursive function with few (2, 3 or 4) functions that can emulate recursion... but by using the recursive tool you need to be aware of the pros and cons...

recursive function pros:
1) simpler code, hence managing and understanding it will be alot easier, hence less prone to logic/semantics error. hence in accordance to kiss principle.

cons:
1) slower execution due to multiple self function calls (can be hundreds of recursive function calls) which in effect will execute housekeeping job a normal program did when jumping (calling) another (modular) function, such as preparing stack and pointers to arguments etc.
2) require deep stack memory space to store return points and local variables. a big no no to limited resource mcu..

with non-recursive functions, the pro and cons is the other way around except con #1 because they can still call hundreds of non-recursive function calls. more difficult to maintain, less readable etc, but requiring close to nothing stack space.

anyway. i cared to reply just because i see missing option in the polls. i want to vote... use recursion depending on the need or when appropriate, there should be no definable time limit where you should use or not use recursion. but its not in the poll list... recursion is a tool, understand it and learn its drawback is the way to go. speculating without really understanding it is a complete waste of time, much like what usually happened in religious discussions, you need to understand your enemy to love or hate them in the right way. imho...

[NorthGuy]

Whose code is faster?

There are a lot of people here with assumptions and prejudices about what is fast, what is slow, what is efficient, what is wasteful.

It would be good to check them sometimes :-)

To be fair, your test does not really test what you want to test. The hamster_nz's code uses "%" operation. The compiler (it's the same GCC everywhere, right?) implements it as a division. In your code, the compiler replaces division with multiplication, which makes hamster_nz's code way slower compared to yours.

If you want a fair comparison, take your code, convert it into non-recursive version without touching anything else, then do the tests.

[Cerebus]

The hamster_nz's code uses "%" operation. The compiler (it's the same GCC everywhere, right?) implements it as a division. In your code, the compiler replaces division with multiplication, which makes hamster_nz's code way slower compared to yours.

I just thought it is worth noting that, at some levels of optimization, GCC will do strength reduction on expensive operations with constants (e.g. '% 8' ==> ' & 0x7'), but it clearly hasn't here (I'm assuming, I haven't bothered to read the assembler).

[NorthGuy]

2) require deep stack memory space to store return points and local variables. a big no no to limited resource mcu..

This is not necessarily true.

Take for example, PIC16 - 16-level deep hardware call stack, very small memory. Seems like it would be stupid to use recursion. XC8 doesn't even support recursion with default settings.

But, on the other hand, you have very small memory. How much data can you really fit into 1024 bytes? When your data is so small, its processing is unlikely to require huge recursion depth. May be you'll need 5-7 levels. Compared to this, the 16-level deep stack looks quite adequate.

[Bruce Abbott]

your code compiles to 140 bytes of code and uses 20 bytes of stack, for 160 total.

My recursive code (below) compiles to 52 bytes of code and uses 8 bytes of stack per digit printed, for a maximum of 80 bytes of stack...

I need 60 bytes more of stack than you do.

Or to put it another way, you need 4 times more stack than he does. But this is a fairly trivial example. How does it scale up? Who's stack will blow out first?

Most MCUs have a lot more ROM than RAM, and many have even more limited stack space.  But hey, just because this is the Microcontroller & FPGA forum doesn't mean...

On an i7 3770:

hamster_nz's iterative code:

real   0m0.898s
user   0m0.876s
sys   0m0.020s

My recursive code:

real   0m0.856s
user   0m0.848s
sys   0m0.008s

Close, but again recursive has the edge.

... that you can't try to win the argument by throwing an i7 at it!

[sasa]

You're looking at the trees and missing the forest!
...

There are a lot of people here with assumptions and prejudices about what is fast, what is slow, what is efficient, what is wasteful.

It would be good to check them sometimes :-)

Not sure what you are talking about. My attitude about recursion you can read at end of page 1 of this thread.

With 30+ years of professional experience, everybody have his own attitude about everything, especially in his own profession. But I'm the liberal one in using different methods and different solutions in different situations, as long it is the most suitable way - I do not force either as the best a priori motivated by some subjective reasons.

If this is only an exercise to prove that everything can be transformed to recursion, yes, it can. But the question is (looking the whole picture) is it the most suitable solution?

[Mechatrommer]

2) require deep stack memory space to store return points and local variables. a big no no to limited resource mcu..

This is not necessarily true.

Take for example, PIC16 - 16-level deep hardware call stack, very small memory. Seems like it would be stupid to use recursion. XC8 doesn't even support recursion with default settings.

But, on the other hand, you have very small memory. How much data can you really fit into 1024 bytes? When your data is so small, its processing is unlikely to require huge recursion depth. May be you'll need 5-7 levels. Compared to this, the 16-level deep stack looks quite adequate.

if your recursive function doesnt store any local variables (i cant think of any recursive function that doesnt need local/temporary variable(s)), then 16 deep calls (give or take) is feasible, but if the function store say 2 variables, then (16/3) deep calls is feasible, ymmv. unless of course if a compiler can do a nice trick of saving local variables in heap memory. yes my statement is not entirely true but i'm talking what is generally recursion is used for. i dont think i will have a need for recursion in 16 deep stack processor, even if i do, recursive function that i usually used will not be runable in such tiny system. more like only for few led blink and some simple arithmetics. recursion is usually used in more complex data structures / algorithm afaik, other than simplicity, will be also because of performance reason. if you only have 1024 items in a list (which as you said pic16 can maximally hold on to), i dont think linear search or O(n^2) bubblesort on 1-16MHz processor will give much impact on performance, so recursive binary search/ O(N.log(N)) sort will not be necessary imho, but... ymmv...

[brucehoult]

Whose code is faster?

There are a lot of people here with assumptions and prejudices about what is fast, what is slow, what is efficient, what is wasteful.

It would be good to check them sometimes :-)

To be fair, your test does not really test what you want to test. The hamster_nz's code uses "%" operation. The compiler (it's the same GCC everywhere, right?) implements it as a division. In your code, the compiler replaces division with multiplication, which makes hamster_nz's code way slower compared to yours.

If you want a fair comparison, take your code, convert it into non-recursive version without touching anything else, then do the tests.

Here we have yet another assumption confidently stated, without data to back it up. And, again, incorrectly.

Here is hamster_nz's code, compiled (you really could do this yourself in about 30 seconds, you know...):

Code: [Select]

00010418 <print_dec>:
   10418:       b57f            push    {r0, r1, r2, r3, r4, r5, r6, lr}
   1041a:       1e05            subs    r5, r0, #0
   1041c:       da03            bge.n   10426 <print_dec+0xe>
   1041e:       202d            movs    r0, #45 ; 0x2d
   10420:       426d            negs    r5, r5
   10422:       f7ff fff1       bl      10408 <myputchar>
   10426:       4a0f            ldr     r2, [pc, #60]   ; (10464 <print_dec+0x4c>)
   10428:       ae01            add     r6, sp, #4
   1042a:       2400            movs    r4, #0
   1042c:       fba5 0102       umull   r0, r1, r5, r2
   10430:       3401            adds    r4, #1
   10432:       2c0a            cmp     r4, #10
   10434:       ea4f 03d1       mov.w   r3, r1, lsr #3
   10438:       eb06 0104       add.w   r1, r6, r4
   1043c:       eb03 0083       add.w   r0, r3, r3, lsl #2
   10440:       eba5 0540       sub.w   r5, r5, r0, lsl #1
   10444:       f801 5c01       strb.w  r5, [r1, #-1]
   10448:       d002            beq.n   10450 <print_dec+0x38>
   1044a:       461d            mov     r5, r3
   1044c:       2b00            cmp     r3, #0
   1044e:       d1ed            bne.n   1042c <print_dec+0x14>
   10450:       3c01            subs    r4, #1
   10452:       5d30            ldrb    r0, [r6, r4]
   10454:       3030            adds    r0, #48 ; 0x30
   10456:       b2c0            uxtb    r0, r0
   10458:       f7ff ffd6       bl      10408 <myputchar>
   1045c:       2c00            cmp     r4, #0
   1045e:       d1f7            bne.n   10450 <print_dec+0x38>
   10460:       b004            add     sp, #16
   10462:       bd70            pop     {r4, r5, r6, pc}
   10464:       cccccccd        .word   0xcccccccd

Where is the division? There is none. The compiler implements divide/mod by 10 by multiplying by 0xcccccccd, exactly the same as in my code.

[NorthGuy]

Where is the division?

here:

Your function compiles to 146 bytes of code, and uses 32 bytes of stack, total 178 bytes.

Code: [Select]

00010222 <print_dec>:
   10222:       1141                    addi    sp,sp,-16
   10224:       c422                    sw      s0,8(sp)
   10226:       c226                    sw      s1,4(sp)
   10228:       c606                    sw      ra,12(sp)
   1022a:       842a                    mv      s0,a0
   1022c:       00055a63                bgez    a0,10240 <print_dec+0x1e>
   10230:       8581a503                lw      a0,-1960(gp) # 1b910 <_impure_ptr>
   10234:       02d00593                li      a1,45
   10238:       40800433                neg     s0,s0
   1023c:       4510                    lw      a2,8(a0)
   1023e:       3f55                    jal     101f2 <__sputc_r>
   10240:       45a9                    li      a1,10
   10242:       02b45533                divu    a0,s0,a1
   10246:       02b47433                remu    s0,s0,a1
   1024a:       03040413                addi    s0,s0,48
   1024e:       c111                    beqz    a0,10252 <print_dec+0x30>
   10250:       3fc9                    jal     10222 <print_dec>
   10252:       8581a503                lw      a0,-1960(gp) # 1b910 <_impure_ptr>
   10256:       85a2                    mv      a1,s0
   10258:       40b2                    lw      ra,12(sp)
   1025a:       4422                    lw      s0,8(sp)
   1025c:       4492                    lw      s1,4(sp)
   1025e:       4510                    lw      a2,8(a0)
   10260:       0141                    addi    sp,sp,16
   10262:       bf41                    j       101f2 <__sputc_r>


[brucehoult]

You're looking at the trees and missing the forest!
...

There are a lot of people here with assumptions and prejudices about what is fast, what is slow, what is efficient, what is wasteful.

It would be good to check them sometimes :-)

Not sure what you are talking about. My attitude about recursion you can read at end of page 1 of this thread.

With 30+ years of professional experience, everybody have his own attitude about everything, especially in his own profession.

Everyone is entitled to their own opinions, but not their own facts. I'm seeing a lot of opinions that recursive code is bigger and or slower than iterative code. I'm the *only* one here who is bothering to establish facts to back up my opinions, by actually compiling and running code -- the results of which have been (at least for this example) that the recursive code is both smaller and faster than the iterative code.

Twice smaller code for a little more stack usage is a good trade-off in most circumstances. Bigger code is sitting there 100% of the time, whether in RAM or flash/ROM. A few bytes of stack usage is temporary, and as long as you have it in the first place is shared with other code running before and afterwards.

[brucehoult]

Where is the division?

here:

Your function compiles to 146 bytes of code, and uses 32 bytes of stack, total 178 bytes.

Code: [Select]

00010222 <print_dec>:
   10222:       1141                    addi    sp,sp,-16
   10224:       c422                    sw      s0,8(sp)
   10226:       c226                    sw      s1,4(sp)
   10228:       c606                    sw      ra,12(sp)
   1022a:       842a                    mv      s0,a0
   1022c:       00055a63                bgez    a0,10240 <print_dec+0x1e>
   10230:       8581a503                lw      a0,-1960(gp) # 1b910 <_impure_ptr>
   10234:       02d00593                li      a1,45
   10238:       40800433                neg     s0,s0
   1023c:       4510                    lw      a2,8(a0)
   1023e:       3f55                    jal     101f2 <__sputc_r>
   10240:       45a9                    li      a1,10
   10242:       02b45533                divu    a0,s0,a1
   10246:       02b47433                remu    s0,s0,a1
   1024a:       03040413                addi    s0,s0,48
   1024e:       c111                    beqz    a0,10252 <print_dec+0x30>
   10250:       3fc9                    jal     10222 <print_dec>
   10252:       8581a503                lw      a0,-1960(gp) # 1b910 <_impure_ptr>
   10256:       85a2                    mv      a1,s0
   10258:       40b2                    lw      ra,12(sp)
   1025a:       4422                    lw      s0,8(sp)
   1025c:       4492                    lw      s1,4(sp)
   1025e:       4510                    lw      a2,8(a0)
   10260:       0141                    addi    sp,sp,16
   10262:       bf41                    j       101f2 <__sputc_r>


That's my code (compiled for RISC-V), not hamster_nz's code. You said " The hamster_nz's code uses "%" operation. The compiler (it's the same GCC everywhere, right?) implements it as a division. In your code, the compiler replaces division with multiplication, which makes hamster_nz's code way slower compared to yours."

The ARM compiler uses multiplication for both of our functions. The RISC-V compiler uses division for both of our functions.

[Cerebus]

Everyone is entitled to their own opinions, but not their own facts.

Whether that is true is a matter of opinion.

[Bruce Abbott]

This is not necessarily true.

Take for example, PIC16 - 16-level deep hardware call stack, very small memory. Seems like it would be stupid to use recursion. XC8 doesn't even support recursion with default settings.

PIC16 hardware stack is for return addresses only, you can't store data on it. Now you may be wondering - how does XC8 store local variables if it can't use the stack? It just puts them in fixed RAM locations. 'Local' doesn't have to mean 'stack'.

But, on the other hand, you have very small memory. How much data can you really fit into 1024 bytes? When your data is so small, its processing is unlikely to require huge recursion depth. May be you'll need 5-7 levels.

Modern PIC16F's have up to 4K RAM, and many low-end ARM MCUs have a similar amount (but use it far less efficiently). But so what? This small amount of RAM may be perfectly adequate, except perhaps for this one function. So let's say you can get 5-7 levels with recursion, or  20-30 without. If your application needs 20 levels...

Who am I kidding? If your code is too bloated you just use a more powerful chip! I hear Raspberry Pi is the minimum now...

[Mechatrommer]

Everyone is entitled to their own opinions, but not their own facts .... I'm the *only* one here who is bothering to establish facts to back up my opinions, by actually compiling and running code -- the results of which have been (at least for this example) that the recursive code is both smaller and faster than the iterative code.

you are not the *only* one in this *world*. take me as example.. is the *only* one that i know in at least 100km radius from where i'm sitting, who actually compiled, runned and in house performance tested code to choose which one will suit my need. long time ago, it is said quicksort (iirc) is the fastest sort, but when i coded, built and tested all, it turned out shellsort (gonnet baeza variant) is the fastest in my particular system and data set, so i still use it until today, no matter what the internet said... having said that... your fact is only applicable to your case only (machine, code and usage), but other people's fact might be different from yours.

[NorthGuy]

That's my code (compiled for RISC-V), not hamster_nz's code. You said " The hamster_nz's code uses "%" operation. The compiler (it's the same GCC everywhere, right?) implements it as a division. In your code, the compiler replaces division with multiplication, which makes hamster_nz's code way slower compared to yours."

Sorry. My bad. I assumed the code posted after the sentence "Your function compiles to 146 bytes of code" would be hamster_nz's code.

[brucehoult]

Everyone is entitled to their own opinions, but not their own facts .... I'm the *only* one here who is bothering to establish facts to back up my opinions, by actually compiling and running code -- the results of which have been (at least for this example) that the recursive code is both smaller and faster than the iterative code.

you are not the *only* one in this *world*. take me as example.. is the *only* one that i know in at least 100km radius from where i'm sitting, who actually compiled, runned and in house performance tested code to choose which one will suit my need. long time ago, it is said quicksort (iirc) is the fastest sort, but when i coded, built and tested all, it turned out shellsort (gonnet baeza variant) is the fastest in my particular system and data set, so i still use it until today, no matter what the internet said... having said that... your fact is only applicable to your case only (machine, code and usage), but other people's fact might be different from yours.

For this usage, of course.

Sasa said "Not only it [recursion] waste resources, but it is as well extremely slow. Printing on screen or file is anyway slow, but try to convert millions of numbers to memory stream and you will notice difference."

Absolutely correct about printing to screen or file ... the code speed is irrelevant.

So I made a test that did exactly what (s)he suggested: converted 10 million negative and 10 million positive numbers into a memory stream (array). Recursive was faster on everything from ARM A series through to i7.

Alas, you fundamentally can't run this test on a small PIC or AVR because it requires something around a 13 MB memory array.

OK, you could output always to the same small buffer. Pretty unrealistic, but it could be done.

Small PICs are fundamentally unsuited to running C code, and especially recursive code, so I accept that my version would probably suck there. The AVR on the other hand is perfectly fine for C and the recursive version should do well. I don't happen to have an AVR handy in Moscow -- mine are back in NZ. I could try it on the SiFive FE310 RISCV microcontroller board I have (reusing a small buffer, as there is only 16 KB RAM).

I'd expect recursive to be better on *any* ARM, from a 1980s Archimedes on, and certainly on anything from an ARM7TDMI and up.

[sasa]

Everyone is entitled to their own opinions, but not their own facts.

Not opinion, but attitude based on 30+ years experience. And the fact is that one methodology is not suitable in all cases.

At end, the only fair judges are customers. They want accurate, fast and stable application/project, making his main job easier or even possible. If they experiencing slowness, many bugs and crashes - your career is finished. I'm not talking about games or anything trivial, but about sensitive applications - one glitch may cost many people life, or millions Euro lost...

Thus, there is no place for vanity and experimentation - you have to use what is the most suitable, proved (certified) and passed  extreme testing before entire project get a green light for commercial use.

I'm seeing a lot of opinions that recursive code is bigger and or slower than iterative code. I'm the *only* one here who is bothering to establish facts to back up my opinions, by actually compiling and running code -- the results of which have been (at least for this example) that the recursive code is both smaller and faster than the iterative code.

Showing valid examples where recursion is necessary, more appropriate and more clear and no body will claim otherwise. Thus lies its magnificence and strength.

Factorial, Fibonacci numbers, continued fractions, converting integers to string and similar, etc, are just examples where recursion can be used, nothing else. Its iterative solutions are much stable and much faster, in a word much suitable solutions. That is not my opinion, but fact.

Twice smaller code for a little more stack usage is a good trade-off in most circumstances. Bigger code is sitting there 100% of the time, whether in RAM or flash/ROM. A few bytes of stack usage is temporary, and as long as you have it in the first place is shared with other code running before and afterwards.

No body will persuade me that trivial: code + stack push + recursive call is faster than code +loop jump. It is simply impossible. You are very well aware of that.

However, if we look at any "divide and conquer" sorting algorithm, we will clearly see that recursion is justified and have full sense - as result we have efficient, fast and clear code.

[brucehoult]

Everyone is entitled to their own opinions, but not their own facts.

Not opinion, but attitude based on 30+ years experience. And the fact is that one methodology is not suitable in all cases.

32.75 years *commercial* experience here, plus valuable experience as a student before that.

I certainly agree that one methodology is not suitable in all cases. That's why I choose the most suitable one, as appropriate.

I'm seeing a lot of opinions that recursive code is bigger and or slower than iterative code. I'm the *only* one here who is bothering to establish facts to back up my opinions, by actually compiling and running code -- the results of which have been (at least for this example) that the recursive code is both smaller and faster than the iterative code.

Showing valid examples where recursion is necessary, more appropriate and more clear and no body will claim otherwise. Thus lies its magnificence and strength.

Factorial, Fibonacci numbers, continued fractions, converting integers to string and similar, etc, are just examples where recursion can be used, nothing else. Its iterative solutions are much stable and much faster, in a word much suitable solutions. That is not my opinion, but fact.

No, it's opinion. I've demonstrated that the facts are otherwise, at least for converting integers to strings, on a range of machines. The recursive solution is smaller code and faster. If you dispute this, show me smaller and faster iterative code. It shouldn't be that hard. All my cards are on the table.

Twice smaller code for a little more stack usage is a good trade-off in most circumstances. Bigger code is sitting there 100% of the time, whether in RAM or flash/ROM. A few bytes of stack usage is temporary, and as long as you have it in the first place is shared with other code running before and afterwards.

No body will persuade me that trivial: [stack push + recursive call] is faster than [loop jump]. It is simply impossible. You are very well aware of that.

The examples I've posted here *demonstrate* the opposite is true. If you're not persuaded by demonstrations that you can easily reproduce yourself -- the essence of the scientific method -- then certainly nothing anyone says will correct your wrong opinions.

But consider this: it is not simply as you paint it. The iterative solutions are not just a loop jump. They have to save data into memory and retrieve it later, just as the recursive solution does. Worse, they require at *least* two loops instead of effectively one.

[NorthGuy]

The ARM compiler uses multiplication for both of our functions. The RISC-V compiler uses division for both of our functions.

I would suggest using this function for speed comparisons:

Code: [Select]

void print_dec(int n) {
  unsigned u, d;
  char ch, *p, buf[12];

  u = n;
  if (n < 0) {
    putchar('-');
    u = -n;
  }
 
  p = buf;
  *p++ = 0;

  while(1) {
    d = u/10;
    *p++ = u - d*10 + '0';
    if (u = d) continue;
    while (ch = *--p) putchar(ch);
    return;
  }
}
IMHO, it is most similar to yours, but doesn't use the recursion.

[sasa]

Sasa said "Not only it [recursion] waste resources, but it is as well extremely slow. Printing on screen or file is anyway slow, but try to convert millions of numbers to memory stream and you will notice difference."

Absolutely correct about printing to screen or file ... the code speed is irrelevant.

So I made a test that did exactly what (s)he suggested: converted 10 million negative and 10 million positive numbers into a memory stream (array). Recursive was faster on everything from ARM A series through to i7.

(It is he, as it is  in profile... Anyway...)

How you exactly provide these tests? Did you store random numbers in array then read it from it, used random integer function call before each call to test subject functions, or simply convert two constant 10 mil. times?

As well, testing environment is very important - ensure your main thread have the highest priority and if possible disable all background...

That, makes a big difference.

[brucehoult]

The ARM compiler uses multiplication for both of our functions. The RISC-V compiler uses division for both of our functions.

I would suggest using this function for speed comparisons:

Code: [Select]

void print_dec(int n) {
  unsigned u, d;
  char ch, *p, buf[12];

  u = n;
  if (n < 0) {
    putchar('-');
    u = -n;
  }
 
  p = buf;
  *p++ = 0;

  while(1) {
    d = u/10;
    *p++ = u - d*10 + '0';
    if (u = d) continue;
    while (ch = *--p) putchar(ch);
    return;
  }
}
IMHO, it is most similar to yours, but doesn't use the recursion.

Strange code.  Why not?

Code: [Select]

void print_dec(int n) {
  unsigned u, d;
  char ch, *p, buf[12];

  u = n;
  if (n < 0) {
    putchar('-');
    u = -n;
  }
 
  p = buf;
  *p++ = 0;

  do {
    d = u/10;
    *p++ = u - d*10 + '0';
  } while (u = d);
  while (ch = *--p) putchar(ch);
}

The Thumb2 code is 96 bytes long, the same as hamster_nz's 2nd try (compared to 52 bytes for mine):

Code: [Select]

00000000 <print_dec>:
   0: b57f      push {r0, r1, r2, r3, r4, r5, r6, lr}
   2: 1e04      subs r4, r0, #0
   4: 4b14      ldr r3, [pc, #80] ; (58 <print_dec+0x58>)
   6: 681a      ldr r2, [r3, #0]
   8: 461e      mov r6, r3
   a: 9203      str r2, [sp, #12]
   c: da03      bge.n 16 <print_dec+0x16>
   e: 202d      movs r0, #45 ; 0x2d
  10: 4264      negs r4, r4
  12: f7ff fffe bl 0 <putchar>
  16: 4911      ldr r1, [pc, #68] ; (5c <print_dec+0x5c>)
  18: f10d 0501 add.w r5, sp, #1
  1c: 2300      movs r3, #0
  1e: f88d 3000 strb.w r3, [sp]
  22: fba4 2301 umull r2, r3, r4, r1
  26: 3430      adds r4, #48 ; 0x30
  28: 08db      lsrs r3, r3, #3
  2a: eb03 0283 add.w r2, r3, r3, lsl #2
  2e: eba4 0442 sub.w r4, r4, r2, lsl #1
  32: f805 4b01 strb.w r4, [r5], #1
  36: 461c      mov r4, r3
  38: 2b00      cmp r3, #0
  3a: d1f2      bne.n 22 <print_dec+0x22>
  3c: f815 0d01 ldrb.w r0, [r5, #-1]!
  40: b110      cbz r0, 8 <putchar+0x8>
  42: f7ff fffe bl 0 <putchar>
  46: e7f9      b.n 3c <print_dec+0x3c>
  48: 9a03      ldr r2, [sp, #12]
  4a: 6833      ldr r3, [r6, #0]
  4c: 429a      cmp r2, r3
  4e: d001      beq.n 54 <print_dec+0x54>
  50: f7ff fffe bl 0 <__stack_chk_fail>
  54: b004      add sp, #16
  56: bd70      pop {r4, r5, r6, pc}
  58: 00000000 .word 0x00000000
  5c: cccccccd .word 0xcccccccd

I'll check the speed later when I 'm where my ARM boards are.

[brucehoult]

Sasa said "Not only it [recursion] waste resources, but it is as well extremely slow. Printing on screen or file is anyway slow, but try to convert millions of numbers to memory stream and you will notice difference."

Absolutely correct about printing to screen or file ... the code speed is irrelevant.

So I made a test that did exactly what (s)he suggested: converted 10 million negative and 10 million positive numbers into a memory stream (array). Recursive was faster on everything from ARM A series through to i7.

(It is he, as it is  in profile... Anyway...)

How you exactly provide these tests? Did you store random numbers in array then read it from it, used random integer function call before each call to test subject functions, or simply convert two constant 10 mil. times?

I posted the entire test framework source code here, along with the exact compile command used and compiler version. You can duplicate it yourself.

As well, testing environment is very important - ensure your main thread have the highest priority and if possible disable all background...

That, makes a big difference.

Y'know, my job is working on code performance optimisation for a major electronics company with one of the biggest market shares in phones.

I've got some idea how to compare different versions of code to see which one is best. And it all has to pass code review, often not only internally but also by engineers at Google (e.g. AOSP) or Microsoft (e.g. CoreCLR).

[janoc]

No body will persuade me that trivial: code + stack push + recursive call is faster than code +loop jump. It is simply impossible. You are very well aware of that.

You are forgetting that many modern compilers will do a tail call optimization and thus there is no stack push! (assuming arguments fit into registers) The entire recursive call is optimized away and replaced by a jump.

And brucehoult has demonstrated that even non tail-recursive function could be faster than iterative version - the overhead of the function call is simply less than the extra code that the non-recursive version needs.

Assumptions are dangerous.

(and excellent work, brucehoult  )

[brucehoult]

The ARM compiler uses multiplication for both of our functions. The RISC-V compiler uses division for both of our functions.

I would suggest using this function for speed comparisons:

Code: [Select]

void print_dec(int n) {
  unsigned u, d;
  char ch, *p, buf[12];

  u = n;
  if (n < 0) {
    putchar('-');
    u = -n;
  }
 
  p = buf;
  *p++ = 0;

  while(1) {
    d = u/10;
    *p++ = u - d*10 + '0';
    if (u = d) continue;
    while (ch = *--p) putchar(ch);
    return;
  }
}

IMHO, it is most similar to yours, but doesn't use the recursion.

Congratulations! Comes in almost exactly the same as the recursive one.

Yours (median of five runs)

real   0m5.489s
user   0m5.220s
sys   0m0.260s

vs mine (likewise)

real   0m5.472s
user   0m5.170s
sys   0m0.290s

I'd say it's too close to call. We're down to experimental error.

Your compiled code is still 1.85x bigger than mine :-)

[sasa]

I posted the entire test framework source code here, along with the exact compile command used and compiler version. You can duplicate it yourself.
..
Y'know, my job is working on code performance optimisation for a major electronics company with one of the biggest market shares in phones.

OK, I accept the challenge.  One part of my job is to make source code optimization for some critical low level functions and algorithms. And I do not rely too much on compiler's optimization, as I use the same code almost unchanged on many platforms, including MCUs. So we will see...

I suggest following:

1. To change function according to C itoc function with one change

char *itoc_contester_version(int n, char *s) {

s - pointer to the first resulting character

Resulting pointer to the null-terminated string, pointing exactly on the last, null-terminator that will help to easy continue storing next converted number

It is assumed result is in decimal  base

2. To avoid any compiler/platform specific code, pure C.

BTW. NorthGuy is on the right track - using pointer's arithmetic is the key.

[hamster_nz]

You're looking at the trees and missing the forest!
...

There are a lot of people here with assumptions and prejudices about what is fast, what is slow, what is efficient, what is wasteful.

It would be good to check them sometimes :-)

Not sure what you are talking about. My attitude about recursion you can read at end of page 1 of this thread.

With 30+ years of professional experience, everybody have his own attitude about everything, especially in his own profession.

Everyone is entitled to their own opinions, but not their own facts. I'm seeing a lot of opinions that recursive code is bigger and or slower than iterative code. I'm the *only* one here who is bothering to establish facts to back up my opinions, by actually compiling and running code -- the results of which have been (at least for this example) that the recursive code is both smaller and faster than the iterative code.

Twice smaller code for a little more stack usage is a good trade-off in most circumstances. Bigger code is sitting there 100% of the time, whether in RAM or flash/ROM. A few bytes of stack usage is temporary, and as long as you have it in the first place is shared with other code running before and afterwards.

The problem of "optimized" is a multi-dimensional one, code size, stack size, speed, power, target architecture, code maintainability.... the costs you put on these are weighted to favor the recursive solution, and every time somebody 'betters the recursive solution you move the goal posts.

We are talking about stack usage...

The goalpost change "But it is about total memory usage (code AND stack)!"

So we get something that is a dozen bytes more code, but a greater saving in stack, taking in it below the recursive solution

The goalpost move "But it is about speed"

Then the goalpost move "Code is more expensive than stack".  If I have an application that only uses a fraction of my ROM, then larger code costs nothing if performance is the key constraint.

Sure, recursion is a workable solution to the problem - it produces the correct output, but it is only optimal for the use case where it is optimal - it won't be the fastest if code size isn't a constraint, or use the least RAM if that is a constraint.

And even as a recursive function it is sub-optimal if you have to print both signed and unsigned values: For example, you could improve performance (measured by code size & speed) by splitting it into two functions, avoiding the sign test for each digit:

Code: [Select]

void print_unsigned(unsigned u)
    unsigned d = u/10, ch = u - d*10 + '0';
    if (d != 0) print_unsigned(d);
    putchar(ch);
}

void print_signed(int n) {
    unsigned u = n;
    if (n < 0) {
        putchar('-');
        print_unsigned((unsigned)(-n))
    } else {
        print_unsigned((unsigned)(n))
    }
}

How does recursion go if you want to include leading spaces, to keep it printing 11 characters for each number? 

[splin]

For comparison, the assembler version of print_dec() from "The Definitive Guide to ARM Cortex-M3 and Cortex-M4 Processors" by Joseph Yiu:

Code: [Select]

; PutDecLoop; Function to display Decimal value
;------------------------------------------------
PutDec FUNCTION
; Subroutine to display register value in decimal
; Input R0 = value to be displayed.
; Since it is 32 bit, the maximum number of character
; in decimal format, including null termination is 11
; According AAPCS, a function can change R0-R3, R12
; So we use these registers for processing.
; R0 - Input value
; R1 - Divide value (10)
; R2 - Divide result
; R3 - Remainder
; R12- Text buffer pointer

        PUSH {R4, LR}           ; Save register values
        MOV  R12, SP            ; Copy current Stack Pointer to R12
        SUB  SP, SP, #12        ; Reserved 12 bytes as text buffer
        MOVS R1, #0             ; Null character
        STRB R1,[R12, #-1]!     ; Put a null character at end of text buffer
                                ; buffer,pre-indexed
        MOVS R1, #10            ; Set divide value
PutDecLoop
        UDIV R2, R0, R1         ; R2 = R0 / 10 = divide result
        MUL  R4, R2, R1         ; R4 = R2 * 10 = Value - remainder (multiple of 10)
        SUB  R3, R0, R4         ; R3 = R0 - (R2 * 10) = remainder
        ADDS R3, #'0'           ; convert to ASCII (R3 can only be 0-9)
        STRB R3,[R12, #-1]!     ; Put ascii character in text buffer
                                ; pre-indexed
        MOVS R0, R2             ; Set R0 = Divide result and set Z flag if R2=0
        BNE PutDecLoop          ; If R0(R2) is already 0, then there
                                ; is no more digit
        MOV  R0, R12            ; Put R0 to starting location of text
                                ; buffer
        BL Puts                 ; Display the result using Puts
        ADD  SP, SP, #12        ; Restore stack location
        POP  {R4, PC}           ; Return
ENDFUNC


I reckon that the 17 instructions take 42 bytes and uses 12 bytes of stack +8 to save R4 and LR (but it doesn't handle negative numbers). He could have saved a few more bytes by using R3 rather than R12 and using R0 instead of R3. He could also have saved a few cycles by not saving LR and jumping to Puts() at the end of the function rather than calling it (after restoring registers and SP) - but that is perhaps going a step too far for most... 

Ok. the comments could have been a bit better, but I'm sure its not just me who doesn't find that very much harder to read and understand than the C version - but it would be harder to write (by me) not having much experience writing Cortex assembler. This isn't a thread about ARM assembler though so apologies for the diversion.

[EDIT] Detabbed code

[Mechatrommer]

You are forgetting that many modern compilers will do a tail call optimization and thus there is no stack push! (assuming arguments fit into registers) The entire recursive call is optimized away and replaced by a jump.

"assuming"? assuming or "hoping" compiler will do its magic is not a wise thing to do, from a programmer standpoint, imho... what if arguments are not fit in registers? "assuming" will create very minimal threat if you are working on a fixed familiar system everytime... but not when on many different systems...

[NorthGuy]

I'd say it's too close to call. We're down to experimental error.

Your compiled code is still 1.85x bigger than mine :-)

So true. But I think the comparison would better reflect the merits of recursion if you compiled it with -fno-stack-protector so that the code wouldn't be affected by stack protection paranoia.

Or, if you insist on stack protection, then you could compile both variants with -fstack-protector-all.

[sasa]

To whom it may concern,

I have briefly made this morning optimized version. I do not have a time currently to write much, some notes are in the code. I hope I did not miss to add someone code. Anyway, can easily added later and cleaned by anyone interested.

Results are made on old Intel Atom, Linux 64-bit, GCC 6.3.0. Clean environment (though, not enough) - only console and calculator, rest is closed, no mouse is moved and no key pressed. The first dummy test is performed, to avoid latency effect on ENTER press during starting application.

@ brucehoult
I did not made and corrections on your original code except inserted pointer to directly write data th the array and add null-terminator. I have added your modified function, similarly hamster_nz also noted.

• itoc_ref_1 - Your original code
  
  itoc_ref_2 - I have split signed and unsigned parts of your code and made some corrections - much faster.
  
  itoc_NorthGuy_1 - NorthGuy's iterative function. Fast, however continue and some other code make a problem to compiler to optimized it better
  
  itoc_sasa_1 - My almost top optimized iterative function. Still can be checked some variations which on this or  other platforms may work faster.
  

Attention: Look at your original code (ref_1) and notice that wrong type for ch and implicit conversion may cost you some large percentage of speed!

As notable from tables below, my function is notable faster, (see tables or test if it is hard to believe) when compiler use maximum optimization, in comparison to your original version. That  imply that is still possible to optimize this source code for this particular platform and compiler, however I currently I have no time for games....

Difference in size when compiled with maximum optimization is only dozen bytes, IIRC. Try any compiler level optimization and you will probably notice similar. Try it on embedded systems, as well.

I have implemented almost all I have commented before, on your recursive and my own iterative code.

I believe all parallels pro et contra for using some methods and techniques are cleared through this thread.

Default optimization:

Code: [Select]

gcc -o printdec printdec.c -Wall -pedantic-errors
itoc_ref_1      : 4254 ms
itoc_ref_1      : 4255 ms
itoc_ref_1      : 4254 ms
itoc_ref_2      : 4064 ms
itoc_ref_2      : 4062 ms
itoc_ref_2      : 4062 ms
itoc_NorthGuy_1 : 4246 ms
itoc_NorthGuy_1 : 4245 ms
itoc_NorthGuy_1 : 4248 ms
itoc_sasa_1     : 3731 ms
itoc_sasa_1     : 3730 ms
itoc_sasa_1     : 3731 ms
Maximum optimization:

Code: [Select]

gcc -o printdec printdec.c -Wall -pedantic-errors -O
itoc_ref_1      : 3279 ms
itoc_ref_1      : 3265 ms
itoc_ref_1      : 3270 ms
itoc_ref_2      : 2786 ms
itoc_ref_2      : 2784 ms
itoc_ref_2      : 2785 ms
itoc_NorthGuy_1 : 2789 ms
itoc_NorthGuy_1 : 2790 ms
itoc_NorthGuy_1 : 2789 ms
itoc_sasa_1     : 2237 ms
itoc_sasa_1     : 2238 ms
itoc_sasa_1     : 2239 ms

Compilable modified code is attached.

[westfw]

No body will persuade me that trivial: code + stack push + recursive call is faster than code +loop jump. It is simply impossible.

Well, perhaps more detailed analysis is in order.  Here's the meat of the recursive version of decout:

Code: [Select]

void decout(int n) {

{
  int rem = n % 10;   // extract the least significant digit of the number.
  n /= 10;             // remove that digit from the overall number
  if (n > 0) {         // If there are any more digits in the number
    decout(n);         //  Then print them first
  }
  putchar(rem + '0');  // Convert the digit to ascii and print
}

And one of the non-recursive versions (also trimmed):

Code: [Select]

void print_dec_2(int n) {
  do {
    unsigned int t = u/10;
    digits[i++] = u % 10;
    u = t;
  } while(i<10 && u != 0);

  while(i) {
    putchar(digits[--i]+'0');
  }
}

Notice that the recursive version does not contain ANY loops or any explicit stores.  Essentially, each loop iteration branch that needs to be done by the non-recursive version is replaced by a call or return (BL or pop of sp) (which takes the same time, probably), and each store/retrieval of a character to the buffer in non-recursive is replaced by a POP (which also takes the same time.)  The recursive version may lose a bit of time doing the sign check each time, and the non-recursive version may lose a bit by having to maintain its own counter or pointer, but at some fundamental level they are doing exactly the same thing - N multiplies/divides, M adds/subtracts, O loads and stores, and P branches.  As the assembly dumps show, the compiler optimizes the recursive version sufficiently that it does not need any "extra" data saved on the stack, other than the PCs and the extra bytes in each digit.

We're down to experimental error.

Indeed.  Thanks to Bruce for doing the grunt-work.  This is not supposed to show that recursion is always "better" in any way than an iterative method; but it DOES show that recursion is not necessarily extremely expensive, either.

You can usually add saving the base pointer to that stack too

Doesn't happen in this case.  Compilers have gotten very good at not creating "stack frames" when they're not needed, and CPU/ABI combinations have gotten pretty good at ensure that simple functions don't usually need them.

2. You always check value is negative.

I'll give you that one.  But this is a micro-optimization...

1. You always send unsigned value in every call but first time. Internal conversion from signed to unsigned all the time.

signed/unsigned is usually not an actual conversion, but more a signal to the compiler on how to treat condition flags.  So these "casts" don't actually add any instructions or execution time.

3. Every recursion put on stack all variables. You spend more of the memory

As shown above, in this example "all of the variables" consists only of the extracted digit, which you'd have to save somewhere anyway.

Code: [Select]

wrong type for ch and implicit conversion may cost you some large percentage of speed!Show me where in the assembly language, please (see (1) above.)   The use of int vs char for the individual digits is an "interesting" optimization - on most 8bit CPUs (maybe including x86), using char would be desirable to save registers and possible compute time in multiply/divide.  On most 32bit RISC CPUs (and ARM in particular), using "int" probably avoids un-needed "covert word to byte" instructions.


(There ought to be some "rule" that distinguishes between variables that would have to be saved anyway, and variables that are local (in a stack frame, or in registers that need saving) but not actually part of the "recursive context."  Functions that have much more local context than recursive context would be poor candidates for recursion.)

(It's worth noting that the analysis above loses validity on other CPUs, where "call" and "branch" do NOT have the same cost.  On bigger AVRs, call and return each take 4 cycles, and branches only 1 or 2.  OTOH, an AVR could store each digit in only a single byte on the stack, with the "push" being significantly cheaper than storing to local variables.)

The USUAL excuse for recursion is that it makes the code much simpler, more compact, and easier to understand at the SOURCE CODE level.  That's vaguely true in this example ("print the rest of the number, print the last digit" vs "extract all the digits and print them backwards"), and not really true at all for the factorial/fibonacci examples.  But it gets real obvious when trying to do trees or divide-and-conquer sort algorithms without recursion.  Towers of Hanoi is probably a good example - anyone want to turn this Hanoi code into an iterative version?

Code: [Select]

void hanoifun(int n, char fr, char tr, char ar)//fr=from rod,tr =to rod, ar=aux rod
{
    if (n == 1)
    {
        printf("\n Move disk 1 from rod %c to rod %c", fr, tr);
        return;
    }
    hanoifun(n-1, fr, ar, tr);
    printf("\n Move disk %d from rod %c to rod %c", n, fr, tr);
    hanoifun(n-1, ar, tr, fr);
}


[Siwastaja]

Twice smaller code for a little more stack usage is a good trade-off in most circumstances. Bigger code is sitting there 100% of the time, whether in RAM or flash/ROM. A few bytes of stack usage is temporary, and as long as you have it in the first place is shared with other code running before and afterwards.

What I encounter often when doing embedded is that I'm having shitloads of excess flash ROM, sitting there doing nothing, while the RAM is the bottleneck. It's not untypical to have 128k of flash for a 10k program, and only 4k of RAM with about 1k available for stack.

This strange balance is because flash rom is cheap, so why not sell it so that it's definitely not running out; while SRAM is freaking expensive and dominating the MCU price.

Actually, I have never ran out of flash rom in any MCU project, which is a bit surprising, since I've been doing quite a lot of things. But RAM is scarce.

Usually (but not always), the importance ends up in this order in my embedded projects:
- RAM usage
- Speed
- Program memory usage

So, to calculate relevant "figure of merits", I'd introduce some heavy coefficients for the cost of stack bytes vs. the cost of program memory bytes, like 10x.

Your mileage may vary.

[brucehoult]

Twice smaller code for a little more stack usage is a good trade-off in most circumstances. Bigger code is sitting there 100% of the time, whether in RAM or flash/ROM. A few bytes of stack usage is temporary, and as long as you have it in the first place is shared with other code running before and afterwards.

What I encounter often when doing embedded is that I'm having shitloads of excess flash ROM, sitting there doing nothing, while the RAM is the bottleneck. It's not untypical to have 128k of flash for a 10k program, and only 4k of RAM with about 1k available for stack.

This strange balance is because flash rom is cheap, so why not sell it so that it's definitely not running out; while SRAM is freaking expensive and dominating the MCU price.

Actually, I have never ran out of flash rom in any MCU project, which is a bit surprising, since I've been doing quite a lot of things. But RAM is scarce.

Usually (but not always), the importance ends up in this order in my embedded projects:
- RAM usage
- Speed
- Program memory usage

So, to calculate relevant "figure of merits", I'd introduce some heavy coefficients for the cost of stack bytes vs. the cost of program memory bytes, like 10x.

Your mileage may vary.

I agree with you. But do consider that we're talking about 80 bytes of stack space difference (on an ARM, only 30 on AVR (or 40 on Mega) which is small even when you've only got 1024 bytes to start with.

Also,  most programs do some calculations and then print results. That stack space is being used only during the result printing. The calculation part is free to use it. (different story if you want to do debug print from the middle of the calculation -- but that's development time and you may be able to afford one bigger device for dev work).

[brucehoult]

The USUAL excuse for recursion is that it makes the code much simpler, more compact, and easier to understand at the SOURCE CODE level.  That's vaguely true in this example ("print the rest of the number, print the last digit" vs "extract all the digits and print them backwards"), and not really true at all for the factorial/fibonacci examples.  But it gets real obvious when trying to do trees or divide-and-conquer sort algorithms without recursion.  Towers of Hanoi is probably a good example - anyone want to turn this Hanoi code into an iterative version?

Code: [Select]

void hanoifun(int n, char fr, char tr, char ar)//fr=from rod,tr =to rod, ar=aux rod
{
    if (n == 1)
    {
        printf("\n Move disk 1 from rod %c to rod %c", fr, tr);
        return;
    }
    hanoifun(n-1, fr, ar, tr);
    printf("\n Move disk %d from rod %c to rod %c", n, fr, tr);
    hanoifun(n-1, ar, tr, fr);
}


I'll reply to the other points later, but in the meantime try this :-) :-) :-)

Code: [Select]

typedef unsigned state;
int cto(state n){return n&1?cto(n>>1)+1:0;}

void hanoifun(int n, char fr, char tr, char ar) { //fr=from rod,tr =to rod, ar=aux rod
    char r[] = {fr,tr,ar};
    for (state s=1; s<((state)1)<<n; ++s)
        printf("\n Move disk %d from rod %c to rod %c",
               cto(~s)+1, r[(s&s-1)%3], r[((s|s-1)+1)%3]);
}

OBVIOUSLY, this is intended to be obfuscated code,not "good" code. But it works, producing byte-for-byte the same output.

[NorthGuy]

To whom it may concern,

Does your C compiler insert the stack protector bloat in all the functions with local array as brucehoult's does? This certainly screws up the results to some extent.

I don't think you can compare the non-recursive routines which can build the output in place with the recursive routines which spit the characters out one by one. You want to make recursive and non-recursive cases as similar as possible. Then your tests will separate the effect of the recursion in the purest form.

[brucehoult]

I'd say it's too close to call. We're down to experimental error.

Your compiled code is still 1.85x bigger than mine :-)

So true. But I think the comparison would better reflect the merits of recursion if you compiled it with -fno-stack-protector so that the code wouldn't be affected by stack protection paranoia.

Or, if you insist on stack protection, then you could compile both variants with -fstack-protector-all.

That's true. I picked simple -Os at the start (and -march=armv7 if your compiler doesn't default to that) and didn't want to go mucking with flags halfway through.

I could do that, but then I'd split my recursive code into two functions (one for signed and one for unsigned, with one calling the other) to even things up and get both faster code and two useful functions for the price of one :-)

[splin]

I agree with you. But do consider that we're talking about 80 bytes of stack space difference (on an ARM, only 30 on AVR (or 40 on Mega) which is small even when you've only got 1024 bytes to start with.

Well we clearly have very different opinions on what is 'small' in the context of an MCU with 1K of ram. 80 bytes of stack is 8% - for one trivial function - is a *huge* amount of one of the most valuable resources. Then double it if an interrupt routine were to print a number out - sure you probably wouldn't want to do this in a high priority interrupt routine but it would be perfectly legitimate to use it in a software interrupt such as a deferred low priority device driver handler routine. Then triple it if another lowish priority interrupt uses it.

Much worse if you are running an RTOS - now multiply that extra stack usage by the number of processes that can use that function. You'd likely want a processor with more than 1K of RAM with an RTOS but the principle remains that RAM costs money and is significantly more expensive than Flash.

Determining maximum stack usage is also much harder which is why recursion is banned by some codes of practice such as MISRA. The compiler can report the maximum stack used by a function but usually can't determine how many times a function can get called recursively. I'm sure there are some good tools available these days to help but stack sizing, especially in RTOS designs, was always something of a dark art and prone to errors - typically resulting in a hard to diagnose or reproduce crash.

Obviously its horses for courses and in some scenarios recursion may be justifiable by simpler code and thus potentially quicker to develop, more reliable and easier to maintain.

[sasa]

No body will persuade me that trivial: code + stack push + recursive call is faster than code +loop jump. It is simply impossible.

Well, perhaps more detailed analysis is in order.
...

No need realty and I will not comment anything particular...

What is evident here is that excuse for writing inappropriate code and using inappropriate methodology is based on a hope that complier will optimize it up to the level that wrong approach will result in good performance! And that is absurd!

The point of being good programmer is to write good optimized code which every compiler should  transfer into efficient machine code, even with zero optimization.  Compiler optimization should be only additional way to rewrite machine code to be efficient...

Several pages here is about tail recursion, compiler optimization, etc... It is simply irresponsible to rely on compiler optimization since on some other  platform may produce equally bad machine code as it is source code.

That is the whole point.

Towers of Hanoi is probably a good example - anyone want to turn this Hanoi code into an iterative version?

Towers of Hanoi is just an example for use of recursion, pointless math puzzle, with no practical usage than learning. Up to some small numbers of rods and disks it is possible to use iterative approach, but generally no.

As any recursion, it can be translated into iterative version, but that is equally pointless.

[NorthGuy]

I could do that, but then I'd split my recursive code into two functions (one for signed and one for unsigned, with one calling the other) to even things up and get both faster code and two useful functions for the price of one :-)

In all honesty, you cannot use the compiler bloat as an argument for or against recursion. I'm sure the -fstack-protector-all option would kill any chances for any recursion

There are many ways to make code faster. For example, you can unroll the loops.

Then the result depends a great deal on the typical data. For example, if most of the data consists of 9-10 digit numbers, it would pay off to divide by 10000000000 first, then by 1000000000 and continue downwards. This would avoid the need to reverse the array. But if the data consists of mostly smaller numbers, such approach would be a complete disaster.

As to the recursion, I think the tests confirmed what we knew all along:

- recursion doesn't produce any significant performance decrease
- the code is more compact and easier to write
- there's some extra stack usage, but it is typically not a problem

[sasa]

Does your C compiler insert the stack protector bloat in all the functions with local array as brucehoult's does? This certainly screws up the results to some extent.
...

I do not really care, that is based on brucehoult's code and I have sent complete source code. My choice will not be such testing case.

Let see brucehoult's testing results on his own test frame and other platforms.

[sasa]

You are forgetting that many modern compilers will do a tail call optimization and thus there is no stack push! (assuming arguments fit into registers) The entire recursive call is optimized away and replaced by a jump.

You certainly cannot rely on compilers optimization on every platform, as I have mentioned here several times. That is just excuse as any for inappropriate coding.

And brucehoult has demonstrated that even non tail-recursive function could be faster than iterative version - the overhead of the function call is simply less than the extra code that the non-recursive version needs.

Brucehoult demonstrated that only heavy machinery should be used, even to cover mouse hole... I'm certainly not a fan for that approach.

Assumptions are dangerous.

Very, very dangerous....

[janoc]

"assuming"? assuming or "hoping" compiler will do its magic is not a wise thing to do, from a programmer standpoint, imho... what if arguments are not fit in registers? "assuming" will create very minimal threat if you are working on a fixed familiar system everytime... but not when on many different systems...

Of course, if you are writing portable, multiplatform code, then what works on one system/compiler may not work on another.

However, in that case wasting few bytes or clock cycles is rarely your problem because you will need to deal with various abstractions to keep the code working between the different platforms. And those will likely cost you more than pushing few arguments on the stack.

Moreover, it is trivial to verify whether the optimization has, in fact, been done.

[janoc]

You certainly cannot rely on compilers optimization on every platform, as I have mentioned here several times. That is just excuse as any for inappropriate coding.

Where have I said that you should blindly rely on the optimization on every platform? That's a strawman you are fighting there.

On the other hand, when what you call "inappropriate coding" delivers both faster and smaller code (both very relevant on resource limited microcontrollers), then your argument flies out of the window. Should we not use the optimization when it is available only because you think such code is "inappropriate"?   

Heck, the code is even perfectly readable, if it was at least some convoluted hack like the Duff's device ...

Brucehoult demonstrated that only heavy machinery should be used, even to cover mouse hole... I'm certainly not a fan for that approach.

Again, that "heavy machinery" (not sure what is "heavy machinery" on a technique taught to every computer science/engineering freshman, but I digress) delivers better performance and needs less code space.

It doesn't mean I am going to start replacing my loops with recursion en masse, but it certainly debunks some widespread & incorrect assumptions.

Not being a fan of something simply isn't a good enough engineering argument here.

[Bruce Abbott]

Small PICs are fundamentally unsuited to running C code,

Which is why nobody writes code for small PICs in C.  Someone should tell Microchip!

The MCU executes machine code, not C. We use a high level language for convenience, not because it is more suited to a particular architecture. In fact translating C into something that works at all is not easy. But we push that problem onto the compiler writer - then we can blithely write 'elegant' source code, hoping that the compiler will optimize the mess it produces.

You are right though, 'small' PICs (and other MCUs which are similarly limited) are not suited to unrestricted recursion. That this is not considered a problem is proof that recursion is not a sought after feature on these chips, otherwise Microchip would have implemented it. But of course nobody uses 8 bit PICs anymore. Microchip must be a bunch of idiots - churning out new 8 bit PICs that nobody wants. 

[ehughes]

http://lars-lab.jpl.nasa.gov/JPL_Coding_Standard_C.pdf


Most people who have to worry about their code working in a difficult scenario (say on a robot 2 million miles away) avoid recursion.

http://www.embedded.com/electronics-blogs/break-points/4025734/MISRA-minimizes-mishaps

MISRA -- > Rule 16.2: Functions shall not call themselves, either directly or indirectly.

[Cerebus]

http://lars-lab.jpl.nasa.gov/JPL_Coding_Standard_C.pdf


Most people who have to worry about their code working in a difficult scenario (say on a robot 2 million miles away) avoid recursion.

http://www.embedded.com/electronics-blogs/break-points/4025734/MISRA-minimizes-mishaps

MISRA -- > Rule 16.2: Functions shall not call themselves, either directly or indirectly.

Argument by authority is never very convincing, especially when you cite as authority an agency whose most infamous coding error is splashed over the surface of Mars.

And here are some other rules from MISRA, quoted above.

Rule 2.2: Source code shall only use /* ... */ style comments.

Rule 20.4: Dynamic heap memory allocation shall not be used.

So, "thou shalt not use recursion" combined with "thou shalt not allocate memory" - presumably "thou shalt not compute any problem the size of which is not fully known in advance" and "when making lamentation about this in source code thou shalt only do so in /* ... */ comments", yerrse...

Judging from some of the other rules, like 5.2, I'm kind of surprised that MISRA doesn't have one that starts "code shall be punched on 80 column cards, starting in column 7...".

I find your citations to be, errm, somewhat underwhelmingly unconvincing.

[bd139]

Indeed. We have more cash moving through our software every *quarter* than the entire MER mission cost to date, the codebase is hundreds of times bigger and we could technically with one data leak screw most of the European finance sector. We don't use MISRA or JPL coding standards! 

Edit: you should be scared. We even have beer fridge in the office!

[tggzzz]

Indeed. We have more cash moving through our software every *quarter* than the entire MER mission cost to date, the codebase is hundreds of times bigger and we could technically with one data leak screw most of the European finance sector. We don't use MISRA or JPL coding standards! 

Edit: you should be scared. We even have beer fridge in the office!

I am scared (but not surprised) and not because you have  a beer fridge

[bd139]

It's the outsourcing that scares me.

I'm going to start digging a bunker in the garden this weekend. It'll be either the outsourcers or the recursion that causes satellites and financial ruin to rain down on us.

[tggzzz]

It's the outsourcing that scares me.

I'm going to start digging a bunker in the garden this weekend. It'll be either the outsourcers or the recursion that causes satellites and financial ruin to rain down on us.

Nah. It is the swallowed NullPointerExceptions and arithmetic errors, amongst many things.

Will the bunker be big enough to contain all your valuables ;} And are they stored as Soveriegns/Britannias, or in EUR?

[Cerebus]

Will the bunker be big enough to contain all your valuables ;} And are they stored as Soveriegns/Britannias, or in EUR?

Vacuum packed PG Tips. It'll be worth a fortune three months into the zombie apocalypse. And with a few jars of Vegemite you'll be able to command a veritable army of ex-pat Aussies.

[sasa]

Where have I said that you should blindly rely on the optimization on every platform? That's a strawman you are fighting there.

Certainly you are not computer software design nor engineer (sorry if you are). Your knowledge and experience may be quite limited and based on some specific university classes, or worst some third-party specific courses, or what you read elsewhere. If someone read that tail recursion is a fancy way of coding and can solve any possible problem - it should be done this way, since there is no negative effect over all, because compiler will optimize it for you... 

Quite superficial and pointless argumentation. Did you ask yourself why exists so many other ways? Main principle in programming is to solve problem on the most efficient and stable way. And using tail recursion for every trivial task is certainly inappropriate and irresponsible. It is the same in EE, you do not use FPGA just to blink led... Oh, but digression is obvious - FPGA is so fancy! It does not matter it is expensive and require quite logistic on the board.

Quite obvious it is pointless discussion - do it at inappropriate way if you want, even in medical devices, planes or nuclear plants and plays with other lives...

Most of people here use programming in C as a necessary evil in order just that whole damn thing start  to work, knowing no better ways than use tail recursion in every occasion. 

Did you even seen how percentage my iterative solution converting integer to string is faster and how code is simple. It also have no single negative effect and can be used with any small MCU as well. Obviously, it is pointless discussion with people knowing nothing more suitable than tail recursion. 

Sapienti sat.

[westfw]

What is evident here is that excuse for writing inappropriate code and using inappropriate methodology is based on a hope that complier will optimize it up to the level that wrong approach will result in good performance! And that is absurd!

The point of being good programmer is to write good optimized code which every compiler should  transfer into efficient machine code, even with zero optimization.

I disagree with you almost 100%.  If you deign to use a compiler, you are ALWAYS counting on it to optimize enough to yield good performance, and many times so with any modern language that isn't tightly coupled the CPU architecture of the target (people will tell you that C is a fancy assembler for the PDP-11.  That's pretty close, but the days where you carefully pick which local variables go into registers and use --p and p++ because they produce more efficient code with the available instruction set are long gone (and good riddance!)  And it's not like we're asking for "extreme optimization" in order to allow simple recursion to be "somewhat efficient."  It's just "don't put lots more data on the stack than you really need to."

Also, perhaps you haven't used an old compiler or one that really does "zero optimization", or taken a compiler design class.  What comes out of most compilers with "no optimization at all" is REALLY AWFUL.  (hint: "gcc -O0" does not do "zero optimization."  For a while, the "free" PIC-8 compiler that Microchip was distributing really did zero optimization, and people were horrified - sure that they were intentionally de-optimizing the code.  I believe they've relented, and now offer something closer to gcc's -O0.  You might be able to find examples from that era in archives around the net.)

BTW, there's at least one C compiler for PIC18 that supports recursion (they implement a second stack for data), and several AVR compilers use separate "data stack" and "return stack.)  FORTH usually has separate call and data stacks.  Many architectures can use essentially any register as a stack pointer, except for interrupts.   So having a "hardware return stack" (not in normal memory) doesn't preclude recursion.

[westfw]

BTW, we're not in the 1970s.  There ought to be lots of well-researched, well-implemented and standardized, well-understood, well-analyzed and well-measured recursive algorithms.  I mean, ALL recursive algorithms are supposed to have nice, bounded termination conditions, and most of the bugs that led to stack exhaustion should be gone (not that you can't write your own!)   I'd expect that the stack usage of the, say, the C++ STL implementation of red/black trees (which I assume is recursive) is better-analyzed than the stack usage of printf().  (OTOH, perhaps all STL code is carefully written to avoid recursion?)

[sasa]

For a while, the "free" PIC-8 compiler that Microchip was distributing really did zero optimization, and people were horrified - sure that they were intentionally de-optimizing the code. 

This have nothing related with  "zero optimization" note. I used to use XC8 years ago, it is based on   HI-TECH C compiler which had exactly the same limitation in free license mode. They intentionally inserted useless instructions and loops in order to force people to buy commercial license, regardless what Microchip representatives explains on they forum...

I will not comment anything else, it is simply pointless.

[bd139]

It's the outsourcing that scares me.

I'm going to start digging a bunker in the garden this weekend. It'll be either the outsourcers or the recursion that causes satellites and financial ruin to rain down on us.

Nah. It is the swallowed NullPointerExceptions and arithmetic errors, amongst many things.

Will the bunker be big enough to contain all your valuables ;} And are they stored as Soveriegns/Britannias, or in EUR?

We haven't had an NPE for years as we have very heavy levels of assertions. Input, outputs, invariants, the lot. Arithmetic errors are a problem, particularly when one your suppliers sends financial values through their APIs as floats!?!?

All I need is ASDA beans and tea bags. Oh and a tin opener. Adding to list

[tggzzz]

It's the outsourcing that scares me.

I'm going to start digging a bunker in the garden this weekend. It'll be either the outsourcers or the recursion that causes satellites and financial ruin to rain down on us.

Nah. It is the swallowed NullPointerExceptions and arithmetic errors, amongst many things.

Will the bunker be big enough to contain all your valuables ;} And are they stored as Soveriegns/Britannias, or in EUR?

We haven't had an NPE for years as we have very heavy levels of assertions. Input, outputs, invariants, the lot. Arithmetic errors are a problem, particularly when one your suppliers sends financial values through their APIs as floats!?!?

All I need is ASDA beans and tea bags. Oh and a tin opener. Adding to list

That's the way it should be, of course - but I have seen otherwise My comments were ignored due to corporate culture; I left.

As for other suppliers being idiotic, well "reconciliation" is a whole subfield of banking transactions.

In a different existence, I created low-impact instrumentation and insisted it was left in delivered products. It was very pleasing to see how many inter-company battles were throttled before people even thought about bringing in lawyers

[bd139]

Indeed. I've not renewed a few contracts over crazy like that. The worst is the cargo cults. They are confident that they are doing it right and are waving their hands approximately but the work they have done is ineffective, solves no problems and costs a lot of money.

Agree with instrumentation. We are VERY instrumentation heavy. About 20% of our infrastructure is monitoring, tracing and alerting. We find and fix the defects that do exist pretty much instantly. It's nice to get a call from a client and you tell them that the issue was fixed two hours before they called. Everyone goes away happy.

[Cerebus]

... The worst is the cargo cults. ...

Or anywhere where you can play "programming buzzword-du-jour bingo".

Run a project like that anywhere near me and you have to be Agile to avoid ASSERT(BacksideStatus == HeavilyBooted).

[janoc]

Where have I said that you should blindly rely on the optimization on every platform? That's a strawman you are fighting there.

Certainly you are not computer software design nor engineer (sorry if you are). Your knowledge and experience may be quite limited and based on some specific university classes, or worst some third-party specific courses, or what you read elsewhere. If someone read that tail recursion is a fancy way of coding and can solve any possible problem - it should be done this way, since there is no negative effect over all, because compiler will optimize it for you... 

Sasa, will all respect, your assumptions are getting worse and worse. 20 years of software engineering under my belt, both commercial (including some embedded work) and research. I guess that's not enough and I am obviously not knowing what am I doing. Thank you for telling me!

Quite superficial and pointless argumentation. Did you ask yourself why exists so many other ways? Main principle in programming is to solve problem on the most efficient and stable way. And using tail recursion for every trivial task is certainly inappropriate and irresponsible. It is the same in EE, you do not use FPGA just to blink led... Oh, but digression is obvious - FPGA is so fancy! It does not matter it is expensive and require quite logistic on the board.

You are still fighting strawmen here, because nobody has made this argument. Nobody is advocating mindlessly using one technique over the other, but you seem to be constantly missing the point.

Quite obvious it is pointless discussion - do it at inappropriate way if you want, even in medical devices, planes or nuclear plants and plays with other lives...

Most of people here use programming in C as a necessary evil in order just that whole damn thing start  to work, knowing no better ways than use tail recursion in every occasion. 

Sorry, that's complete BS - nobody was making such argument here. Another strawman.

Did you even seen how percentage my iterative solution converting integer to string is faster and how code is simple. It also have no single negative effect and can be used with any small MCU as well.

Sapienti sat.

Well, the facts don't seem to support neither the "faster" and the "simple" is arguable (granted, it is trivial code in both cases).

Obviously, it is pointless discussion with people knowing nothing more suitable than tail recursion. 

No, it is a completely pointless discussion with people not understanding (or willing to understand) written text and not wanting to see facts even when they get them on a silver plate.

Sorry.

[Mechatrommer]

so this is a dick waving contest of how many years of black belt you have... well, i have about 20 years of "self-learnt" belt, anything other than assembly language for performance is moot, and thats it...  if you really care about squeezing out performance by tweaking generated machine code, reducing "backstage" housekeeping code generated by the compiler, then i think you should rethink of your life... gurus in algorithm are only talking about O(?) operations, not in anywhere mentioning about machine specific code, let alone compiler options. yeah, i have to specifically key in the -ffunction-sections, -Wl,--gc-sections options in every AVR-GCC projects that i built, just to get rid of dormant functions in the final hex file, fucking compilers of the 21st century... and that compiler options only available when you ask in the forum  and err (edit), havent i told you one of my PIC16 program went rampant just because of stack overflow? i called to many functions.. fucking compiler for not letting me know..

[janoc]

Sasa, I took your optimized code you have posted as a challenge and added my recursive variant to it.

Code: [Select]

int print_dec1(unsigned n, char*s, int l)
{
    unsigned d = n/10;
    char ch = n - d*10 + '0';
    *s = ch;
   
    if (d == 0)
        return l;
    else
        return print_dec1(d, s + 1, l + 1);
}

void reverse(char *a, char *b)
{
    if(a < b)
    {
        char t = *b;
        *b = *a;
        *a = t;
        reverse(a+1, b-1);
    }
}

char* print_dec(int n, char *s) {
    int       len = 0;
    unsigned  u   = n;
    char     *r   = s;
   
    if (n < 0) {
        *(r++) = '-';
        u = -n;
        len = 1;
    }   
   
    len += print_dec1(u, r, 0);
    *(s+len+1) = '\0';
   
    reverse(r, s+len);
    return s;
}

Gasp, 3 functions!

Compiled with optimization for size (which is what you had there, I believe: gcc -Os printdec.c )

Code: [Select]

itoc_sasa_1     : 772 ms
itoc_sasa_1     : 746 ms
itoc_sasa_1     : 740 ms
print_dec     : 769 ms
print_dec     : 775 ms
print_dec     : 773 ms

My code compiles to 142 bytes (all three functions together), yours to 96 bytes.

Hmm, not bad but let's see what happens if we actually turn on -O2 which does the tail call optimization (gcc -O2 printdec.c ):

Code: [Select]

itoc_sasa_1     : 244 ms
itoc_sasa_1     : 216 ms
itoc_sasa_1     : 216 ms
print_dec     : 217 ms
print_dec     : 217 ms
print_dec     : 216 ms

Guess what, the running time is identical, despite me having 3 functions there vs one you have. However, my code is now 3x longer for some reason (313 bytes vs 107 bytes). Didn't check why, maybe something got inlined.

It could be probably improved even more if I have used an "accumulator" argument in the recursive function which would eliminate the need for the reversing at the end at the expense of needing 2x the memory, but I really couldn't be bothered. I think this is more than enough to prove the point already.

For the record, I have used this gcc:

Code: [Select]

$ gcc -v
Using built-in specs.
COLLECT_GCC=gcc
COLLECT_LTO_WRAPPER=/usr/lib/gcc/x86_64-mageia-linux-gnu/5.4.0/lto-wrapper
Target: x86_64-mageia-linux-gnu
Configured with: ../configure --prefix=/usr --libexecdir=/usr/lib --with-slibdir=/lib64 --with-pkgversion='Mageia 5.4.0-5.mga6' --with-bugurl=https://bugs.mageia.org/ --mandir=/usr/share/man --infodir=/usr/share/info --enable-checking=release --enable-languages=c,c++,ada,fortran,objc,obj-c++,java --enable-linker-build-id --build=x86_64-mageia-linux-gnu --host=x86_64-mageia-linux-gnu --with-cpu=generic --with-system-zlib --enable-threads=posix --enable-shared --enable-objc-gc --enable-long-long --enable-__cxa_atexit --disable-libunwind-exceptions --enable-clocale=gnu --enable-java-awt=gtk --with-java-home=/usr/lib/jvm/java-1.5.0-gcj-1.5.0.0/jre --with-ecj-jar=/usr/share/java/eclipse-ecj.jar --enable-gtk-cairo --disable-libjava-multilib --enable-ssp --disable-libssp --disable-werror --with-isl --with-python-dir=/lib/python2.7/site-packages --enable-lto
Thread model: posix
gcc version 5.4.0 (Mageia 5.4.0-5.mga6)

I have tried it with clang 3.9.1 too and the results are similar.

Now, to make it clear once more - I am not expecting people to write recursion instead of loops in situations like this. It is not very intuitive for most (especially my messy implementation) and would make the code harder to maintain. However, I hope we have proved once for all that recursive code does not have to be slower or use more resources than iterative code. If in doubt, measure!

This is the code I have used:
https://pastebin.com/Y3pJZuP1

[sasa]

Now, to make it clear once more - I am not expecting people to write recursion instead of loops in situations like this. It is not very intuitive for most (especially my messy implementation) and would make the code harder to maintain. However, I hope we have proved once for all that recursive code does not have to be slower or use more resources than iterative code. If in doubt, measure!

We proved nothing yet, I'm afraid.

Results I have, only proves my point - compiler optimization parameters only matters, not a code quality. In default compiler optimization, your function is far more the worst of all - 2x slower! See sorted tables and test yourself if not believe.

My function is clearly the fastest, except with -Ofast. I could optimize it a bit more, but currently I have no time for playing around.

Hint: When use tail recursion on Intel/AMD 64-bit, always use -Ofast. Or not? Perhaps other code speed may suffer?

Few notes:

1. If have fast computer, elapsed time of 200ms and 210ms means nothing - resolution is not good enough. Enlarge data by factor 5 or 10.
2. Leave dummy test to execute, as suggested.

-O0 (if not specified, same as default, by GCC help page):

Code: [Select]

itoc_sasa_1     : 3730 ms
itoc_ref_2      : 4040 ms
itoc_NorthGuy_1 : 4245 ms
itoc_ref_1      : 4253 ms
itoc_janoc_1    : 6553 ms

-Os:

Code: [Select]

itoc_sasa_1     : 5890 ms
itoc_janoc_1    : 6017 ms
itoc_ref_1      : 6155 ms
itoc_ref_2      : 6264 ms
itoc_NorthGuy_1 : 6382 ms

-O (size and time, without any optimizations that take a great deal of compilation time)

Code: [Select]

itoc_sasa_1     : 2239 ms
itoc_ref_2      : 2785 ms
itoc_NorthGuy_1 : 2789 ms
itoc_ref_1      : 3254 ms
itoc_janoc_1    : 3539 ms

-Ofast

Code: [Select]

itoc_ref_2      : 1998 ms
itoc_janoc_1    : 2166 ms
itoc_sasa_1     : 2357 ms
itoc_NorthGuy_1 : 2371 ms
itoc_ref_1      : 2808 ms


[NorthGuy]

Speaking of compilers. I wonder how all these fare against itoa()?

[janoc]

Speaking of compilers. I wonder how all these fare against itoa()?

They don't - itoa() is not a standard function and many C libraries don't implement it. That's why this silly example - it is a commonly (re)-implemented function.

We proved nothing yet, I'm afraid.

Results I have, only proves my point - compiler optimization parameters only matters, not a code quality. In default compiler optimization, your function is far more the worst of all - 2x slower! See sorted tables and test yourself if not believe.

So, you have disabled an optimization that the recursive code explicitly depends on in order to claim a "win".

That's a pretty desperate move.

GCC needs to have at least optimization level -O2 (no need for -Ofast which is -O3 + some extras) on in order to do tail recursion optimization. So if you turn that off, of course the code is going to be slower! What a surprise! 

And with -Ofast my code was actually faster than yours!

The default optimization level with GCC is, surprise, none!

From the manpage:

Without any optimization option, the compiler's goal is to reduce the cost of compilation and to make debugging produce the expected results.  Statements are independent: if you stop the program with  a breakpoint between statements, you can then assign a new value to any variable or change the program counter to any other statement in the function and get exactly the results you expect from the source code.

So if you are compiling with the default options in production, you should better re-read the manual of your compiler. Pretty much nobody uses GCC with no optimization on, except for debug builds. I don't see what is the point in such comparison unless you are grasping at straws to prove your point.

[sasa]

...
I don't see what is the point in such comparison unless you are grasping at straws to prove your point.

Please avoid that kind of terminology. If that is true, I would certainly hide result with -Ofast. I have missed to copy results with -O2.

-O2:

Code: [Select]

itoc_sasa_1     : 2082 ms
itoc_janoc_1    : 2209 ms
itoc_NorthGuy_1 : 2574 ms
itoc_ref_2      : 2580 ms
itoc_ref_1      : 3124 ms

Upper table certainly show different.

I do not know about what desperate move you are talking about. These are actual results on "clean environment" on mentioned Intel Atom and Linux. Everybody may try on any platform.

Did you provide corrections I have suggested you in order to get comparable times?

[westfw]

GCC needs to have at least optimization level -O2 (no need for -Ofast which is -O3 + some extras) on in order to do tail recursion optimization.

Is this code even subject to tail optimization?  No one has been posting any of the x86 assembly code :-(

Umm...

Code: [Select]

_itoc_ref_2_uint:
00000000000000d0    pushq    %rbp
00000000000000d1    movq    %rsp, %rbp
00000000000000d4    pushq    %rbx
00000000000000d5    pushq    %rax
00000000000000d6    movl    %edi, %eax
00000000000000d8    movl    %eax, %ecx
00000000000000da    movl    $0xcccccccd, %edi       ## imm = 0xCCCCCCCD
00000000000000df    imulq    %rcx, %rdi
00000000000000e3    shrq    $0x23, %rdi
00000000000000e7    imull    $-0xa, %edi, %ecx
00000000000000ea    leal    0x30(%rax,%rcx), %ebx
00000000000000ee    cmpl    $0xa, %eax
00000000000000f1    jb    0xf8
00000000000000f3    callq    _itoc_ref_2_uint
00000000000000f8    movq    _pp(%rip), %rax
00000000000000ff    leaq    0x1(%rax), %rcx
0000000000000103    movq    %rcx, _pp(%rip)
000000000000010a    movb    %bl, _myputchar(%rax)
000000000000010c    addq    $0x8, %rsp
0000000000000110    popq    %rbx
0000000000000111    popq    %rbp
0000000000000112    retq
0000000000000113    nopw    %cs:_myputchar(%rax,%rax)
That seems a bit weird in a couple of ways...
1) It sets of a stack frame that it doesn't use (even with -O3)
2) Doesn't x86 have a nice divide instruction that gives you the quotient and remainder in one instruction?  The compiler doesn't seem to figure out that it could do that (or perhaps Multiply is that much faster than divide?)  It does even worse if I use "%"...

[hamster_nz]

Spurred on by decimal digit extraction debate, I was wondering if there is a faster way to divide a 32-bit integer by 10 on modern 64-bit CPU.....

It turns out there is:

Code: [Select]

   d = (i * 0xCCCCCCCDLLU)>>35;

is faster than GCC's default:

Code: [Select]

   d = i/10;

Test program (compile with/without REF defined):

Code: [Select]

#include <stdio.h>

unsigned div10(unsigned x) {
#ifdef REF
      /* Implement 32-bit division using divide */
      return x/10;
#else
      return (x * 0xCCCCCCCDLLU)>>35;
#endif
}

int main(int argc, char *argv[]) {
   unsigned i;
   for(i = 0; i < 0xFFFFFFFF; i++) {
      unsigned d,r;
      d = div10(i);
      /* Implement 32-bit division using 32x32 multiply */
      r   = i-10*d;
      if(r > 9) {
        printf("Invalid i =  %u, d = %u, r= %u\n",i,d,r);
      }
   }
   return 0;
}

Here is the assembler, if anybody is interested:

Code: [Select]

div10:
.LFB23:
        .cfi_startproc
        movl    %edi, %eax
        movl    $-858993459, %edx
        mull    %edx
        movl    %edx, %eax
        shrl    $3, %eax
        ret
vs

Code: [Select]

div10:
.LFB23:
        .cfi_startproc
        movl    %edi, %eax
        movl    $3435973837, %edx
        imulq   %rdx, %rax
        shrq    $35, %rax
        ret
        .cfi_endproc
.LFE23:

On my AMD A10-9600P laptop, using the multiply takes only 70% of the time (7.688 sec vs 10.764). Even when inlined I get much the same result. Anybody want to try on an Intel?

I've never seen this mentioned anywhere before - has anybody else seen this mentoned?

[John Coloccia]

Main principle in programming is to solve problem on the most efficient and stable way.

You've said this a couple of times now, I couldn't disagree more. The main goal is to write bug-free, maintainable code that meets the requirement. "Most efficient" is a terrible goal and leads to the kind of unmaintainable garbage that I have to fix day in and day out.

This whole thread is kind of strange, actually. I use recursion if it's the right solution, and I don't use it if it's the wrong solution. It's like asking, "do you use function pointers in the real world?"

[brucehoult]

Spurred on by decimal digit extraction debate, I was wondering if there is a faster way to divide a 32-bit integer by 10 on modern 64-bit CPU.....

It turns out there is:

Code: [Select]

   d = (i * 0xCCCCCCCDLLU)>>35;


Err .. this is *exactly* what gcc does anyway. I'd be disapointed by any compiler than didn't. Look at, for example, the code in my days ago post: https://www.eevblog.com/forum/microcontrollers/recursion-do-you-use-it-in-the-real-world/msg1296764/#msg1296764

[hamster_nz]

Spurred on by decimal digit extraction debate, I was wondering if there is a faster way to divide a 32-bit integer by 10 on modern 64-bit CPU.....

It turns out there is:

Code: [Select]

   d = (i * 0xCCCCCCCDLLU)>>35;


Err .. this is *exactly* what gcc does anyway. I'd be disapointed by any compiler than didn't. Look at, for example, the code in my days ago post: https://www.eevblog.com/forum/microcontrollers/recursion-do-you-use-it-in-the-real-world/msg1296764/#msg1296764

You're missing that on x64 for the the '/10 ' version GCC only uses 32-bit registers, and the high word of the result ends up in the wrong register and then has to shuffle the results around.

When using the LLU constant, the result ends up in 64-bit register, so no register-to-register moves are required.

[sasa]

Spurred on by decimal digit extraction debate, I was wondering if there is a faster way to divide a 32-bit integer by 10 on modern 64-bit CPU.....

I've never seen this mentioned anywhere before - has anybody else seen this mentoned?

This, as well as multiplying by shifting is used on platforms without hardware implementation. And that should be primarily the job for compiler optimizer for specific platform.

You've said this a couple of times now, I couldn't disagree more. The main goal is to write bug-free, maintainable code that meets the requirement. "Most efficient" is a terrible goal and leads to the kind of unmaintainable garbage that I have to fix day in and day out.

As well, I have mentioned couple of times: "suitable way", "proper solution for the task", etc. But everybody here seems to prefer to pull up words from context and interpret as they like... 

If function / algorithm is essential/low-level for the whole application, of course you should code it to be the fastest possible platform independent solution regardless what compiler optimization will produce. Otherwise should be used the most appropriate way... All that is also mentioned several times. Please read the whole thread.

The (useless) debate here is about appropriate clean and fast iterative solution for specific task and recursive "simple and clean code" compiler is capable to transfer info the fastest and shortest code, ignoring or minimizing effect every recursion theoretically have.

So far, results show that on Intel/AMD Linux 64-bit platform,  the fastest recursive solution is indeed really fastest only with one parameter (-Ofast), while in all others confirms wide instability and can be second fastest or even the slowest.

On other platforms, with other machine code (RISC mostly), iterative solution with its stability will probably be again one of the top fastest (if not top), regardless what optimization is used. The reason is simple, but tail recursion fan ignore that fact and will try to find most suitable optimization parameter which will make it faster.

Then we come to MCU platform, where recursion is obviously hardly desirable. Then, there is no other way than use the most suitable iterative solution. Again, if avoid hand written ASM - not a single compiler will made better optimized code.

Etc, etc. As someone noted here that this is a "dic* contest", and basically is to disprove the theory that recursion should be forced because nature of the problem is recursive or it is the clearest way of coding producing smallest and fastest machine code.

[T3sl4co1l]

For example, I've got this for AVR:

Code: [Select]

;
;     uDivTen
;
; Unsigned division by ten.  45 words, takes 60 cycles (plus rcall).
;
; Input:
;   r17:r16 = operand
; Output:
;   r1:r0 = quotient
;   r3:r2 = remainder
;   (r16 = 10, r17 = 0)
;
uDivTen:
push r7 ; register usage:
push r6 ; r7:r6 = operand (in[0..1])
push r5 ; r5:r4:r3:r2 = 40 bit accumulator, D[1..3] (byte 0 discarded)
push r4 ; r1:r0 = partial products
movw r6, r16 ; r16 = temp, r17 = zero
clr r17 ; (but first, save operand)

; multiply by K = 2^20 * 16 / 10 to make D[0..3] = in[0..1] * K[0..2]
; (implicitly discarding D[0])

ldi r16, (((exp2(24) / 10) + 1) & (0x0000ff << 16)) >> 16
mul r7, r16 ; in[1] * K[2]
movw r4, r0 ; save high word

ldi r16, (((exp2(24) / 10) + 1) & (0x0000ff << 0)) >> 0
mul r7, r16 ; in[1] * K[0]
movw r2, r0 ; save low word

mul r6, r16 ; in[0] * K[0]
add r2, r1 ; accumulate to D[1] (discard lowest byte)
adc r3, r17
adc r4, r17
adc r5, r17

ldi r16, (((exp2(24) / 10) + 1) & (0x0000ff << 8)) >> 8
mul r6, r16 ; in[0] * K[1]
add r2, r0 ; accumulate to D[1..2]
adc r3, r1
adc r4, r17
adc r5, r17

mul r7, r16 ; in[1] * K[1]
add r3, r0 ; accumulate to D[2..3]
adc r4, r1
adc r5, r17


ldi r16, (((exp2(24) / 10) + 1) & (0x0000ff << 16)) >> 16
mul r6, r16 ; in[0] * K[2]
add r3, r0 ; accumulate to D[2..3]
adc r4, r1
adc r5, r17

; dig remainder out of the fractional part

ldi r16, 0x10 ; rounding bit
add r3, r16
ldi r16, 10
mul r3, r16 ; frac * 10
mov r2, r1
clr r3
movw r0, r4 ; quotient out

; r3 = 0, r2 = [0...9], r1:r0 = [0...6553]
pop r4
pop r5
pop r6
pop r7
ret
; END PROC uDivTen

Downside is it does a 24 bit intermediate operation.

Tim

[NorthGuy]

On my AMD A10-9600P laptop, using the multiply takes only 70% of the time (7.688 sec vs 10.764). Even when inlined I get much the same result. Anybody want to try on an Intel?

GCC uses multiplication instead of division. But ... Intel's division has early termination. If it is only 50% slower than multiplication, it might be more beneficial to use division. The division automatically provides the remainder which would eliminate the need for back multiplication and subtraction. There's a possibility that it actually could be faster. It's hard to figure out without trying.

Another question is how to tell C to use division. Perhaps, using /10 and %10 close to each other can trigger it. Otherwise, assembler is the way.

Anyway, this all is platform related.

[brucehoult]

Spurred on by decimal digit extraction debate, I was wondering if there is a faster way to divide a 32-bit integer by 10 on modern 64-bit CPU.....

It turns out there is:

Code: [Select]

   d = (i * 0xCCCCCCCDLLU)>>35;


Err .. this is *exactly* what gcc does anyway. I'd be disapointed by any compiler than didn't. Look at, for example, the code in my days ago post: https://www.eevblog.com/forum/microcontrollers/recursion-do-you-use-it-in-the-real-world/msg1296764/#msg1296764

You're missing that on x64 for the the '/10 ' version GCC only uses 32-bit registers, and the high word of the result ends up in the wrong register and then has to shuffle the results around.

When using the LLU constant, the result ends up in 64-bit register, so no register-to-register moves are required.

I'm not missing that. I looked at it, and understood that it makes no difference at all on a modern x86 because the register moves end up as simple renames in the pipeline.

I think you're missing that div10() has been inlined into main() and in the non-REF case the division has been entirely optimized away, because gcc was able to turn your code into this:

Code: [Select]

int main(int argc, char *argv[]) {
   unsigned i;
   unsigned long long inc = 0xCCCCCCCD, tot = 0;
   for(i = 0; i < 0xFFFFFFFF; i++) {
      unsigned d,r;
      d = tot>>35;
      r = i - ((d + d<<2) << 1);
      if(r > 9) {
        printf("Invalid i =  %u, d = %u, r= %u\n",i,d,r);
      }
      tot += inc;
   }
   return 0;
}

Try adding __attribute__ ((noinline)) to div10() and you'll find that the execution times are identical, at least on my linux desktop (Core i7 6700K Skylake) and on my 2011 17" MacBook Pro (Core i7 2720QM Sandy Bridge).

I'd be very surprised if that didn't apply to your AMD as well.

[hamster_nz]

Try adding __attribute__ ((noinline)) to div10() and you'll find that the execution times are identical, at least on my linux desktop (Core i7 6700K Skylake) and on my 2011 17" MacBook Pro (Core i7 2720QM Sandy Bridge).

I'd be very surprised if that didn't apply to your AMD as well.

Just checked on a core I3, and got 4.96 vs 7.68 seconds.

You are right, it is because "d = (i * 0xCCCCCCCDLLU)>>35;" can get inlined better, enabling the MUL ti be replaced by repeated addition.

So I can at least say it sometimes gives better results, but is no worse then the default.

EDIT: If you change the loop to "for(i = 0; i != 0xFFFFFFFF; i+=19)" you still get full coverage, and  it prevents the MUL from being optimized away. It is still quicker.

[Bruce Abbott]

You've said this a couple of times now, I couldn't disagree more. The main goal is to write bug-free, maintainable code that meets the requirement.

I agree. The real reason to avoid recursion is not that it might be less efficient, but because it can be non-obvious and easily introduce latent bugs.   

"Most efficient" is a terrible goal and leads to the kind of unmaintainable garbage that I have to fix day in and day out.

People have different ideas on what constitutes 'efficient' code. Some (wrongly) think that 'cleaner' or 'more elegant' source code will always produce more efficient machine code. Others go to extreme lengths to avoid constructs that the compiler will probably optimize away anyway. The worst are people who condense it into terse one-liners, then don't add any comments because their code is 'self-documenting'.

There are cases where efficiency is more important than readability, but that still doesn't make 'unmaintainable garbage' acceptable. Tricky code still needs to be well written and documented, perhaps even more so than standard stuff that everyone recognizes. I write mainly in assembler (which most people probably think is 'unreadable') but I structure it well, avoid tricky stuff wherever possible, and comment everything. Usually I will start by writing the most 'obvious' code, then once it is all working I go back and optimize any bits that are worth it. Code running fast enough? Haven't run out of memory? No need to optimize.
 

 

[brucehoult]

You've said this a couple of times now, I couldn't disagree more. The main goal is to write bug-free, maintainable code that meets the requirement.

I agree. The real reason to avoid recursion is not that it might be less efficient, but because it can be non-obvious and easily introduce latent bugs.   

I'm sorry but that's just absolutely not true. In any complex situation, a recursive solution is far easier to reason about and prove correct (to whatever standard you want/need).

The things that are non-obvious and easily introduce latent bugs are:

1) spaghetti gotos
2) assignment of a new value to an already-initialized variable
3) dynamic memory allocation using malloc&free

This is simple mathematical fact.

Recursive algorithms lend themselves to reasoning about static questions, independent of the concepts of time and flow of program execution. "I know how to solve the simplest version of this problem. I know how to partially solve a complex problem, and reduce it (along some dimension) towards the simplest version of the problem. Therefore I've proved that the solution to the complex problem is correct".

This is called proof by induction, and was taught in High School when I was there. I don't know if it still is.

Once you've proven the algorithm is correct THEN you can think about what resources it will need. If the work you do to reduce the problem to a simpler one is always *before* the recursive call then the extra resources are zero ... you (or the compiler) can turn it into a loop. Doing it yourself is pretty error prone though -- especially if you're programming in assembly language.

[hamster_nz]

Recursive algorithms lend themselves to reasoning about static questions, independent of the concepts of time and flow of program execution. "I know how to solve the simplest version of this problem. I know how to partially solve a complex problem, and reduce it (along some dimension) towards the simplest version of the problem. Therefore I've proved that the solution to the complex problem is correct".

This is called proof by induction, and was taught in High School when I was there. I don't know if it still is.

Once you've proven the algorithm is correct THEN you can think about what resources it will need. If the work you do to reduce the problem to a simpler one is always *before* the recursive call then the extra resources are zero ... you (or the compiler) can turn it into a loop. Doing it yourself is pretty error prone though -- especially if you're programming in assembly language.

I think that this might be a little bit generous with the truth, and self-selection of the problem being solved is at work.

 I think ("it is my unresearched opinion") that problems that tend to naturally fit recursive solutions in general tend to be simpler to prove correct, as they only have a limited amount of active state at any one time and all decisions are made locally.

For example, is a recursive bubble sort any easier to prove correct than the normal iterative version?

Code: [Select]

void bubble(struct *data, int n) {
   /* Sort the biggest value to the end of the list */
   int i;
   for(i = 1; i < n; i++)
     compare_and_swap(data+i-1, data+i);
   if(n > 2)
      bubble(data,n-1);
}

I am sure (if I coded this correctly) that it works just as well as a iterative solution -  apart from blowing up the stack at scale, but only if you don't have the correct compiler optimizations switched on.   

[John Coloccia]

You've said this a couple of times now, I couldn't disagree more. The main goal is to write bug-free, maintainable code that meets the requirement.

I agree. The real reason to avoid recursion is not that it might be less efficient, but because it can be non-obvious and easily introduce latent bugs.   

"Most efficient" is a terrible goal and leads to the kind of unmaintainable garbage that I have to fix day in and day out.

People have different ideas on what constitutes 'efficient' code. Some (wrongly) think that 'cleaner' or 'more elegant' source code will always produce more efficient machine code. Others go to extreme lengths to avoid constructs that the compiler will probably optimize away anyway. The worst are people who condense it into terse one-liners, then don't add any comments because their code is 'self-documenting'.

There are cases where efficiency is more important than readability, but that still doesn't make 'unmaintainable garbage' acceptable. Tricky code still needs to be well written and documented, perhaps even more so than standard stuff that everyone recognizes. I write mainly in assembler (which most people probably think is 'unreadable') but I structure it well, avoid tricky stuff wherever possible, and comment everything. Usually I will start by writing the most 'obvious' code, then once it is all working I go back and optimize any bits that are worth it. Code running fast enough? Haven't run out of memory? No need to optimize.
 

You must really hate Python. LOL.

My experience has generally been that if you write simple, straightforward code, you're giving the compiler writer the absolute best chance of figuring out just what the heck you had in mind, and the best chance at optimizing.

And anyhow, a great deal of code is I/O bound anyway. People spend too much time worrying about an instruction here and there, when what they should be worrying about is sensible data structures and organizing the algorithm so that pipelines and caching can work efficiently.

I don't mind assembly just so long as the obvious bits are written obviously, and the tricky bits are explained. For comments, I like to write psudeo-C code where I can. I definitely helps when you can see what you're trying to do right next to the assembly.

[Bruce Abbott]

The Power of 10: Rules for Developing Safety-Critical Code

1. Avoid complex flow constructs, such as goto and recursion.

The NASA study of the Toyota Electronic throttle control firmware found at least 243 violations of these rules.

Toyota used a tool called gstack from Green Hills Software to determine maximum stack size requirements. The tool gstack is a static analyzer that computes an upper bound on the stack size required by a given executable. For the ETCS-i, it reported the maximum possible stack size as 1688 bytes. This result comes with a caveat, however: gstack cannot account for recursion, as stated in its user manual:

gstack cannot work if there are potential direct or indirect recursive calls in the program because it cannot predict how many times the recursion can occur. gstack prints a warning message if it detects a possible recursion in the call graph.

Faced with this limitation, Toyota added an extra margin of safety to the predicted bound by allocating 4096 bytes for the ETCS-i stack—more than double the original prediction. As to why recursion was present in the ETCS-i software, Toyota reported that it was a deliberate design choice in order to simplify the quality assurance process and reduce the total size of the executable...

The flow reveals that the function is actually doubly recursive: It flows from gehdlp_req_1ms to function2, recurses back to function2, and then recurses again back to gehdlp_req_1ms. Toyota engineers confirmed this software recursion. It is not clear what impact recursion has with respect to the larger UA problem. Whether one recursive loop or two, there are other sites of recursion in the ETCS-i that remain unanalyzed.

[westfw]

The point of being good programmer is to write good optimized code which every compiler should  transfer into efficient machine code

I can agree with this (at least, as much as I've quoted of it), and I'm especially amused that we now have people proposing the use of 64bit integers because it leads to faster code using a particular compiler on x86...  :-)

[sasa]

The Power of 10: Rules for Developing Safety-Critical Code

1. Avoid complex flow constructs, such as goto and recursion.

The NASA study of the Toyota Electronic throttle control firmware found at least 243 violations of these rules.

Good point Bruce. But the fact is, that here seems no body works for NASA or at least on sensitive and safety-critical software, I have pointed already in this thread.

[sasa]

The point of being good programmer is to write good optimized code which every compiler should  transfer into efficient machine code

I can agree with this (at least, as much as I've quoted of it),

You have  previously said that you disagree almost 100%

I find not very useful to pull up words and sentences out of context and then comment with opposite opinion. Your, nor anybody reactions "I agree/disagree" will not change a bit in my professional and principle attitudes.

and I'm especially amused that we now have people proposing the use of 64bit integers because it leads to faster code using a particular compiler on x86...  :-)

You imply that I have  proposed exactly that? Not likely...
Seems that you have meant on somebody else, but why you comment in the same sentence and my quote?

[hamster_nz]

and I'm especially amused that we now have people proposing the use of 64bit integers because it leads to faster code using a particular compiler on x86...  :-)

You imply that I have  proposed exactly that? Not likely...
Seems that you have meant on somebody else, but why you comment in the same sentence and my quote?

Don't worry Sasa, that jibe was aimed at me, for daring to play around with functionally equivalent code, just out of idle curiosity.

[John Coloccia]

The Power of 10: Rules for Developing Safety-Critical Code

1. Avoid complex flow constructs, such as goto and recursion.

The NASA study of the Toyota Electronic throttle control firmware found at least 243 violations of these rules.

Good point Bruce. But the fact is, that here seems no body works for NASA or at least on sensitive and safety-critical software, I have pointed already in this thread.

Actually, I work on safety critical software. You seem to make a lot of assumptions about people, or maybe you're intentionally trying to be condescending. Either way, even with safety critical software, you have to write utilities and things that have nothing to do with the software and have nothing to do with safety critical code. For example, I just wrote a utility that grabs the change log for a release out of Mercurial. It's recursive and that's the correct solution.

[Cerebus]

The Power of 10: Rules for Developing Safety-Critical Code

1. Avoid complex flow constructs, such as goto and recursion.

The NASA study of the Toyota Electronic throttle control firmware found at least 243 violations of these rules.

Good point Bruce. But the fact is, that here seems no body works for NASA or at least on sensitive and safety-critical software, I have pointed already in this thread.

I don't get the obsession some people have with NASA as a touchstone. Most of their flight prototypes went KABOOM the first time they were switched on and, as I have previously pointed out, their most infamous programming bug is splattered across the surface of Mars. 

I never programmed for NASA, but I used to have two people working alongside me (Doing AI in FORTRAN, don't ask!) who were moonlighting from their day jobs as programmers at JPL. Their code was nothing to be proud of and quite enough to convince me that there's nothing special about the staff at NASA, they're just as crappy as everybody else.

[Mechatrommer]

The Power of 10: Rules for Developing Safety-Critical Code

1. Avoid complex flow constructs, such as goto and recursion.

The NASA study of the Toyota Electronic throttle control firmware found at least 243 violations of these rules.

Toyota used a tool called gstack from Green Hills Software to determine maximum stack size requirements. The tool gstack is a static analyzer that computes an upper bound on the stack size required by a given executable. For the ETCS-i, it reported the maximum possible stack size as 1688 bytes. This result comes with a caveat, however: gstack cannot account for recursion, as stated in its user manual:

gstack cannot work if there are potential direct or indirect recursive calls in the program because it cannot predict how many times the recursion can occur. gstack prints a warning message if it detects a possible recursion in the call graph.

Faced with this limitation, Toyota added an extra margin of safety to the predicted bound by allocating 4096 bytes for the ETCS-i stack—more than double the original prediction. As to why recursion was present in the ETCS-i software, Toyota reported that it was a deliberate design choice in order to simplify the quality assurance process and reduce the total size of the executable...

The flow reveals that the function is actually doubly recursive: It flows from gehdlp_req_1ms to function2, recurses back to function2, and then recurses again back to gehdlp_req_1ms. Toyota engineers confirmed this software recursion. It is not clear what impact recursion has with respect to the larger UA problem. Whether one recursive loop or two, there are other sites of recursion in the ETCS-i that remain unanalyzed.

the depth of recursion can easily be monitored or limited by

Code: [Select]

void goinsideme(int &depth) {
if (depth < whatever) {
depth++;
goinsideme(depth);
depth--;
} else {
tellmymomma();
};
};

no need fancy and expensive utilities... opps, i forgot this thread is about optimizing tail recursion, sorry. cant help you with that then ...

[NorthGuy]

Code: [Select]

void goinsideme(int &depth) {
if (depth < whatever) {
depth++;
goinsideme(depth);
depth--;
} else {
tellmymomma();
};
};

no need fancy and expensive utilities... opps, i forgot this thread is about optimizing tail recursion, sorry. cant help you with that then ...

If you simplify it a bit, your code will be perfectly suitable for tail recursion optimization 

Code: [Select]

void goinsideme(int depth) {
  if (depth < whatever) {
    goinsideme(depth+1);
  } else {
    tellmymomma();
  }
}

[splin]

the depth of recursion can easily be monitored or limited by

Code: [Select]

void goinsideme(int &depth) {
if (depth < whatever) {
depth++;
goinsideme(depth);
depth--;
} else {
tellmymomma();
};
};

no need fancy and expensive utilities... opps, i forgot this thread is about optimizing tail recursion, sorry. cant help you with that then ...

AutoLandingSystem::AdjustFlightPath(int Altitude, int AirSpeed, int DescentRate, int Thrust, int Pitch)
{
      //Todo: Make sure Flight Manual notes that behaviour is unspecified if altitude exceeds 32767 feet

      if(++RecursionLevel >= MAX_RECURSION_LEVEL)
             throw(TIME_TO_SAY_YOUR_PRAYERS_EXCEPTION);

      //Compute best Landing vector - variables interact so adjust parameters and recompute until error is within bounds
      if(CalcPathError(Altitude, AirSpeed, DescentRate, Thrust, Pitch) > MAX_PATH_ERROR)
              AdjustFlightPath(Altitude, AdjustAirSpeed(AirSpeed), DescentRate, Thrust, Pitch);
     ...

}

[Mechatrommer]

If you simplify it a bit, your code will be perfectly suitable for tail recursion optimization 

yup except it does nothing other than goinsideme, for obvious reason (to get to the point)... tail this...

Code: [Select]


Public Sub QuickSort(a() As Integer, Start As Long, Finish As Long)
    Dim posOfSplitter As Long

    If Finish > Start Then
        Partition a(), Start, Finish, posOfSplitter
        QuickSort a(), Start, posOfSplitter - 1
        QuickSort a(), posOfSplitter + 1, Finish
    End If
End Sub

;Partition() excluded for obvious reason...


AutoLandingSystem::AdjustFlightPath(int Altitude, int AirSpeed, int DescentRate, int Thrust, int Pitch)
{
      //Todo: Make sure Flight Manual notes that behaviour is unspecified if altitude exceeds 32767 feet

      if(++RecursionLevel >= MAX_RECURSION_LEVEL)
             throw(TIME_TO_SAY_YOUR_PRAYERS_EXCEPTION);

      //Compute best Landing vector - variables interact so adjust parameters and recompute until error is within bounds
      if(CalcPathError(Altitude, AirSpeed, DescentRate, Thrust, Pitch) > MAX_PATH_ERROR)
              AdjustFlightPath(Altitude, AdjustAirSpeed(AirSpeed), DescentRate, Thrust, Pitch);
     ...

}

thats why you should not be in avionics business... imho...

[Bruce Abbott]

I don't get the obsession some people have with NASA as a touchstone. Most of their flight prototypes went KABOOM the first time they were switched on and, as I have previously pointed out, their most infamous programming bug is splattered across the surface of Mars.

Not a 'touchstone', but experience we can benefit from. They have learned expensive lessons the hard way.

As (hopefully) did Toyota. Perhaps there was no fault in their code and all the incidents of 'unintended acceleration' were due to user error, but the lawsuit brought to light their unsafe coding practices. Their stack checking tool warned them that it could not account for recursion, so what did they do? Fudged the stack size based on nothing more than pure guesswork. And why did they use recursion? Not because it was the obvious algorithm for the job, but because they were trying to save program memory. They created spaghetti code to save a few bucks, and ended up costing the company billions (and perhaps even killing a few people).       

Toyota's software engineers must have thought they were such awesome coders that the rules didn't apply to them. Maybe they were that awesome, but their code cannot be verified so we will never know if it was safe. That's simply irresponsible, and indefensible.
 

I used to have two people working alongside me (Doing AI in FORTRAN, don't ask!) who were moonlighting from their day jobs as programmers at JPL. Their code was nothing to be proud of and quite enough to convince me that there's nothing special about the staff at NASA, they're just as crappy as everybody else.

NASA needs these rules because their programmers are 'just as crappy as everybody else'. I am not arrogant enough to think that I am better than NASA. Are you?
   

[Bruce Abbott]

the depth of recursion can easily be monitored or limited by

Code: [Select]

void goinsideme(int &depth) {
if (depth < whatever) {
depth++;
goinsideme(depth);
depth--;
} else {
tellmymomma();
};
};

no need fancy and expensive utilities...

You better have something like that, or your code is totally unsafe. But even with it, how do you know how much stack will be used? What about when someone modifies the code without re-calculating it? What if the counter is not properly initialized, or gets corrupted? Can your tools detect these issues? If not then the code is still unsafe.

[Cerebus]

I am not arrogant enough to think that I am better than NASA. Are you?   

Of course I am better than NASA. They are a soulless US federal agency, I am a warm fuzzy human being. 

I suspect the real touchstones for software quality are people we don't even notice, because they just quietly produce stuff that works.

[Mr. Scram]

the depth of recursion can easily be monitored or limited by

Code: [Select]

void goinsideme(int &depth) {
if (depth < whatever) {
depth++;
goinsideme(depth);
depth--;
} else {
tellmymomma();
};
};

no need fancy and expensive utilities... opps, i forgot this thread is about optimizing tail recursion, sorry. cant help you with that then ...

I applied almost exactly that solution. Combined with the fact that the recursion occurred in one specific spot, all was well.

[westfw]

I am not arrogant enough to think that I am better than NASA. Are you?

Did you SEE the code that led to Ariane blowing up?  Where they made their Ada look like Fortran, and redefined "int64" to be a 32bit integer (or something like that)?  (Ok, ESA rather than NASA, but still...)  I'm sure NASA has some very good Fortran programmers, and I'm equally sure that some of their code still looks like Fortran.  (No recursion, no  dynamic allocation.  Perfect!)

[depth checks] You better have something like that, or your code is totally unsafe.

You should totally put limit counts on your iterative loops too!  Which is semi-serious.  I actually had that bug once.)
Seriously: there are well-understood recursive algorithms with well defined depth that shouldn't need additional paranoia.  Our sample printDec() doesn't need a depth check.  Making up an entirely new recursive algorithm is another matter entirely.

[Mechatrommer]

alas i dont think depth check is good enough. its only for catashrophe prevention, not the integrity of the running program. program code should work to its completion imho, if somehow limitation should be imposed on the recursive function, then another strategies should be used such as limiting or divide and conquer the data size to be put into the function, or use equivalent iterative code. as an example of the quick sort above, if depth limitation is activated, the data will not be fully sorted. so, as most wise people said, use it when appropriate vice versa...

no need fancy and expensive utilities...

You better have something like that, or your code is totally unsafe. But even with it, how do you know how much stack will be used? What about when someone modifies the code without re-calculating it? What if the counter is not properly initialized, or gets corrupted? Can your tools detect these issues? If not then the code is still unsafe.

thats why, if its a concern to use recursion in limited resource system, then its better not to use it... if its inevitable, then it need to be tested and the extensiveness of the test will depend on the risk involved, this is where experience and competency come in... ymmv.

[sasa]

You should totally put limit counts on your iterative loops too!  Which is semi-serious. 

Not quite always.

If algorithm is stable, you always know or you can predict almost good enough how much at maximum memory and time you would need for execution, depending on all possible inputs.

If algorithm is not stable - praying that worst case scenario never happens is the best you can do, regardless it is iterative or recursive solution. With recursion you may just hit the roof much faster...

Hopefully, there is many different algorithms in theory and practice...

And BTW, you can count to hit the roof even with stable recursion based algorithm as our small example here is, if use it extensively in  multi-core/multi-thread environment, as someone already mentioned (I think it was user splin).

[brucehoult]

alas i dont think depth check is good enough. its only for catashrophe prevention, not the integrity of the running program. program code should work to its completion imho, if somehow limitation should be imposed on the recursive function, then another strategies should be used such as limiting or divide and conquer the data size to be put into the function, or use equivalent iterative code. as an example of the quick sort above, if depth limitation is activated, the data will not be fully sorted. so, as most wise people said, use it when appropriate vice versa...

That quicksort code was dumb. A small fix makes it safe (with tail call optimization)

Code: [Select]

Public Sub QuickSort(a() As Integer, Start As Long, Finish As Long)
    Dim posOfSplitter As Long

    If Finish > Start Then
        Partition a(), Start, Finish, posOfSplitter
        If posOfSplitter-Start < Finish-posOfSplitter Then
            QuickSort a(), Start, posOfSplitter - 1
            QuickSort a(), posOfSplitter + 1, Finish
        Else
            QuickSort a(), posOfSplitter + 1, Finish
            QuickSort a(), Start, posOfSplitter - 1
        End If
    End If
End Sub

This is guaranteed to use stack less than log2(Finish-Start). Even for a billion items that's no more than 30 levels of recursion i.e. probably less than 1 KB of stack.

[sasa]

This is how I would make basic test app and that is added - I have no more time nor any interest to improve this further.

- Proper testing data distribution over whole range, or range of interest, instead of max 8 decimal digits.

- Proper testings excluding the best and the worst result and giving the mean of the rest.  In real testing case I would add standard deviation information as well, better elapsed time resolution  than ms, but it is anyway a bit better now...

- Possibility to compile and run on embedded systems.

- Added hamster_nz function (sorry, I missed it). Classical example, really fast with many optimization parameters.

- Brucehoult code is disabled, as it missing data pointer and returning pointer(similar to itoc). You may correct it accordingly and add it for testings if you wish.

- Janoc's function is adopted only to return null-terminator pointer in resulted string, in order to be identical to the proposed prototype function (faster writing new converted numbers).

Results are still similar:

O0:

Code: [Select]

itoc_sasa_1       : 2022.00ms Eliminated 2022, 2023 from 5 results
itoc_hamster_nz_1 : 2707.00ms Eliminated 2707, 2708 from 5 results
itoc_NorthGuy_1   : 2959.00ms Eliminated 2959, 2960 from 5 results
itoc_janoc_1      : 3591.00ms Eliminated 3591, 3592 from 5 results

O:

Code: [Select]

itoc_sasa_1       :  879.00ms Eliminated 878, 879 from 5 results
itoc_NorthGuy_1   : 1569.33ms Eliminated 1569, 1570 from 5 results
itoc_hamster_nz_1 : 1695.00ms Eliminated 1695, 1696 from 5 results
itoc_janoc_1      : 1820.67ms Eliminated 1820, 1823 from 5 results

O2:

Code: [Select]

itoc_sasa_1       :  888.00ms Eliminated 888, 888 from 5 results
itoc_janoc_1      : 1053.33ms Eliminated 1053, 1054 from 5 results
itoc_NorthGuy_1   : 1422.00ms Eliminated 1421, 1423 from 5 results
itoc_hamster_nz_1 : 1515.67ms Eliminated 1515, 1516 from 5 results

Os:

Code: [Select]

itoc_sasa_1       : 2175.33ms Eliminated 2175, 2177 from 5 results
itoc_hamster_nz_1 : 3052.00ms Eliminated 3052, 3052 from 5 results
itoc_janoc_1      : 3059.67ms Eliminated 3059, 3060 from 5 results
itoc_NorthGuy_1   : 3087.00ms Eliminated 3086, 3087 from 5 results

Ofast:

Code: [Select]

itoc_sasa_1       :  826.67ms Eliminated 826, 828 from 5 results
itoc_janoc_1      :  951.33ms Eliminated 951, 952 from 5 results
itoc_hamster_nz_1 : 1296.00ms Eliminated 1295, 1297 from 5 results
itoc_NorthGuy_1   : 1422.00ms Eliminated 1422, 1422 from 5 results


[Cerebus]

Go is Algol 68 in a shirt and tie. The shirt has pizza stains down it but you still wear it in a nightclub because the lights are down. It's also an acknowledgement that C was a silly idea all along as it was written by two toked up hippies on an ASR33 and PDP8 trying to write games and accidentally ending up with an OS and compiler and now we need to be serious because the CVE list is make it look like it was a bad idea.

I hope they have "use after free" chiseled on their gravestones.

I finally got a few minutes free and simultaneously remembered that you'd pointed me at go. Both have happened in the last few days, but not together. So I took a look.

Code: [Select]

PROC my conclusion = () VOID:
BEGIN
    PROC i will eat my hat = () VOID: CODE () "Om, nom, nom"; {Algol68RS extension: Assembly code for a theoretical hat eating processor.}

    BOOL go is the new algol 68 = FALSE; {Algol 68 aficionados will appreciate that the mode here is BOOL, not REF BOOL.}

    IF go is the new algol 68 THEN i will eat my hat FI
END

{That ought to be runnable, as long as you've got a HatEater9000 to run it on, but it's been a while since I actually had to feed any Algol 68 into a compiler.}

Not really close, not even first cousins, second or third - maybe.

It's got some merits, but it lacks the rigour and orthogonality that I always found so aesthetically pleasing in Algol 68 and the ultra clean syntax and, last but not least, the option to put (non-significant) spaces in variable names.

Thanks for the heads up anyway.

[Howardlong]

FWIW, my first recursive program was in Algol 60, keyed in on paper tape. It was a key feature that everyone talked about, but mostly failed to find a use for beyond the Fibonacci sequence or calculating factorials. It was quite a key facet of programmer training.

Almost all of my recursion use nowadays isn't a new type of implementation, it's to workaround limitations of a one particular language which architecturally doesn't lend itself well to iterating as it's predominantly set-based. It also makes for excruciatingly difficult code to read, understand and maintain, it's like a stylus coming off a record when you come across it in a peer review. It's a reasonable solution in certain situations given the language limitations, but it's just hard to comprehend when figuring out how it works and any potential problems or limitations it may have in a given use case.

[tggzzz]

FWIW, my first recursive program was in Algol 60, keyed in on paper tape. It was a key feature that everyone talked about, but mostly failed to find a use for beyond the Fibonacci sequence or calculating factorials. It was quite a key facet of programmer training.

Elliott Algol?

Famously Hoare implemented the compiler in 4Kwords (The 803 had an architectural max of 8K) using  a "collection of mutually recursive procedures" using "an explicit stack for recursion". He noted that "Without the Algol 60 concept of recursion, at that time highly controversial, we could not have written this compiler at all".

The 4K/8K  limit should cause those that claim recursion is (without qualification) too complex/inefficient/slow to reconsider their claims.

[bd139]

Go is Algol 68 in a shirt and tie. The shirt has pizza stains down it but you still wear it in a nightclub because the lights are down. It's also an acknowledgement that C was a silly idea all along as it was written by two toked up hippies on an ASR33 and PDP8 trying to write games and accidentally ending up with an OS and compiler and now we need to be serious because the CVE list is make it look like it was a bad idea.

I hope they have "use after free" chiseled on their gravestones.

I finally got a few minutes free and simultaneously remembered that you'd pointed me at go. Both have happened in the last few days, but not together. So I took a look.

Code: [Select]

PROC my conclusion = () VOID:
BEGIN
    PROC i will eat my hat = () VOID: CODE () "Om, nom, nom"; {Algol68RS extension: Assembly code for a theoretical hat eating processor.}

    BOOL go is the new algol 68 = FALSE; {Algol 68 aficionados will appreciate that the mode here is BOOL, not REF BOOL.}

    IF go is the new algol 68 THEN i will eat my hat FI
END

{That ought to be runnable, as long as you've got a HatEater9000 to run it on, but it's been a while since I actually had to feed any Algol 68 into a compiler.}

Not really close, not even first cousins, second or third - maybe.

It's got some merits, but it lacks the rigour and orthogonality that I always found so aesthetically pleasing in Algol 68 and the ultra clean syntax and, last but not least, the option to put (non-significant) spaces in variable names.

Thanks for the heads up anyway.

A detailed comparison...

https://cowlark.com/2009-11-15-go/

[Howardlong]

FWIW, my first recursive program was in Algol 60, keyed in on paper tape. It was a key feature that everyone talked about, but mostly failed to find a use for beyond the Fibonacci sequence or calculating factorials. It was quite a key facet of programmer training.

Elliott Algol?

Famously Hoare implemented the compiler in 4Kwords (The 803 had an architectural max of 8K) using  a "collection of mutually recursive procedures" using "an explicit stack for recursion". He noted that "Without the Algol 60 concept of recursion, at that time highly controversial, we could not have written this compiler at all".

The 4K/8K  limit should cause those that claim recursion is (without qualification) too complex/inefficient/slow to reconsider their claims.

... but those weren't just any words, they were 39 bit words!

The modifier bit was pretty interesting, allowing not only for indirect addressing, but also self-modifying code, used to great effect in the initial instructions.

[sasa]

What is evident is that everyone forced recursion for this integer to string example, gave up after pages and page "proves by testing" that code is faster and compact...

After making real testing values and measuring in proper environment, naturally no one have any further argument to disprove obvious. Perhaps it would be probably "smaller and cleaner" with C interpreter, however compiled, pointer arithmetic and iterative approach is more "natural way" and faster to CPU to execute some simple tasks as this one...

Pretty much waste of time in this thread.

[NorthGuy]

Pretty much waste of time in this thread.

I though the question was not whether it is possible to write a code which executes faster. It is certainly possible to do so without recursion, and it will be even faster if you don't use C at all.

However, the question was whether the recursive code is somehow slower than essentially the same code without recursion. The tests made by brucehoult have proven that the speed is about the same. The result was partly confounded by the fact that the compiler added piles of stack-checking bloat to the non-recursive code, but brucehoult argued that C does what it does and removing the stack bloat would be tweaking. And I agree with that - if you use C you've got to accept the consequences be it bloat  or optimization. But even if brucehoult repeated the tests without bloat, I doubt that the difference would be large. The conclusion would stay.

Your results confirmed this. We didn't see the disassembly, so there's no way to tell what the C compiler did in this case, but your code came remarkably close to most similar version of recursive code posted by janoc both in his and your tests when optimized for speed.

Do you not agree with that conclusion?

[westfw]

everyone forced recursion for this integer to string example, gave up after pages and page "proves by testing" that code is faster and compact...

That's because you were the only one focused on proving "faster and more compact."  Everyone else was content to say "hey, this low-effort recursive implementation was 1) not awful, and 2) actually turned out faster and more compact than that other low-effort iterative implementation.  Also, you switched from "embedded microcontrollers" to x86, which for some reason seems to do a particularly poor job of optimizing this algorithm - and you're correct that if you have to start hunting for special compile switches then it's not worth it.

My (very old - 8088 days, and pre-C compilers) recursive x86 decout looked like:

Code: [Select]

public decout
ten    dw    10
decout    proc near  ;; enter with 16bit value in ax
    xor    dx,dx
    div    ten
    push    dx
    or    ax,ax
    jz    DECOU2
    call    decout
decou2:    pop    ax
    add    al,'0'
    call    typchr
    ret
decout    endp

[sasa]

...
Do you not agree with that conclusion?

Test case provided by brucehoult is definitely wrong.

Results prove only one - good algorithm should never depend on compiler optimization. That is said already many times. As well, this as well imply that results on embedded platform cannot be much different.

I have no time for extensive testings, but compiling with AVR show that janoc's recursive solution is worst 2x in size + stack usage (did not manage to test speed).

BTW. You have made function with infinite loop and continue with finite data - that (and use of labels and goto) are basic examples how code in structured programming should never be written.

@brucehoult You may thanks to anyone many times you want to fight your own lost battles. But at least provide tests in fair conditions and brings fair conclusions next time. At end, never mind, unless your code and suggestion does not cost someone life, health or money...

[NorthGuy]

Results prove only one - good algorithm should never depend on compiler optimization.

I agree. You cannot rely on particular optimization or anything of that sort simply because it may be gone in future versions. However, I don't think this can be proven or disproven. Without a doubt, measuring speed of anything cannot be used as a proof of this statement.

BTW. You have made function with infinite loop and continue with finite data - that (and use of labels and goto) are basic examples how code in structured programming should never be written.

Why? I like using "break" and "continue". It saves lots of time. In this particular loop it doesn't matter, but in some more complex loops, getting out of the loop prematurely with "break" (or eliminating part of the processing with "continue") is very handy. Otherwise, you get lots of nested ifs which are much more messy.

[hamster_nz]

Results prove only one - good algorithm should never depend on compiler optimization.

I agree. You cannot rely on particular optimization or anything of that sort simply because it may be gone in future versions. However, I don't think this can be proven or disproven. Without a doubt, measuring speed of anything cannot be used as a proof of this statement.

BTW. You have made function with infinite loop and continue with finite data - that (and use of labels and goto) are basic examples how code in structured programming should never be written.

Why? I like using "break" and "continue". It saves lots of time.

I find that 'continue' and 'break' are quite agreeable.

I also find goto's are agreeable to handle complex exceptional conditionals - where you might need to free file handles and release memory and so on. I just don't like them so much if the jump out of inner loops.

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

Code: [Select]

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

   file = fopen(filename,"rb")
   if(file == NULL) goto error_cleanup;

   buffer = malloc(buffer_size);
   if(buffer == NULL) goto error_cleanup;

   while(1) {
      if(!read_a_record(file, buffer))
        break;
      if(!record_matches(buffer))
       continue
     do_stuff_with_matching_records(buffer);
   }

   free(buffer);
   fclose(file);
   return SUCCESS;

error_cleanup:
   if(buffer != NULL)  free(buffer);
   if(file != NULL)    fclose(file)
   return FAILURE;
}


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

[brucehoult]

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.

But is that true for random people from the general (intelligent) population who have never been exposed to programming before? Or is it only true for people who have already passed through the filter of "CS101" and learned C/Java/Python?

Don't forget that beginner programming courses all have HUGE dropout rates, despite a lot of effort to understand and change that. Reasoning about assignment and loops is HARD at first, even for people who eventually get it. And many never do.

[brucehoult]

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

I'm not talking about ignoring execution time or efficiency, just reasoning about correctness. You can count the number of operations just as easily with recursive code as with iterative.

[westfw]

I'm not talking about ignoring execution time or efficiency

I wasn't, either.  Although at some point that comes into play, of course.  I mostly meant, oh, "process oriented" vs "data oriented", or something like that.   I wasn't even necessarily including "fast" under "real time" (although perhaps understanding the difference is an example of what I'm talking about.)

I don't have any problem believing that some people are better at one, and other people better at the other...

[brucehoult]

I'm not talking about ignoring execution time or efficiency

I wasn't, either.  Although at some point that comes into play, of course.  I mostly meant, oh, "process oriented" vs "data oriented", or something like that.   I wasn't even necessarily including "fast" under "real time" (although perhaps understanding the difference is an example of what I'm talking about.)

Of course I'm aware that "real time" doesn't mean "fast", but only "known and guaranteed upper bound on response time". That might be microseconds for some applications, but it could equally be minutes or days for other applications.

[sasa]

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


I did not specifically mentioned "while" loop - try on "do - while".

And I would never write such pointless function. Then you make test case around it and specific compiler optimization parameter  - all that is pretty much useless. What is usually used in a loop as a limited factor is a counter as a simplest form, or complex boolean expression. Try with better example, then results and conclusions can be slightly different...

I hope you know that any "while" loop you can turn in "do-while" in assembler quite trivially. Then you will have no unconditional jumps and a bit more compact and faster code. There is no much point for unconditional jump and right after that conditional...

[brucehoult]

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


I did not specifically mentioned "while" loop - try on "do - while".

And I would never write such pointless function. Then you make test case around it and specific compiler optimization parameter  - all that is pretty much useless. What is usually used in a loop as a limited factor is a counter as a simplest form, or complex boolean expression. Try with better example, then results and conclusions can be slightly different...

I hope you know that any "while" loop you can turn in "do-while" in assembler quite trivially. Then you will have no unconditional jumps and a bit more compact and faster code. There is no much point for unconditional jump and right after that conditional...

It would help if you read the posts you reply to.

Did I mention I write compilers for a living? "I hope you know..." indeed. FFS.

[Vtile]

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

My general distaste for programming comes from these illogic mantras parroted around or rather childish fanboyism flooted most online resources. Which both often sound like the arguments we had at the school yard in our snot nose nerd circle. Sorry I needed to put this out.

[NorthGuy]

But is that true for random people from the general (intelligent) population who have never been exposed to programming before? Or is it only true for people who have already passed through the filter of "CS101" and learned C/Java/Python?

I don't think so. At least I haven't heard of any great HDL programmers who would have troubles understanding C.

The paper has been written in 1968. This is almost ten years before I wrote my first program, so I obviously cannot possibly know what were the programming concepts back then. But, I remember I had read a book about Algol-68. I think back then approaches and languages such as Algol-68 were believed to be the future of the programming. People thought that they will be able to create abstract languages (not unlike Algol-68), which will make programming more organized through application of higher abstractions. I have a feeling that the author of the article had similar vision.

As we know now, 50 years later, this vision happened to be incorrect, and programming is best approached not as highly abstracted science, but rather as a down-to-the-earth trade, were languages such as C are the most practical. Thus there cannot be any theoretical rules which would mandate use of recursion or forbid it. As any other tool, recursion gets used where it is called for. And this is all there is to it. Entia non sunt multiplicanda praeter necessitatem.

Don't forget that beginner programming courses all have HUGE dropout rates, despite a lot of effort to understand and change that. Reasoning about assignment and loops is HARD at first, even for people who eventually get it. And many never do.

I don't know about dropout rate statistics, but if you're right, then perhaps programming courses for the beginners do not try to teach basics before they attempt to teach programming. If someone knows how computer memory works, then understanding variables and assignments won't be hard. If you don't explain the concept of memory first then teaching programming will be hard.

[John Coloccia]

I don't know about dropout rate statistics, but if you're right, then perhaps programming courses for the beginners do not try to teach basics before they attempt to teach programming. If someone knows how computer memory works, then understanding variables and assignments won't be hard. If you don't explain the concept of memory first then teaching programming will be hard.

Absolutely, 100% spot on. I couldn't begin to count the number of times I've said that the best way to teach "programming" is to teach how the stupid computer works in the first place. On occasions I've had to tutor, I don't even bother getting to the subject matter until I've gotten through the nuts and bolts of how computers work. Then the rest is EASY.

[westfw]

As we know now ...  programming is best approached not as highly abstracted science, but rather as a down-to-the-earth trade

We know that, do we?
I don't think that I'm very confident that that is an accurate statement!
I'll accept "we've now applied programming to a large set of problems that are not at all abstract."
I'll bet there are more "computer scientists" using abstract languages to solve abstract problems today, than there were in 1968.
And I'm pretty sure that C was influenced by Algol.

[tggzzz]

As we know now ... and programming is best approached not as highly abstracted science, but rather as a down-to-the-earth trade, were languages such as C are the most practical.

Nonsense, from many many points of view.

Almost all people that think they know C, actually don't, since there are far too many undefined and implementation dependent behaviours (let alone standards!).

Thus there cannot be any theoretical rules which would mandate use of recursion or forbid it.

And exactly how does that follow from your assertion?

As any other tool, recursion gets used where it is called for.

Tools are often misused, and recursion is no exception.

[brucehoult]

People thought that they will be able to create abstract languages (not unlike Algol-68), which will make programming more organized through application of higher abstractions. I have a feeling that the author of the article had similar vision.

As we know now, 50 years later, this vision happened to be incorrect, and programming is best approached not as highly abstracted science, but rather as a down-to-the-earth trade, were languages such as C are the most practical.

I think it's more that we get a heck of a lot of mileage out of a few well choosen and documented abstractions, rather than inventing new ones constantly. Things such as "everything is either a block device or a bytestream (and here's how to make one look like the other)", key-value storage, hierarchical namespaces.

I don't know about dropout rate statistics, but if you're right, then perhaps programming courses for the beginners do not try to teach basics before they attempt to teach programming. If someone knows how computer memory works, then understanding variables and assignments won't be hard. If you don't explain the concept of memory first then teaching programming will be hard.

I agree. I believe everyone wanting to learn imperative programming (C, Pascal, Java/C#, Python, ...) should start with assembly level programming. Not on something torturous like PIC or 6502 or even x86. Something where you can document the entire instruction set and programmer's model on two sides of an A4 sheet (which admittedly you can with many 8 but CPUs) AND where you don't have to jump through hoops to manipulate decent sized integers and pointers and function call/return and a stack and struct members etc.

I'd say PDP-11 qualifies, but not PDP-8, Nova, or VAX.

Thumb1 is close, but has too many different instruction formats. You could maybe just not tell them about half of them. ARMv2 has few instruction formats, but the individual instructions are too complex with predication, "free" shifts on one operand, too many addressing modes.

MIPS is good, except for the damned delay slots. But generations of students have used SPIM successfully.

The base RISC-V instructions set is just about ideal. It's something close to MIPS fixed up. Only four instruction formats, simple addressing, no condition codes. The only thing I can really criticise is that immediate constants and branch/load/store offsets are hard to code/decode by hand because they are in multiple fields and scrambled a bit. And the fields don't line up nicely into hex (or octal) digits.

PDP11 was fantastic to program in actual machine code. Five octal digits for opcode, src register, src addressing mode, dst register, dst addressing mode, and one bit left over to indicate byte or word operation (except for add/sub, which shared an opcode). 6502 came close to, with first hex digit indicating the operation and 2nd hex digit indicating the addressing mode.

[Howardlong]

Coincidentally this came up in my Youtube feed today.

  here

[Cerebus]

I agree. I believe everyone wanting to learn imperative programming (C, Pascal, Java/C#, Python, ...) should start with assembly level programming. Not on something torturous like PIC or 6502 or even x86. Something where you can document the entire instruction set and programmer's model on two sides of an A4 sheet (which admittedly you can with many 8 but CPUs) AND where you don't have to jump through hoops to manipulate decent sized integers and pointers and function call/return and a stack and struct members etc.

What you're looking for is CESIL - Computer Education in Schools Initial Language. It's a pseudo assembler designed by a couple of chaps at ICL back in the mid-seventies as part of ICL's planned schools computer educations course (well before it was fashionable to teach computing in schools).

It's a one accumulator machine with a grand total of 14 instructions and a syntax that any assembler programmer would recognise but none of the syntactic features that get in the way of just getting your first program through the assembler without any error messages. It's just enough like a real computer to teach and test understanding of the very basics without any of the distracting details that would make trying to program in assembler as your first ever programming experience a woeful one.

[Howardlong]

I wrote a CESIL interpreter when I was 13 for my homebrew hand-wired computer (a hex keyboard and LEDs were all the I/O it had). It was a very easy thing to write, the language was so simple. Even my maths teacher was impressed, but it took half a lesson to key the interpreter in before you could use it, I didn’t have the luxury of a cassette interface at the time.

[Tom45]

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

Dijkstra's paper predates the C language. In 1967 when he wrote the paper, assembly language, FORTRAN, and COBOL ruled. Algol 60 was more relevant in academia than in industry. Dijkstra's paper couldn't have been a reaction to bad programming using the C language.

I remember when I first heard of Dijkstra's goto paper. I was discussing it with coworkers and we couldn't imagine how it would be possible to do without goto's. But we programmed in assembly and FORTRAN. Neither had support for loop constructs that made the goto statement unnecessary.

After more than a half century I'm still writing software for a living. I can't remember the last time I used a goto statement in a high level language. It has been at least a few decades. I haven't had to try to not use a goto, it just hasn't been necessary. Assembly language is, of course, a different story.

Tom

[brucehoult]

I agree. I believe everyone wanting to learn imperative programming (C, Pascal, Java/C#, Python, ...) should start with assembly level programming. Not on something torturous like PIC or 6502 or even x86. Something where you can document the entire instruction set and programmer's model on two sides of an A4 sheet (which admittedly you can with many 8 but CPUs) AND where you don't have to jump through hoops to manipulate decent sized integers and pointers and function call/return and a stack and struct members etc.

What you're looking for is CESIL - Computer Education in Schools Initial Language. It's a pseudo assembler designed by a couple of chaps at ICL back in the mid-seventies as part of ICL's planned schools computer educations course (well before it was fashionable to teach computing in schools).

No. Not even close.

While something like that might have value for very young students, or for the first one or two lessons, it is far too limited to be useful.

- no subroutines
- no arrays or structs
- no conception of memory as storage locations with addresses

It's pretty much BASIC with worse syntax and all the useful parts taken out.

The worst sin of all -- it doesn't even give you the tools required to build the useful and missing parts yourself!

[Cerebus]

While something like that might have value for very young students, or for the first one or two lessons, it is far too limited to be useful.

- no subroutines
- no arrays or structs
- no conception of memory as storage locations with addresses

It's pretty much BASIC with worse syntax and all the useful parts taken out.

The worst sin of all -- it doesn't even give you the tools required to build the useful and missing parts yourself!

Exactly, it's for the first few lessons where all the other stuff you've just mentioned is just a distraction and contributes to information overload. it's not intended to be useful in itself, it's intended to be useful in introducing, for the first time, what the inside of machine looks like from a programmers perspective. That is exactly the context you were talking about, starting learning to program.

[westfw]

Why would anyone want to change that bootloader - what could it do differently for better or worse, than the one that it comes with ?

Meh.  If you're going to teach assembly language, you ought to at least teach (a subset of) a REAL assembly language.

One of the tenets of the RISC movement might be stated "it doesn't make sense to design a processor with an "elegant" assembler/machine language; you should design the processor to execute code that compilers can emit easily."  So modern cpus tend to be a bit ugly.   But probably, if you're going to teach a subset anyway (you surely don't have time to teach ALL of any architecture as "part of" an introductory class), you can use anything. 
If you want elegace, If the absence of the lovely PDP11 (sigh), I think I'd recommend the MSP430.  ARM or AVR wouldn't be awful.  Shucks, there's probably a useful common subset: load, store, math, branch...

[brucehoult]

Why would anyone want to change that bootloader - what could it do differently for better or worse, than the one that it comes with ?

Meh.  If you're going to teach assembly language, you ought to at least teach (a subset of) a REAL assembly language.

I agree entirely.

I'm also thinking about a different binary coding of a real assembly language such as RISCV to simplify working in raw machine code, but keeping the assembler (and therefore compilers too) compatible.

One of the tenets of the RISC movement might be stated "it doesn't make sense to design a processor with an "elegant" assembler/machine language; you should design the processor to execute code that compilers can emit easily."  So modern cpus tend to be a bit ugly.

I disagree. It's true the original designers of RISC said something along those lines, but it's not like they made things deliberately ugly or something.

Some early RISCs didn't have pipeline interlocks, which meant the programmer needed to think about how long each instruction would take and make sure anything using the result was enough instructions later that the result would be available in time. That's a bit of a chore for the programmer to keep track of, especially if it applies to add/subtract and and/or/xor not only to multiply/divide and memory loads. Two things quickly killed this idea 1) enough transistors became available that pipeline interlocks could be added easily, and 2) CPUs got faster a lot more quickly than memory did, meaning load delays got a LOT longer, and also highly variable depending on whether the load hit in cache or not.

The other thing that happened was some studies indicated that programmers could write a certain number of lines of code in a day, and that number didn't depend on whether they were writing in a high level language or in assembly language. So some designers (most famously VAX) decided to bring assembly language and machine language closer to a high level language. They made it possible to do things such as

Code: [Select]

a[x] = b[y] + c[z] in a single instruction, and also added single instructions to do all the work of function call or return -- saving registers, adjusting stack frames etc. x86 got some of the same philosophy too.

The RISC people said "That's nuts! We can compile

Code: [Select]

a[x] = b[y] + c[z] into four simple instructions (or even seven or ten) and it runs just as fast or faster -- EVEN ON YOUR VAX".

The biggest problem with the RISC way is that the poor old programmer has to find registers to put all the intermediate results in. The VAX has to do that too, but it does it for you, using hidden registers the programmer doesn't know about and can't access.

If you want elegace, If the absence of the lovely PDP11 (sigh), I think I'd recommend the MSP430.  ARM or AVR wouldn't be awful.

Agreed on all of those, with caveats, and indeed I suggested basically the same set of machines.

PDP11 doesn't have enough registers. Only six, effectively (or five if you don't save/restore the link register). In

Code: [Select]

a[x] = b[y] + c[z] that's only enough to hold a, b, c, x, y, z but not the actual data! Need to keep at least some of them in the stack frame. Ugh.  (32 bit x86 has the same problem of course)

MSP430 is basically a PDP11 with twice the registers and half the addressing modes. Usually a good trade-off.

ARM and Thumb I already discussed. Teaching a subset of Thumb1 is I think a good choice, especially as it runs on a huge range of real hardware that people already have or can buy cheaply, from Raspberry Pi to Android to every iPhone before the new models just announced (which I assume are, like iOS 11 everywhere, Aarch64 only). Say, for example, just instruction formats 2, 3, 9, 11, 13, 14, 16, 18, 19 at first (i.e. slightly less than half of them) from page 2 here https://ece.uwaterloo.ca/~ece222/ARM/ARM7-TDMI-manual-pt3.pdf.

That's still a lot more complex than RISCV's effectively four instruction formats.

AVR is good. Lots of registers. Simple instructions. The main problems are it's only 8 bits (making dealing with useful sized numbers or even pointers a pain), and fiddly support for using multiple pointers/arrays at the same time. But the hardware is very cheap and easily available, with excellent tool support.

[westfw]

PDP11 doesn't have enough registers. Only six, effectively (or five if you don't save/restore the link register). In a

• = b[y] + c[z] that's only enough to hold a, b, c, x, y, z but not the actual data!

Don't forget that the PDP11 could operate directly on memory, and its indexed addressing modes could cover the entire address space, so a,b, and c wouldn't usually be in registers, and the data doesn't need to be, either.  (if they WERE pointers, you'd have to do explicit math anyway, since there weren't any double-register addressing modes.)  Your example might assemble to:

Code: [Select]

   mov b(y), a(x)   ; destination on the right, IIRC?
   add c(z), a(x)

it's not like [RISC designers] made things deliberately ugly or something.

Perhaps "deliberately spent no effort on making things pretty" is closer.  The ARM assembly language is one of the ugliest I've ever used (IMO.)