A recursitive procedure is one in which a number of passes, depending the problem itself, are made in order to reach a solution to a problem where the results of the process immediately preceding the process being considered are used to complete the current process.
A famous example of a recursitive procedure is the Fibonacci sequence of numbers whereby an algorithm is used to generate a string of numbers, starting at 0 and 1, where the next number in the sequence is the sum of the two previous numbers. The unending recursitive procedure for producing a Fibonacci sequence:
if (n = 0) (output(n) = 0)
elseif (n = 1) (output(n) = 1)
elseif (output(n) = (output(n-1) + output(n-2))
Result: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, …….
An iterative procedure is one in which a number of loops, depending on the problem itself, are made in order to reach a solution by repeating the same set of instructions on each pass to complete the process. Fibonacci’s sequence, to produce the same results as the recursitive procedure above can be represented as:
n = 0
loop while (n) (
if (n = 0) then (z = 0 AND x = 0 AND y = 1) else (z = x + y)
do (output z)
do (x = y)
do (y = z)
do (n = n + 1)
Result: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, ….
On examining the complexity of each procedure, the recursive procedure takes two processes on each step where as the iterative one takes only one so in this respect and therefore is a more efficient procedure (less complex and less resource hungry).
Conversely, if we took an iterative process to calculate the factorial of any given number (n) the procedure would be written as:
result = 1
if ( n = 0 ) ( result = 1 ) else (
loop while ( n <> 0 )
do (result = result * n)
do (n = n – 1)
do (output result)
Whereas this represented recursitively would be:
result(0) = 1
result(n) = n * result(n-1) for n > 0
As iterative processes tend to be subsets of instructions for recursive processes it is a challenge to quantify which process is more effective in any given situation and this is largely dictated by the value of “n” and the available time and resources. In testing therefore, certainly in the consideration of the Fibonacci sequence it is necessary to provide “n” with a finite value otherwise we have indefinite processes. Whilst recursitive process descriptions often provide a more succinct way of formularising algorithms, they often rely on function calls which are more demanding than iterative steps and so “effectiveness” can only be judged in context and as a result both recursive and iterative ways of dealing with processes are a necessary part of the programmer’s toolkit.
Wikipedia: Fibonacci Number [Online]. Available at: http://en.wikipedia.org/wiki/Fibonacci_number (Accessed 28 November 2009).
Wikipedia: Recursion [Online]. Available at: http://en.wikipedia.org/wiki/Recursion_(computer_science) (Accessed 28 November 2009).