Re: Recursion?
 

I bet you could simulate a stack on RAM and get one with more size. It would take some work, and you would need to know some asm to do it, but I think it's entirely possible. Rather than using call to jump to the function, which pushes the PC onto the stack, you could just use goto, which just jumps striaght there. Storing variables gets harder though.

I doubt it's worth the effort. Just watch STKPTR<4:0> and make sure your recursive function stops recursing if it sees the stack is near full.

useless commands
 

If we're talking about useless things, might as well hit on the GOTO command. Why use goto for that situation instead of just using a for or while loop or any of their variations (for(;;), while(1), do-while, etc.)? Goto is a useless command. I cannot think of one situation where the taske cannot be better performed with some sort of loop. As far as i know, there has only been one situation found where go must be used to get the desired effect, i.e. break, continue, or loops will not work, and that was discovered by some fulltime programmer who was dedicating his time to finding it. So, to close up a long winded soapboxing, don't use goto.

edit: ok, that's not supposed to be a winking smiley, but a semicolon then a closed parenthesese, just accept it. Smilies.... arggh!

edit #2: as i clicked ok, i realized there was a disable smilies button, so now it works.

Re: Recursion?
 

Break and continue are simply a goto command in disguise. Break and continue should be avoided for the same reasons that goto should. The reason that software engineers really hate goto (and break and continue for that matter) is that it generally makes code harder to read. However, there are times where a well-placed goto can simplify code and make it easier to understand than it would be if you had to wrap it in a bunch of if() or for() statements.



{soapbox}
I work full time as an embedded software engineer, and I still wouldn't feel comfortable making statements like these. While I agree that gotos and recursion are generally a bad practice, I know that there's a nearly infinite amount of software engineering situations that I haven't encountered yet, and one or both of these methods may be the best solution in that situation. I'm very encouraged to see so many young people on this board taking such an interest in engineering (and software engineering in particular), and the amount that you all know about these fields already is amazing. However, do you really feel that you guys have enough experience to back these statements up?

I hope that this post doesn't offend anyone, and if it does I apologize. I am really impressed at the level and intelligence of discussion that occurs on this board. I'm just concerned that the level of misleading information around here seems to be on the rise. There's a lot of teams that are going to go through a bit of a software engineering trial-by-fire this year with the C based controller, and I just don't want to see the situation made worse by providing them with bad information when they come here for help.
{/soapbox}

Re: Recursion?
 

By the way, I didn't mean the C command goto, I was talking about the asm command goto.

In asm the only way of "looping" is with goto's or branches.

I think the idea of goto being bad coding practice comes from BASIC. Programs with large numbers of gotos get incredibly confusing to read, since there really is no flow in the program. The program can just jump to any other point without warning and the reader is left wondering why, especially in BASIC with line numbers and statements like "GOTO 150."

for and while loops help to keep everything structured and easy to follow. Break and continue interrupt that flow, but they made their way into the higher level languages because they are useful and simplify code a lot.

Can you imagine trying to break out of a loop without break? You would need a flag, and all the code after the point you wanted to break from would have to be under an if statement to check to see whether the break flag has been set to true. It could get quite ugly.

Basically, a lot of goto's in a program is probably a bad idea, but they can be useful in certain situations. If you can find a way to do it without goto's that doesn't hurt performance a lot, do it.

Re: Recursion?
 

The reason that recursion is bad is that when it fails your stack overflows, and that is one of the failure modes that result in unpredictable behavior - its very difficult to debug, because the SW simply looses its mind

GOTO statements are bad because a function or subroutine should have one entry point and one exit point - GOTO is used when you dont really know what you are doing- when you havent really worked out the inputs, output and processing that has to happen to get the outputs from the inputs - its an indication that the programmer started writing code BEFORE he figured out what the code had to do (failed to do the high level design work first)

in all the SW programming classes I took, if you used a goto statement, or you used recursion, or self modifying code, you got an automatic F on whatever that code was for, a project, a quiz, or the final exam -

its not something to avoid, its something you should never use - if you cant figure out how to parse your input, or navigate your data structures without using these shortcuts, then you need to go back and work on your data structures and algorythms somemore.

There are HW equivalents too, like gating a clock, using one shot timers, or circuits that can generate glitchs. The shortcut you make is not worth the problems you will have when the system becomes unstable, or crashes, and you have no idea where to start looking for the cause.

Re: Recursion?
 

That depends entirely on what you mean by "better". If you mean using less stack space, then iterative is definately the way to go. If you mean faster running time, then this just simply isn't true. For example, the recursive quicksort procedure is generally significantly faster than it's iterative counter-part[1,2]. Also, for some algorithms it's next to impossible to write an iterative solution (alpha-beta searching, for example).

At the same time, some problems that may seem recursive (towers of hanoi[3], fibonacci, etc), often have much more elegant and faster iterative solutions.

The reality is that sometimes recursive algorithms are better for a task, and sometimes iterative ones are. Learn how and when to use both, and you'll be a much better programmer because of it.

[1] http://www.mathcs.carleton.edu/cours...aj/algory.html
[2] http://www.mvps.org/vb/hardcore/html...equicksort.htm
[3] http://hanoitower.mkolar.org/shortestTHalgo.html

Re: Recursion?
 

And thats why i retracted my previous statement. I try to speak only when i know know what i'm talking about, but please point it out if I or anyone else say something incorrect.

Re: Recursion?
 

(emphasis mine)

Well, sure, generally speaking goto should be avoided. But like in all things, extremities should be avoided, and one must be careful not to avoid doing something merely for the sake of avoiding it. There are some insightful discussions on the internet I will refer everyone to, that can clear up the issue somewhat. Knuth has an interesting paper on the subject, titled Structured Programming with 'go to' Statements:

(please, read on; the quality is somewhat sketchy, though, and bear in mind it was written in the 70s)

And if Knuth isn't a big enough name, Edsger W. Dijkstra has written a paper called Go To Statement Considered Harmful. (And, for those famiar with perl, there is a nice discussion at perlmonks.com).

Just remember that there are different goals in writing programs. Some programs you want to be really fast, while others you want to have a low memory profile, while others still, you want to be very readable. A goto statement might not fit into the "readability" column (and everyone remember that premature optimization is -- indeed -- the root of all evil), but it might make something go faster, which in some cases is a higher objective. You ask whether to use the goto statement? To give the "MIT answer" as my old teacher used to say all too frequently: It depends. I think it is only folly to take away a potentially useful tool from a programmers tool box (sure, the programmer has to pay extra attention to make sure he uses the right tool for the right job ... but that applies everywhere).

Re: Recursion?
 

things that seemed important back in the '70s are no longer an issue for SW. Back in the 70's mainframe computers only had 32 to 64 k (not megs, thousands) bytes of memory

you would be hard pressed to find appications today where memory utilization or processor speeds are really an issue

and in those cases, you dont code in C, you write assembly code for the critical functions.

the greatest expense in SW is debugging and code updates and maintance. Clarity and readability is EVERYTHING.

If you have ever been required to debug someone elses code, or modify it, you will know what Im talking about - goto statements turn your code into spagetti.

I wasnt kidding when I said the SW courses I took in college (6 semisters), you got an automatic F if you used them - there was no recourse or arguing with the professor either - THATS how serious of an issue these shortcuts are.

Re: Recursion?
 

Something like 90% of microprocessors sold are for use in embedded systems. The vast majority of those are still 8 bit. Many embedded systems are still constrained by the same issues as those in the '70s (obvious example: our new robot controller has only 1800 bytes of memory).
Maybe not in the desktop world. Embedded systems are still very concerned about these issues. Code execution speed is still a critical factor for things such as interrupt handlers and device drivers.
Not necessarily true. My above example of device drivers and interrupt handlers are quite often written in C, but still need to execute very quickly. In fact, I'm working with code for a device driver right now that's written in C and makes use of a goto (no, I didn't write it).
Of course. However, if you're trying to make a device that sells for $5 with an embedded processor in it, you may not have the option of using as much RAM as you like or having the fastest processor.
The same would have been true in my software engineering courses. However, that was because all of the problems on those homework assignments and exams could be done cleanly without gotos, and they didn't specify "make this code work in as few cycles as possible."

Re: Recursion?
 

Not that I'm a programmer by any stretch, (the last language I worked with was FORTRAN and not much of that) but it seems to me that college professors are not exactly known for their appreciation of the difficulties of life in the real world. In many cases they live in an ideal world of their own creation, even in software and engineering courses. (Remember "ideal fluids"?) So the strictness of how something is dealt with in school is not necessarily an indicator of its importance in the real world.

Computer languages do not happen by accident. They are constructed to serve specific purposes. Somebody put effort into developing the GOTO command and including it in the language. Since people don't usually do such things without a reason, I would say that there must be a reason for the GOTO to exist. I may not know what it is, and it is certainly not for common use, but I am pretty sure a reason exists.

Re: Recursion?
 

there is another aspect to shortcuts like goto and recursion.

In SW and HW you always want to keep your program sequence and flow control separate from your data processing

gotos and recursion violate that - what I mean is your code should look like

decision statement (will the flollowing code be executed?)
---data processing equation (outputs are a function of inputs)
---equation
---equation
---equation
---equation
---equation
---equation

decision statement (will the following code be executed?)
--- data processing equation (outputs are a function of inputs)
---equation
---equation
---equation
---equation
---equation
---equation
what goto statements do is inject a program flow statement in the middle of the data processing equations - intermixing your data and control leads to nightmares - and there really is no reason for it (which is why the professors would give you an F, there is no excuse)

humans can only think one or two steps ahead at a time - if you have a block of code, with a conditional execution statement at the top, and then two or more conditional exits (gotos) inside the data equations - it becomes impossible to look at the code and understand what its going to do in every case.

I cant put this in the right words, so here is a challenge. Next time you feel tempted to use a goto statement in a high level language, go back to the algorythm or flowchart, or bubble diagram, and figure out what you would have to do to get rid of the goto statement - and you will see how the change makes the code cleaner, simpler, and easier to read and debug.

Re: Recursion?
 

In most cases it is possible to convert any recursive algorithm into an iterative one. See if this is an option if you run out of stack space. An iterative algorithm will never run out of stack space, but may be slower in some cases.

Re: Recursion?
 

Ok.. maybe I should throw my two cents in here just for kicks...

I love goto! :)

LoL... ok, just kidding. Actually, I agree with umm.. some of the people here. Not going to take the time to figure out which ones....

Goto's are good in their place. Excessive use of goto is pointless. However, there are some instances where having a goto is good, the main one being to break out of loops in assembly language. Except we call them "JMP"'s :)

Obviously with higher level languages goto's aren't as necessary because of you have all these fun constructs you can play with to make it work, however, there is always a case where its just very easy to stick a goto in and forget about it.

Remember... programming is about laziness! The only thing that matters in the long run is whether the program actually does what its supposed to do... I'll take a working program with millions of goto's in it and bad programming practice over a non-working program that looks pretty. Of course, after I get the program I'd probably make it look prettier so I can do something constructive with it.... :D

Re: Recursion?
 

Wow... I'm almost speechless. Programming is not about laziness. Whether or not a program does what it is supposed to do is NOT the only thing that matters!!! Please get these notions out of your head. I'm sure you didn't mean it, but saying things like that could be very offensive to those of us who work as software engineers (if it didn't sound so ridiculous, that is).

I really don't know how to address those statements. If you're ever in a position to work on a project that's made up of hundreds of thousands or millions of lines of code you'll understand how absurd those two statements sound.

I'd highly recommend not saying things like that to professors, colleagues, potential employers, or on your resume... :ahh: