[C] The usage of ? and : when cleaning up recursive code

[STEMucator]

I noticed some interesting utility in using ? and : when writing some recursive code out of boredom. I thought I'd share some of the code for those interested.

These were written in C, and I must say they simplify a lot of code.

#include <stdio.h>
#include <math.h>

/* Return x raised to the power n for n >= 0. */

double power(double x, int n){
  return n == 0 ? 1 : x * power(x, n-1);
}

/* Return x raised to the power n for n >= 0. This code reduces the recursive calls.*/

double power2(double x, int n){
  return n == 0 ? 1 : n % 2 != 0 ? x * power2(x, n/2) * power2(x, n/2) : power2(x, n/2) * power2(x, n/2);
}

/* Return the number of digits in integer n, n >= 0. */

int num_digits(int n){
  return n < 10 ? 1 : num_digits(n/10) + 1;
}

/* Return the count of the number of times target occurs in the first
 * n elements of array a.
 */

int occurrences(int a[], int n, int target){
  return n <= 0 ? 0 : *(a+n-1) == target ? occurrences(a, n-1, target) + 1 : occurrences(a, n-1, target);
}

Why is there no initiative for this notation? This code surely must run as fast as possible.

 

[jedishrfu]

The C compiler will generate the same executable for this as it would for an if statement. There should be no difference. The ?: ternary operator can also be found in Java. It's equivalent to

If (...Boolean expression...) x=math expression; else x=math expression;

We call it syntactic sugar.

 

[jim mcnamara]

Why is there no initiative for this notation? This code surely must run as fast as possible.

[Speaking about the C language only here]: May not be a good assumption. Each recursion instantiates a new copy of the function. This is the same as calling the function, in terms of overhead. So generally recursion is not a performance booster.

Recursion is wonderful for making code short. short != faster always. Try compiling and profiling your code. Plus you can incur lots stack overhead, going past the OS limit and resulting in a crash. Your code seems simple enough that a crash probably will not happen, but try a recursive heap sort some day. Those are famous for stack overflow.

 

[gsal]

Have you heard of "location...location...location"? (I learn of this when house hunting).

Have you heard of "clarity...clarity...clarity"? Probably not...I just made it up; but you run into this over and over for the last 40 years...that's right, even in Knoth's days, he already had mention that computer time keeps getting cheaper and cheaper, that one needs to worry about the time programmers spend understanding code, meaning, code written by somebody else as, surely, every one of us will run into inherited code that needs to be modified, enhanced, updated, ported, etc...if only everybody programmed with clarity in mind.

Needless to say, I don't find those one-liners very clear...if I found them in a code, I would probably re-wrote them explicitly with nested "if-then-else".

my and a lot of other programmer's 2 cents

 

[nsaspook]

Using the ternary operator is usually not faster than if-else with modern compilers but it simplifies boolean printf statements in debug code.
printf( "%s", (bletch ? "foo" : "bar") );

 

[STEMucator]

I would argue there is something to be said about syntactical elegance at least. One line versus ten lines leaves something to be desired.

 

[nsaspook]

I would argue there is something to be said about syntactical elegance at least. One line versus ten lines leaves something to be desired.

Sure, after semantic clarity. An important human factor in code simplicity is block structure. The compiler doesn't care and will blissfully generate the most incomprehensible and efficient machine code possible from the source code but I do when I have to modify something years later and need to understand a function quickly.

 

[jedishrfu]

Another point is code maintenance:

If someone uses the ?: operator and later you must amend the code with a more complicated form then you may be forced to go to the block if statement format.

But you used the block if from the start then its an easy matter to add your changes and easier for someone to review your changes before they get into production code.

 

[STEMucator]

Guys. The point of the code is to display how : and ? are useful when writing recursive functions. If there was some "more complicated form" maybe I would've written some different code then, possibly with block statements, but that's redundant and off topic.

As for semantic clarity, if we both understand the same thing, then who cares anyway right?

I understand there is some '¿simplicity?' in writing block statements, but how do you measure simplicity anyway? Seems pretty abstract up to the individual.

 

[Mark44]

Guys. The point of the code is to display how : and ? are useful when writing recursive functions.
If there was some "more complicated form" maybe I would've written some different code then, possibly with block statements, but that's redundant and off topic.

As for semantic clarity, if we both understand the same thing, then who cares anyway right?

I understand there is some '¿simplicity?' in writing block statements, but how do you measure simplicity anyway? Seems pretty abstract up to the individual.

I don't really see that there's any advantage in this form:

double power(double x, int n){
  return n == 0 ? 1 : x * power(x, n-1);
}

over this one:

double power(double x, int n){
   if (n == 0) return 1;
   else return x * power(x, n-1);
}

The latter takes one more line of code, which is pretty much a meaningless measure. I would argue that the latter form is simpler in the sense that it is more easily comprehended by human readers, which is something that could be measured if someone were ambitious enough to do so.

The most compelling reason to use the ternary operator, IMO, is in print statements where a boolean expression can control which of two strings gets printed, including the possibility that one of them is an empty string.

 

[DaveC426913]

Assuming performance is similar, blocks of code would do well to mimic how readers (programmers) conceptualize the tasks.

If a conditional really is conceptually a single task: "print this or that" then use the ternary. One task, one line.

But if the there is a two tasks that are conceptually different depending on a condition: "if this, do these things, otherwise do a different thing", use the block form. Multiple tasks, multiple lines.

Mark44's power() example above is most definitely of the latter type. There are two distinct tasks; the code should reflect that. It tells the programmer what's happening in a spatially visual way with a minimum of brain cycles. They don't have to read every character in the line to grasp the flow.

 

[FactChecker]

There is no functional advantage to the ? : form. It has no advantage in recursion; however, it is useful when there are a lot of simple repetitive conditional lines. It happens more than you might think. But there is a real danger that the code and logic will get more and more complicated, leading to one-line monstrosities. I have personally encountered single lines of code with "? :" conditions nested 15 or 20 conditions deep. I had to write parsing programs to format and comment the nested conditions in a way that I could understand.

 

[nsaspook]

I would also say don't use recursion unless its really needed. There is always another way that's better and most safety related programming coding rules like MISRA-C ban direct or indirect recursion.

 

[Mark44]

I would also say don't use recursion unless its really needed.

Amen to that...

 

[FactChecker]

I would also say don't use recursion unless its really needed. There is always another way that's better and most safety related programming coding rules like MISRA-C ban direct or indirect recursion.

There are algorithms that are conceptually much easier to implement using recursion. If safety is not an issue, there is no reason to avoid regression in any language that supports it.

 

[Mark44]

There are algorithms that are conceptually much easier to implement using recursion. If safety is not an issue, there is no reason to avoid regression in any language that supports it.

Here's a reason -

Recursion is wonderful for making code short. short != faster always. ... Plus you can incur lots stack overhead, going past the OS limit and resulting in a crash.

 

[nsaspook]

There are algorithms that are conceptually much easier to implement using recursion.

Using goto is conceptually much easier than proper control structures. Easier should be near the bottom on the list of software engineering principles.

 

[elusiveshame]

Using goto is conceptually much easier than proper control structures. Easier should be near the bottom on the list of software engineering principles.

Agreed 1,000%

 

[DaveC426913]

Using goto is conceptually much easier than proper control structures. Easier should be near the bottom on the list of software engineering principles.

Virtually every poster has stated implicitly or explicitly such things as 'functionally the same', or 'without loss of performance' or ' without compromise of safety'. As programmers, these are givens (yet we all still stated them anyway, because we're like that).

But if it's not obvious to some non-programmers, then I'll restate the question making explicit the conditions we all know:

What is the better way (if at all) of coding a block such as this obviously barring loss of performance and unsafe techniques?

 

[jim mcnamara]

We should be helpful here, too; I did not mention this before, my bad:
This code does not return anything useful:

double power(double x, int n){
  return n == 0 ? 1 : x * power(x, n-1);
}

It returns 1 on success. Not a double. How would you change the function to make it do what seems to be implied.

 

[nsaspook]

Virtually every poster has stated implicitly or explicitly such things as 'functionally the same', or 'without loss of performance' or ' without compromise of safety'. As programmers, these are givens (yet we all still stated them anyway, because we're like that).

I really wonder how much of a 'given' that is today in C with the design of new languages that restrict the level of expression to some 'safe' sandbox with a parachute to save you from design and coding errors. There's a reason why certain language constructs in C are forbidden, restricted or are unwise to use in other programming languages. Programmers used and abused them in C as hat-tricks with sometimes horrible results.

 

[Mark44]

We should be helpful here, too; I did not mention this before, my bad:
This code does not return anything useful:

double power(double x, int n){
  return n == 0 ? 1 : x * power(x, n-1);
}

It returns 1 on success. Not a double. How would you change the function to make it do what seems to be implied.

Actually, it does return a double. The (int) 1 in the return statement will get promoted to a double.

 

[FactChecker]

Using goto is conceptually much easier than proper control structures. Easier should be near the bottom on the list of software engineering principles.

There are reasons that many algorithms and mathematical proofs are recursive and/or inductive. I would say that there are some very easy recursive algorithms that are almost impossible, and certainly impractical, to do without recursion. Furthermore, maintaining and testing the recursion version is orders of magnitude easier.

 

[mafagafo]

There is no functional advantage to the ? : form. It has no advantage in recursion; however, it is useful when there are a lot of simple repetitive conditional lines. It happens more than you might think. But there is a real danger that the code and logic will get more and more complicated, leading to one-line monstrosities. I have personally encountered single lines of code with "? :" conditions nested 15 or 20 conditions deep. I had to write parsing programs to format and comment the nested conditions in a way that I could understand.

I am one of the guys that like to write those 15 ternaries / 300 characters per line.
*Raise digital shield.*

We should be helpful here, too; I did not mention this before, my bad:
This code does not return anything useful:

double power(double x, int n){
  return n == 0 ? 1 : x * power(x, n-1);
}

It returns 1 on success. Not a double. How would you change the function to make it do what seems to be implied.

I think you missed a '?'.

Spoiler: My code (NOT A C programmer)

double power(double base, unsigned int exponent) { // this is just going to work for n >= 0 anyways, may as well make it clear.
                                                   // better names for the variables
                                                   // over 80 per line, what I think is standard for C.
  return n == 0 ? 1.0 : x * power(x, n - 1); // spaces before and after the minus sign calm my eyes.
}

 

[FactChecker]

I am one of the guys that like to write those 15 ternaries / 300 characters per line.

Ha! Well, everyone has to have a hobby. I checked my notes and I was not quite correct. They were logic statements without '?:' phrases. But the longest was 345 characters. If not you, maybe it was a relative who did it?

 

[jim mcnamara]

Actually, it does return a double. The (int) 1 in the return statement will get promoted to a double.

You are correct - I meant x, what is point of all those gyrations to return a 1 (double or not)? I thought the function implied it was calculating some value to a power of n.

 

[nsaspook]

There are reasons that many algorithms and mathematical proofs are recursive and/or inductive. I would say that there are some very easy recursive algorithms that are almost impossible, and certainly impractical, to do without recursion. Furthermore, maintaining and testing the recursion version is orders of magnitude easier.

Just like goto there are reasons to use recursion like filesystem traversal but you never need (by using an explicit stack and proper data structures) recursion in C and it is preferable (from an embedded and systems programmers point of view) not to use it unnecessarily due to stack overhead and function call slowness instead of iteration.

 

[mafagafo]

Ha! Well, everyone has to have a hobby. I checked my notes and I was not quite correct. They were logic statements without '?:' phrases. But the longest was 345 characters. If not you, maybe it was a relative who did it?

My teacher, maybe. In order to reduce the repository and source size we avoid the useless '\n'.

"if " + " else " = 9 characters!
" ? " + " : " = 6 characters! WAY BETTER!

You can use the ternary operator 3 times by the cost of 2 if-then-else! It's all about the bits.

 

[Mark44]

You are correct - I meant x, what is point of all those gyrations to return a 1 (double or not)? I thought the function implied it was calculating some value to a power of n.

That's exactly what it does. If the exponent is 0, the function returns 1. If the exponent is an int larger than 0, the function calls itself using an exponent that is decremented by 1.

 

[Mark44]

My teacher, maybe. In order to reduce the repository and source size we avoid the useless '\n'.

"if " + " else " = 9 characters!
" ? " + " : " = 6 characters! WAY BETTER!

You can use the ternary operator 3 times by the cost of 2 if-then-else! It's all about the bits.

This is a very silly reason. To save a few bytes of storage, you're dramatically decreasing the readability of your code, which makes it much more difficult for the poor schlub who has to maintain your code. That's a bad tradeoff, especially when RAM is so cheap. I just bought a 32 GB zip drive for about $30.

 

[mafagafo]

You are correct - I meant x, what is point of all those gyrations to return a 1 (double or not)? I thought the function implied it was calculating some value to a power of n.

$$x^n = \prod_{i=1}^{n}{x} = \underbrace{x \cdot x \cdot x \cdot \ldots \cdot x}_\text{n times}$$
The function calls itself $n$ times.

This is a very silly reason. To save a few bytes of storage, you're dramatically decreasing the readability of your code, which makes it much more difficult for the poor schlub who has to maintain your code. That's a bad tradeoff, especially when RAM is so cheap. I just bought a 32 GB zip drive for about $30.

It was a joke. Either you are being sarcastic (if so, +1 for you) or you are really bad at getting it. See the post I replied to.

 

[Mark44]

This is a very silly reason. To save a few bytes of storage, you're dramatically decreasing the readability of your code, which makes it much more difficult for the poor schlub who has to maintain your code. That's a bad tradeoff, especially when RAM is so cheap. I just bought a 32 GB zip drive for about $30.

It was a joke. Either you are being sarcastic (if so, +1 for you) or you are really bad at getting it. See the post I replied to.

No sarcasm - I didn't pick up that you were joking. It's harder to pick up subtleties on the interwebz than in face-to-face conversations where you can see other cues. When people are writing tongue-in-cheek on the Net, they often use smileys to send that cue - :D

 

[mafagafo]

People don't get my sarcasm in real life either. It is not a novelty, I just don't want you or anyone else getting serious about s*** I say.

Unless you are on a machine where your secondary s. cap. is < 8 MB, counting bits is unnecessary.

I think that some embedded stuff also ship the source, in that case reducing size to the extreme be needed (but there are better ways to achieve it than replacing if-then-else by ternaries).

Don't like the smileys. See the one you used? 137 bytes. Keep killing the planet we live in.

 

[jedishrfu]

Your return when n=0 should be 1.0 since the function returns doubles.

As far as computing the nth power of a variable, it looks correct otherwise.

y=power(2.0,1)
n=1 --> 2.0*power(2.0,0)
n=0 --> 2.0*1.0
y=2.0

 

[mafagafo]

Your return when n=0 should be 1.0 since the function returns doubles.

As far as computing the nth power of a variable, it looks correct otherwise.

y=power(2.0,1)
n=1 --> 2.0*power(2.0,0)
n=0 --> 2.0*1.0
y=2.0

See my version. What you pointed out was "corrected" there.

Returning 1 instead of 1.0 is UGLY, not WRONG. (#22 explains why)