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

Iteration, recursion, optimization,

  1. Nov 28, 2012 #1
    Actually, it is really as easy as it looks. Paradoxically, it may be helpful to regard it as a special case of:
    1 2 3 ...n 1
    1 2 3 ...n 1 2 3 ...n 1
    1 2 3 ...n 1 2 3 ...n 1 2 3 ...n 1
    1 2 3 ...n 1 2 3 ...n 1 2 3 ...n 1 2 3 ...n 1
    1 2 3 ...n 1 2 3 ...n 1 2 3 ...n 1 2 3 ...n 1 2 3 ...n 1

    which is only marginally more difficult to program but may be easier to think about because it's more general. Look up the C operator "%"

    Here's an example output from a Mathcad function, which is written in 5 (completely invisible and very short) lines

    attachment.php?attachmentid=53413&stc=1&d=1354106454.jpg
     

    Attached Files:

    Last edited: Nov 28, 2012
  2. jcsd
  3. Nov 28, 2012 #2
    Re: Why is this simple output so difficult to code in C

    Producing that the "straightforward" way would require three loops, whereas the special case (121212...) only requires two. So which way to program this depends on whether you find
    Code (Text):
    for n = 1 to 2 do {
    ... do something with n ...
    }
    easier to program than
    Code (Text):
    Do something with 1
    and then do the same thing with 2.
    Still, the three-loop idea does seem interesting, especially for producing christmas-tree-like outputs, if you know people who'd enjoy being sent that kind of a code as a christmas email :-)
     
  4. Nov 28, 2012 #3

    rcgldr

    User Avatar
    Homework Helper

    Re: Why is this simple output so difficult to code in C

    There have already been a couple of single loop solutions posted and later deleted from this thread. Since the OP never replied to this thread, I'm wondering if this is just a "wind-up" (to keep us busy).
     
  5. Nov 28, 2012 #4
    Re: Why is this simple output so difficult to code in C

    Umm ... I suppose that depends upon one's definition of "straightforward". It took 2 loops in Mathcad using an algorithm that should readily port into C. The original can be done in one loop - here's a Mathcad string variant of the original, showing the single loop ...

    attachment.php?attachmentid=53415&stc=1&d=1354112743.jpg

    The "Christmas Tree" effect is due to Mathcad's method of formatting arrays and isn't a programming artifact.
     

    Attached Files:

  6. Nov 28, 2012 #5
    Re: Why is this simple output so difficult to code in C

    By "straightforward" I meant "the way it would be taught in school", and a two-dimensional print-out is ideal for teaching nested loops. This is a subject that you can completely understand with only two loops -- one would be missing the point, and three would be unnecessarily complicated. It's like teaching the concept of "plurals" in language lesons.

    Incidentally, I was one of the posters whose post was deleted. I managed the output with no loop at all, even though it depended on the number of lines. The same is possible for the more general case with lines including 123...n123...n123...n1. But what you'd learn from the technique involved is not the "loop" concept.
     
  7. Nov 28, 2012 #6

    rcgldr

    User Avatar
    Homework Helper

    Re: Why is this simple output so difficult to code in C

    Depends if the goal is to print a pattern of increasing length with just two alternating characters such as:

    a
    a b a
    a b a b a
    ...

    Since the OP has never replied to this thread again, and since it doesn't appear to be homework, I thought it would be OK to include the concept from one of the deleted posts, using C, with spoiler tag:

    Code (Text):
    [spoiler]
    int i;
    char str[1024] = "1";

        for(i = 0; i < 5; i++){
            printf("%s\n", str);
            strcat(str, " 2 1");
        }
    [/spoiler]
     
    Last edited: Nov 28, 2012
  8. Nov 28, 2012 #7
    Re: Why is this simple output so difficult to code in C

    Yes, but if I saw that no-loop solution in the wild I would most likely vomit. If I remember it was still longer than the 1 loop solution, and slower anyways because you were dealing with maps - although it was most certainly a unique solution!

    I don't know what this pattern is called:
    Code (Text):

           1
         1 2 1
       1 2 3 2 1
     1 2 3 5 3 2 1
    ...
     
    but even doing something complex like that is better done with a single loop, both because it would be faster, shorter and more human readable.

    It's all about human readability...speed is the added bonus.
     
  9. Nov 28, 2012 #8
    Re: Why is this simple output so difficult to code in C

    If you put human readability over other matters, you'd probably be best off with two loops rather than one here. Just imagine explaining this pattern to someone over the telephone (so you can't draw pictures for him or wave your hands about). I imagine you'd say something like this:
    • There are lines which increase in length from top to bottom.
    • In each line the numbers increase from 1 to the line number and then decrease back to 1 again.
    Thanks for saying that my no-loop solution was "most unique". Whether such algorithms that use maps are slower or faster than their loop counterparts depends on the kind of language and compiler you're using though. And being able to read and understand them as an idiom of the programming language you're using is just a habit you can learn.

    P.S.: did you really intend the number 5 in the last line of your pattern? If you did, the sequence (1, 2, 3, 5, ...) may need a bit more explaining than my "increase from 1 to the line number" would be offering.
     
  10. Nov 28, 2012 #9
    Re: Why is this simple output so difficult to code in C

    Ah, I guess I missed out by not being taught to program ... it was just something we were expected to find out for ourselves. Why would the more general numeric sequence require 3 loops to be taught (in what respects is 2 loops inadequate?).

    Still, if we're talking classroom, then perhaps we ought to consider introducing recursion?

    attachment.php?attachmentid=53427&stc=1&d=1354145024.jpg

    (My introduction to the PDP-11 and programming: "Excuse me, Dr X, but how can I analyse all this data in time for the next lab?", "Um, ah, err ... there's a computer just outside the lab. I think there's a manual for it somewhere ...")
     

    Attached Files:

  11. Nov 28, 2012 #10
    Re: Why is this simple output so difficult to code in C

    Lucky you. When I learned to program, we weren't expected to do anything, because it wasn't a subject in school.

    I don't know how you used only two loops, and I don't know Mathcad (which is probably the reason why I don't know how you did it). But I do suspect that you used some built-in "listing" function that produces a list or string of the form "12345...n" if you give it an integer n. In C that would require a third loop.

    A notoriously difficult subject to teach, as I know from experience. This "tree" problem we're looking at would be a good example though. Alas, I don't know how to read your Mathcad code, beginning with f(n,v)##\leftarrow## I guess this produces some kind of output, but what do n and v mean here?
     
  12. Nov 28, 2012 #11
    Re: Why is this simple output so difficult to code in C

    Here's a working example in JavaScript (because you can see it online): http://jsfiddle.net/Eg3MC/

    I'm completely self-taught, so I couldn't say how they teach it at school. I'm pretty sure they wouldn't be teaching you recursion in this way however.

    I think you're overcomplicating it. For example, this pattern:
    Code (Text):

           a
         a b a
       a b a b a
     a b a b a b a
    ...
     
    Can be expressed simply as:
    Code (Text):

    var n = 4, str = '';

    while(n--){
        printLine 'a' + str;
        str += ' b a';
    }
     
    Whereas the more complex "1, 2, 3, 5, 8, 13, 21...":
    Code (Text):

              1
            1 2 1
          1 2 3 2 1
        1 2 3 5 3 2 1
      1 2 3 5 8 5 3 2 1
    ...
     
    Can be done like:
    Code (Text):

    var n = 10,          //number of lines to execute
        middle = 2,      //The current middle number
        last = 1,        //last loops middle digit
        old = 0,         //middle digit 2 loops ago
        left = '',       //left half of the string
        right = '';      //Right half of the string

    for(i = 0; i < n; i++){
        //Reverse the left half
        right = left.split(" ").reverse().join(' ');

        //Output the entire line
        $('#tree').append(left + last + ' ' + right + '<br>');

        //Update values
        old = last;
        last = middle;
        middle = last + old;
        left += old.toString() + ' ';
    }​
    PS:
    I'm using JavaScript for the live example just because it's something you can view online. Also I don't know Matchcad either, but I agree, recursion is tricky.

    Oh PPS:
    Michael you're right about the speed differences, the compiler does its own optimization at compile time (I keep thinking in terms of scripting languages like JS).
     
    Last edited: Nov 28, 2012
  13. Nov 28, 2012 #12
    Re: Why is this simple output so difficult to code in C

    Well, I'm also self-taught, but I have taught CS at two German schools (to 16-19-year-olds), so I have some grasp of what concepts are taught and what seem good examples to bring them across. ("Good" = the students understand them and find them meaningful, or even fun.)

    Nested loops are one such concept, and a two-dimensional picture (like our trees) seem a good way to apply it.

    Single loops that "remember" what happend in previous loops are another such concept. Your Javascript programs use this technique, but nowadays global variables are rather frowned upon, so it would need some rather ugly re-writing to be used in school.

    Recursion is also taught, but mostly using the two standard examples, computing factorials (boooring) and the Towers of Hanoi. They're a bit similar to our trees, but more challenging, since the recursive call needs to know the parameters of the current call.

    What I'm thinking about most in this whole discussion is not what's the best way to construct the tree diagram, but what the purpose of the whole exercise is, i.e. what is the student supposed to learn by solving it?
     
  14. Nov 28, 2012 #13

    rcgldr

    User Avatar
    Homework Helper

    Re: Why is this simple output so difficult to code in C

    It's not really a tree structure, but instead a 4 byte pattern of " 2 1" that is appended to a string with each iteration of output. Unlike what the title suggests, producing this output is not difficult to code in C. I'm wondering if the orignal post got the output wrong or if this was even an actual problem from some learning material.
     
  15. Nov 29, 2012 #14
    Re: Why is this simple output so difficult to code in C

    This attitude towards Recursion is one of those things I find puzzling - it's often the most straightforward and natural way to look at a problem. Indeed, there are quite a few problems where I'd go even more loopy (!) than I am if I tried to write an algorithm in standard iterative form - especially if it involves 'work' or 'thinking' :yuck:

    Following on from the above, how is it more challenging? The Mathcad function that I showed the outline for passes information in the arguments.

    attachment.php?attachmentid=53453&stc=1&d=1354204546.jpg

    Without the "student" input, I see it as a cat-skinning exercise o:)

    (The OP may very well know about loops but just have been having a "Doh!" moment or looking for non-existent "traps" in a straightforward problem (been there, done that and worn holes in the T-shirt!))
     

    Attached Files:

  16. Nov 29, 2012 #15
    Re: Why is this simple output so difficult to code in C

    In JavaScript, "var" defines a local variable. Even in other languages, all you would have to do is define local variables - I don't know how this would involve "ugly" re-writing. It might actually even be less code if your language is weakly typed or automatically variables as local.

    I'm a fulltime web developer (at work and for fun), and I can tell you that I rarely see recursion used in the wild outside of iterating through file structures or structures involving "nodes". And I review A LOT of code.

    Why introduce another level of abstraction? It's been said that math is poetry, and code is too (it's even WordPress' slogan)...how can you possibly argue recursion over something like this:
    Code (Text):

    var n = 4, str = '';

    while(n--){
        printLine 'a' + str;
        str += ' b a';
    }
    The reason I said "recursion is tricky" is because it is "trickier" than the alternative. Recursion involves you breaking the logic of the code into functions, passing around variables, and setting up if statements that do exactly what a for...loop does anyways.

    It's more code, it's less readable, and it's slower.

    Recursion is more meaningful when you are "recursively" going through data, not when you are building it. Perhaps in MathCad, recursion is less verbose and easier to read (honestly, I don't know what I'm looking at in your diagram). Recursion has it's uses, and sometimes, it's the only way to solve a problem.

    You don't hammer in nails with a screwdriver...unless of course you don't know where the hammer is.
     
  17. Nov 29, 2012 #16

    Mark44

    Staff: Mentor

    Re: Why is this simple output so difficult to code in C

    Recursion can be a terribly inefficient to go about things, since each recursive call to the function requires saving program state on the stack, such as return address, local variables, and so on. It's not uncommon for a poorly written recursive program (written by a programmer who is averse to thinking) to exhaust stack memory, resulting in the program crashing.

    Speaking of 'work' and 'thinking', programmers generally understand that computers are very stupid machines that can perform calculations very quickly. If the programmer is unwilling or unable to think, he or she is much more likely to cobble together a program that is too slow, not to mention more full of bugs. These aren't "features" that customers are often willing to pay for.
    Years ago, when I was involving in writing a bunch of x86 assembly code, a book that made a strong impression on me was Michael Abrash's "Zen of Assembly." In that book he timed various versions of code to eliminate as many bottlenecks as possible on the hardware of the time. He even went so far as to eliminate loops by "unrolling" them, because of the time cost of starting another iteration, and how that affected the processor pipeline.
     
  18. Nov 30, 2012 #17

    rcgldr

    User Avatar
    Homework Helper

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Iteration, recursion, optimization,
  1. Recursion in C (Replies: 12)

  2. MadGraph optimization (Replies: 4)

Loading...