Iteration and Recursion

Albert Y. C. Lai, July 12, 2003
trebla [at] vex [dot] net

There are several ways of teaching programming. One way teaches how to execute a program. Another way teaches how to solve a problem.

Looping with variables is very easy to execute by hand. Recursion with parameters is harder to execute by hand, especially when the human is not told about tail-call shortcuts. Most programming courses spend all their time on how to execute if-then-else, how to execute a while loop, and how to execute recursive calls. Therefore looping must look simpler than recursion.

Recursion is more handy in solving problems. To add up 10 numbers, you just have to know how to add up 9 numbers and how to account for the 10th. To find a number in a sorted array of size 16, you just have to know how to find a number in a sorted array of size 8 and how to decide which 8. Solving a problem by divide-and-conquer or reduction is a natural instinct, and we do that all the time, inside or outside programming. In contrast, to solve a problem by looping, the approach is either trial-and-error (which ironically is itself a loop:

0:  clue := empty
1:  P := "while ? do ?"
2:  repeat
3:    P := genetic mutation of P using clue
4:    r := result of executing P 1 time, 2 times, "many" times
5:    d := difference between r and expectation/specification
6:    (* as a result there is always a bug when P is executed 0 times *)
7:    clue := clue U some conjectures made from d
8:  until d is empty
9:  return P
) which is tedious, error-prone, and seldom convergent; or refinement rules based on loop invariants, which is Greek to most people. Writing a working loop is swim-or-sink in education and dark magic in practice.

Unfortunately as an artifact of teaching programming by execution and not problem solving, students do not think of divide-and-conquer when writing a recursion, but rather waste time worrying about how the program will be executed, cornering themselves into resorting to the above trial-and-error method, of which step 4 becomes much harder indeed. So writing a working recursion looks more dark magic due to misguidance.

Also part of article posted to comp.lang.functional (Google copy).

Go to Weblog of Albert Y. C. Lai