The recursion and iteration debate

[Aron Silvester]

I've read from various forums and it's no one really has a definite answer to this statement

Statement: "Recursion provides for a more elegant and quicker solution for most problems." This is I think comparing recursion to iteration.

What is your opinion on this? TRUE OR FALSE?

CROSS POST LINK HERE: The recurion and iteration debate

[Les Morgan]

Recursion will produce a much simpler and more elegant coding solution than iteration, in many instances where recursion can be used.

The problem is that recursion is a much more dangerous solution path than iteration: in recursion you have to be able to produce a stopping point or a breakout for workable futility. IMO, most programmers cannot do that. You have to design an algorithm to reign in the infinite to make the recursive call workable. That sounds a lot more simple than it really is--because we have constraints on our physical devices that we have to work with. How many iterations can you do before you get a stack overflow error, or you just simple run out of memory in some other way. Can you guarantee that your implementation will always stay within the confines of its physical domain? Therein is most of the problems using recursion--can you make it halt and can you guarantee you will always be within your resources.

I am biased towards recursion in that I enjoy the elegance of the solutions available, but I am also one who will not champion it with most projects as I cannot guarantee the one designing the algorithm, if it is not me, can sufficiently understand the problems to create a safe solution.

[Paul Clapham]

Aron Silvester wrote:Statement: "Recursion provides for a more elegant and quicker solution for most problems."

If it weren't for the word "most", I would agree with that statement. There are many problems for which it is more elegant and quicker to write a recursive solution than an iterative solution. And if you're a computer science student it may even be true for most of the problems you work on. But in my world most of the problems involve going through an SQL result set and processing each row -- iteratively. Doing that recursively wouldn't be more elegant.

So if you're a student and you're writing (say) an algorithm to go through a tree structure and find its maximum depth, don't hesitate to use a recursive algorithm. Just remember that in real life you will rarely be writing those algorithms, you'll likely be using algorithms written by somebody else and packaged into a library.

[Molayo Decker]

Recursion provides for a more elegant and quicker solution for most problems

I think there are some things problems that iterator can perform simpler than using a recursion. If am preforming complex calculations or trying to sort an array or search a value i think recursion will be the best approach. But if am trying to add values to an array or populate some primitive integers or alphabet in an array i will use iteration.

[Campbell Ritchie]

Les Morgan wrote:. . . in recursion you have to be able to produce a stopping point or a breakout for workable futility. IMO, most programmers cannot do that. . . .

Don't you have to provide a termination point for iteration too? At least an infinite recursion will make its presence felt by throwing exceptions.
You sound very pessimistic about other programmers there. How much evidence do you have for that assertion?

[Winston Gutkowski]

Aron Silvester wrote:What is your opinion on this? TRUE OR FALSE?

I'm going to play the devil's advocate here: FALSE.

There are a few problems for which it definitely makes sense - like Quicksort, or "heaping", or traversing a tree - but many more for which, "elegant" or not, recursive code is insanely difficult to follow (or visualise), and even worse to test.

Maybe it's a bit like 2D and 3D design - some people just "see" things in 3D better than others.
Me: I'm strictly a 2D guy - even after nearly 40 years. Give me a nice flat for loop with a few saved "stacky"-type variables any day.

YM, of course, MV.

Winston

[Jesper de Jong]

Recursion is favoured when you are doing functional programming. Some functional programming languages do not even have loops and the only way to loop through something is by using recursion.

In procedural or imperative programming languages, using loops is the standard way to loop through things.

Note that using recursion can have a performance penalty and other problems. Each time you do a method call, a return address and other data has to be allocated on the call stack. If you go very deep with recursion, so deep that you run out of stack space, you will get a StackOverflowError. This can happen if you recursively try to go over a list with thousands of elements in Java, for example.

Functional programming languages normally have a special optimization to avoid this problem; they can optimize tail calls to avoid allocating stack space for each recursive call. The Java compiler and the JVM however do not have this optimization.

My conclusion is: if you're programming in Java, stick to using loops, and don't use recursion if it's not really necessary, because of performance reasons and the risk of getting a StackOverflowError.

[Campbell Ritchie]

Jesper de Jong wrote:. . . Some functional programming languages do not even have loops and the only way to loop through something is by using recursion. . . .

Some don't even have random‑access lists and any lists are implemented as a cross between a stack and a linked list; those “lists” have another performance overhead that it is only possible to traverse them by recursion.

[Les Morgan]

I have several. I have had a few projects that were "not possible" according to feasibility studies. When a client mentioned one, I took interest--I am always interested in the impossible. I told the client I would do that part of their project for free and not have it take any longer in the timeline. I was a delightful little 50 to 60 lines of code that made the entire project worth doing and gave the client exactly what they wanted in features for the project.

I have been asked by competing consulting firms if they could send someone over to see what I was doing and how a portion of a project functioned--recursion--they could not grasp the concept.

I had a nice little routine in a project what was guaranteed to recurse no more than 10 times, well within the limits of the machines resource limits, but a year later they had to replace it because nobody in their IT/IS department could follow what was going on.

I sent in a small, 20 lines, of code for a programming example once--recursive code from a project--nobody in the interview panel could figure out what it did, even though it was commented heavily, I got the job, but months later one of their upper managers that I became friends with told me that nobody could figure out what or why the code worked, but it did, and their top programmer basically said: "I've not a clue, but it is very obvious that he does."

In my college it was required for CS graduation candidates do consulting in the computer labs--basically field question from the entire school. I chose the CS/EE departments computer labs and fielded question after question on how to implement recursion for assignments. Helped TA's (grad students) figure out problems for programming recursion...

I have been Sr Programmer and Lead developer in many of my jobs... I always do sitdowns with my developers to understand what experiences they have had and what knowledge base they are coming from--very few, even those with degrees, have understood recursion.

I was able to get a small 3 question series inserted into our interview questions for prospective programmers -- this was for all levels of programming, but was right out of the CS 101 books -- and well over 1/2 of the candidates missed all 3 questions. These were the candidates that already received the blessing of the HR department and Admins, basically they were up for a rubber stamp and a I think they can play well with our team type of endorsement. Probably needless to say, we did not hire them. We gave the same test to everyone from just out of college to 12+ years of experience for programmers.

need I go on?

One thing that I have become "enlightened" about: many of the programmers can get buy with just doing what it is that they normally do--basically by wrote--but they really don't know a lot of fundamentals in programming. I am not talking about knowing a language inside and out, but just knowing how to layout a problem and what needs to be done. In almost every where I have worked, I have become known as the "programming smith", not the "language smith", but when someone wants to know how to do something--they often find their way to my office, or in my email, or a phone conversation.

Campbell Ritchie wrote:

Les Morgan wrote:. . . in recursion you have to be able to produce a stopping point or a breakout for workable futility. IMO, most programmers cannot do that. . . .

Don't you have to provide a termination point for iteration too? At least an infinite recursion will make its presence felt by throwing exceptions.
You sound very pessimistic about other programmers there. How much evidence do you have for that assertion?

[Aron Silvester]

Les Morgan wrote:I have several. I have had a few projects that were "not possible" according to feasibility studies. When a client mentioned one, I took interest--I am always interested in the impossible. I told the client I would do that part of their project for free and not have it take any longer in the timeline. I was a delightful little 50 to 60 lines of code that made the entire project worth doing and gave the client exactly what they wanted in features for the project.

I have been asked by competing consulting firms if they could send someone over to see what I was doing and how a portion of a project functioned--recursion--they could not grasp the concept.

I had a nice little routine in a project what was guaranteed to recurse no more than 10 times, well within the limits of the machines resource limits, but a year later they had to replace it because nobody in their IT/IS department could follow what was going on.

I sent in a small, 20 lines, of code for a programming example once--recursive code from a project--nobody in the interview panel could figure out what it did, even though it was commented heavily, I got the job, but months later one of their upper managers that I became friends with told me that nobody could figure out what or why the code worked, but it did, and their top programmer basically said: "I've not a clue, but it is very obvious that he does."

In my college it was required for CS graduation candidates do consulting in the computer labs--basically field question from the entire school. I chose the CS/EE departments computer labs and fielded question after question on how to implement recursion for assignments. Helped TA's (grad students) figure out problems for programming recursion...

I have been Sr Programmer and Lead developer in many of my jobs... I always do sitdowns with my developers to understand what experiences they have had and what knowledge base they are coming from--very few, even those with degrees, have understood recursion.

I was able to get a small 3 question series inserted into our interview questions for prospective programmers -- this was for all levels of programming, but was right out of the CS 101 books -- and well over 1/2 of the candidates missed all 3 questions. These were the candidates that already received the blessing of the HR department and Admins, basically they were up for a rubber stamp and a I think they can play well with our team type of endorsement. Probably needless to say, we did not hire them. We gave the same test to everyone from just out of college to 12+ years of experience for programmers.

need I go on?

One thing that I have become "enlightened" about: many of the programmers can get buy with just doing what it is that they normally do--basically by wrote--but they really don't know a lot of fundamentals in programming. I am not talking about knowing a language inside and out, but just knowing how to layout a problem and what needs to be done. In almost every where I have worked, I have become known as the "programming smith", not the "language smith", but when someone wants to know how to do something--they often find their way to my office, or in my email, or a phone conversation.

Campbell Ritchie wrote:

Les Morgan wrote:. . . in recursion you have to be able to produce a stopping point or a breakout for workable futility. IMO, most programmers cannot do that. . . .

Don't you have to provide a termination point for iteration too? At least an infinite recursion will make its presence felt by throwing exceptions.
You sound very pessimistic about other programmers there. How much evidence do you have for that assertion?

I am now more interested about you than the question I posted. In your post you mentioned about fundamentals, do you think that getting really good and understanding the basic fundamentals of programming has the potential to separate you from majority of the programmers? Is that why you've been dubbed as the "programming smith". Or is it just from thousands of hours coding, or maybe both?

[John Pacuta]

I tried thinking of the simplest recursion vs. iteration I could muster, printing some array values.

//iteration, for any amount of values
public void arrayPrint(int[] values){
  
  for(int i = 0; i < values.length(); i++){
    System.out.println(values[i]);
  }
}

//recursion, for 10 values
int n = 10;
int[] values = new int[n];
public void arrayPrintRecursion(int x){

  if(n > 0){
  System.out.println(values[x]);
  n -= 1;
  arrayPrintRecursion(n);
  }
  
  }

It might not even actually be recursion! But what I do know is that iteration was easy and it felt natural. Maybe recursion will make your execution faster. It is certainly more beautiful. But reusability is so important in code projects, and if I can barely understand my own recursion, how will I understand someone else's? TL;DR: Recursion may be inefficient because it is not as reusable.

[Winston Gutkowski]

Aron Silvester wrote:Or is it just from thousands of hours coding, or maybe both?

According to Peter Norvig, mostly the first; but you definitely have to practise as well.

You also have to spend time thinking. Many beginners make the mistake of thinking that programming is all about coding, and that if they bash away long enough, a solution will somehow eventually materialise. Well, it ain't so.

In order to solve a problem, you first need to understand it. And that involves things like breaking it down, separating responsibilities, and recognising patterns and algorithms. Oddly enough, most programming is not of the type that Les described (his "black magic routine"); it's mundane.

I liken it to playing bridge: You can't be stupid and play the game well; but the guys at the very top (or the "little old ladies" who routinely fleece eager young bucks with the sweetest of smiles) are the ones who do the 'little things' well - they count, they listen, and above all, they don't make mistakes. Squeeze plays and trump coups and smother plays simply don't crop up very often and, while there's a huge satisfaction in getting one right, it's how you play the other 95% of the hands that determines how good you are.

Winston

[Les Morgan]

Aron,
It's more like grace of God and training. I have a high ability to think in the abstract and visualize what is happening. My father was an auto mechanic and as a young child I started working spare time in the family business: about 6 years old. When I started I just did little jobs--washing windows, vacuuming and etc. By the time I was 10 my father, as an exercise, would ask me what I thought was wrong with a car--by the time I was in Jr High (middle school) I was usually right, and by the time I was in High School I was working as a Journeyman level auto mechanic.

What does that have to do with programming? It's trouble shooting in a complex system composed of mechanical, electrical, and fuel systems all combined into a single system. I had to be able to mentally quickly visualize what was happening and make a diagnosis by the noises, vibrations, and smells that the vehicle was making without the ability to inspect closer--time is money and in small business it is the difference between surviving or not.

I studied general engineering and when it came to a class to introduce us to computers, my first programming class, I remember sitting there reading over the first assignment and thinking: "Wow, I really understand what is happening. This is how my brain works. I should probably look into this as a career." When I went to the university I majored in computer science. I consider that people now give me money to play with the computer--I love it!

I am a fundamentalist because it enables me to do the most complex programming quickly and have the system work well and be maintained and modified easily. IMO fundamentals are like to foundation for a building--good foundation; strong house. In programming: strong fundamentals, a bit of imagination, some ability to think in the abstract and voila--people give you money to play with the computer for them.

Aron Silvester wrote:
I am now more interested about you than the question I posted. In your post you mentioned about fundamentals, do you think that getting really good and understanding the basic fundamentals of programming has the potential to separate you from majority of the programmers? Is that why you've been dubbed as the "programming smith". Or is it just from thousands of hours coding, or maybe both?