iteration, recursion, optimization, ...

NemoReally

Quote by camel-man

1
1 2 1
1 2 1 2 1
1 2 1 2 1 2 1
1 2 1 2 1 2 1 2 1

I am stumped on how to do this, is it really as easy as it looks?

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

Michael Redei

Quote by NemoReally

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

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:

for n = 1 to 2 do {
... do something with n ...
}

easier to program than

Code:

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 :-)

rcgldr

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).

NemoReally

Quote by Michael Redei

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:

for n = 1 to 2 do {
... do something with n ...
}

easier to program than

Code:

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 :-)

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 ...

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

Michael Redei

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.

rcgldr

Quote by rcgldr

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).

Quote by Michael Redei

By "straightforward" I meant "the way it would be taught in school"

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:



Spoiler


 
  
int i;
char str[1024] = "1";

    for(i = 0; i < 5; i++){
        printf("%s\n", str);
        strcat(str, " 2 1");
    }

OMGCarlos

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.

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:

       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.

Michael Redei

Quote by OMGCarlos

I don't know what this pattern is called:

Code:

       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.

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.

NemoReally

Quote by Michael Redei

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.

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?

(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 ...")

Michael Redei

Quote by NemoReally

Ah, I guess I missed out by not being taught to program ... it was just something we were expected to find out for ourselves.

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

Quote by NemoReally

Why would the more general numeric sequence require 3 loops to be taught (in what respects is 2 loops inadequate?).

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.

Quote by NemoReally

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

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?

OMGCarlos

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:

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

Can be expressed simply as:

Code:

var n = 4, str = '';

while(n--){
    printLine 'a' + str;
    str += ' b a';
}

Whereas the more complex "1, 2, 3, 5, 8, 13, 21...":

Code:

          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:

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).

Michael Redei

Quote by OMGCarlos

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.

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?

rcgldr

Quote by Michael Redei

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?

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.

NemoReally

Quote by OMGCarlos

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:
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.

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'

Quote by Michael Redei

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.

...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.

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

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?

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

(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!))

OMGCarlos

Quote by Michael Redei

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.

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.

Quote by NemoReally

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'

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:

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.

Mark44

Quote by NemoReally

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'

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.

Quote by OMGCarlos

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.

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.

Quote by OMGCarlos

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:

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.

rcgldr

Quote by Mark44

eliminate loops by "unrolling" them.

or partial unrolling of loops such as Duff's device:

http://en.wikipedia.org/wiki/Duff's_device

Similar Threads for: iteration, recursion, optimization, ...
Thread	Forum	Replies
Proving recursion relations. BFGS non linear optimization	Calculus & Beyond Homework	1
Recursion vs. Iteration	Programming & Comp Sci	6
Recursion	General Physics	6
Recursion	General Math	0

rcgldr Recognitions: Homework Help	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).