Recursion vs Iteration

You may have noticed a guide by TDD on iteration in the Delphi programming language. It shows how to perform a basic looping function in a very efficient manner.

Iteration, however, is not the only loop structure allowed in Delphi, and most other programming languages. Lending a functional hand, so to speak, is the idea of recursion. Recursion is a programming concept whereby a function of program calls, or executes, itself. This may seem like an odd concept, but it is easiest to illustrate in brute-force style math programs, such as a factorial program. The following is in Scheme;

Code:

(define (fact n)
    (if (= n 0)
        1
        (* n (fact (- n 1))))

This might seem pretty impenetrable (It might scare the more C/C++/Java-oriented among you, what with all the parenthesi ).

What it does is define a procedure called "fact" (Short for factorial, in our case), which takes the argument "n". "n" is checked to see whether it is equal to 0, and, if it is, it returns 1. If not, it recurses, and here we see where recursion can become confusing, as the expression

Code:

(* n (fact (- n 1)))

reduces down to

Code:

(* n [the result of evaluating fact again, if it is true])

This can quickly become hugely complex to envision, but it can help to imagine a long string of (fact (- n 1)), until we reach the correct answer, when we begin the process of multiplying "n" by each successive answer.

Each time a recursive process calls itself, it stores a copy of itself in memory. In essence, it expands the procedural call. An example;

Code:

(* n (fact (- (* n (fact (- (* n (fact (- n 1))) 1))) 1)))

The above is the example code for the final call, (* n (fact (- n 1))), if we assume "n" = 3.

As you can see, recursion is memory-intensive. It stores the entire loop within itself -- you can expose a flaw of C by creating an infinite recursive loop and watching it crash as it runs out of stack space. A stack is an abstract data type, which stores our instructions to the computer. When it overflows, the program dies and our operating system frees the resources.

Recursion's problem of stack space can be dealt with by using tail recursion, a method of writing your recursion in such a way that the program executes in constant space, ie. it always takes the same amount of memory. This is considered an iterative loop, because the memory required does not increase in line with the number of recursive calls.

Recursive loops, for mathematical functions, are very succinct. An iterative loop would require more explicit tests to be made, in a less orderly fashion, but would be more efficient.

Iteration is much simpler. While recursion pushes the operation onto the stack until it can be popped for execution, iteration simply moves the pointer to where the operation is stored. Consequently, it can be much, much faster, but iterative loops are typically ugly, and do not track their current state. Ackermann functions, tree traversal and Quicksort are all examples of problems which cannot effectively use an iterative solution. Any iterative solution would need to use a stack, lumbering it with the same problems as a recursive solution.

Iterative loops typically look like this (Examples given in C);

Code:

while(condition) {
  action(argument);
}

For loops are a little different.

Code:

for(variable-initialisation;variable-condition;variable-increment/decrement) {
    action(arguments);
}

I hope you've learnt a little from this, and not gotten too lost. Post any problems, inaccuracies and missing information you see from this guide on the thread, and I'll edit it in. Thanks.

 

Great guide, Fascist!

 

This isn't delphi you dumb bitches. Moved.

 

i think its awsome

 

looks good and straight forward. i enjoyed reading this thx

 

great guide 8/10