Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Dec 3, 2014 #1

    Zondrina

    User Avatar
    Homework Helper

    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.

    Code (Text):

    #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.
     
  2. jcsd
  3. Dec 3, 2014 #2

    jedishrfu

    Staff: Mentor

    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.
     
  4. Dec 3, 2014 #3

    jim mcnamara

    User Avatar

    Staff: Mentor

    [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.
     
  5. Dec 3, 2014 #4
    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
     
  6. Dec 3, 2014 #5

    nsaspook

    User Avatar
    Science Advisor

    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") );
     
  7. Dec 3, 2014 #6

    Zondrina

    User Avatar
    Homework Helper

    I would argue there is something to be said about syntactical elegance at least. One line versus ten lines leaves something to be desired.
     
  8. Dec 3, 2014 #7

    nsaspook

    User Avatar
    Science Advisor

    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.
     
  9. Dec 3, 2014 #8

    jedishrfu

    Staff: Mentor

    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.
     
  10. Dec 3, 2014 #9

    Zondrina

    User Avatar
    Homework Helper

    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.
     
  11. Dec 3, 2014 #10

    Mark44

    Staff: Mentor

    I don't really see that there's any advantage in this form:
    Code (Text):
    double power(double x, int n){
      return n == 0 ? 1 : x * power(x, n-1);
    }
    over this one:
    Code (Text):
    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.
     
  12. Dec 3, 2014 #11

    DaveC426913

    User Avatar
    Gold Member

    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.
     
    Last edited: Dec 3, 2014
  13. Dec 3, 2014 #12

    FactChecker

    User Avatar
    Science Advisor
    Gold Member

    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.
     
  14. Dec 3, 2014 #13

    nsaspook

    User Avatar
    Science Advisor

    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.
     
  15. Dec 4, 2014 #14

    Mark44

    Staff: Mentor

    Amen to that...
     
  16. Dec 4, 2014 #15

    FactChecker

    User Avatar
    Science Advisor
    Gold Member

    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.
     
  17. Dec 4, 2014 #16

    Mark44

    Staff: Mentor

    Here's a reason -
     
  18. Dec 4, 2014 #17

    nsaspook

    User Avatar
    Science Advisor

    Using goto is conceptually much easier than proper control structures. Easier should be near the bottom on the list of software engineering principles.
     
  19. Dec 4, 2014 #18
    Agreed 1,000%
     
  20. Dec 4, 2014 #19

    DaveC426913

    User Avatar
    Gold Member

    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?
     
  21. Dec 4, 2014 #20

    jim mcnamara

    User Avatar

    Staff: Mentor

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

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: [C] The usage of ? and : when cleaning up recursive code
  1. Recursion in C (Replies: 12)

Loading...