Recursitive Procedures

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:

procedure RecursiveFibonacci
if (n = 0) (output(n) = 0)
elseif (n = 1) (output(n) = 1)
elseif (output(n) = (output(n-1) + output(n-2))
end procedure

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:

procedure IterativeFibonacci
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)
end loop
end procedure

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:

procedure IterativeFactorial
result = 1
if ( n = 0 ) ( result = 1 ) else (
loop while ( n <> 0 )
do (result = result * n)
do (n = n – 1)
end loop
)
do (output result)
end procedure

Whereas this represented recursitively would be:

procedure RecursiveFactorial
result(0) = 1
result(n) = n * result(n-1) for n > 0
end procedure

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.

References

Glenn, J. (2009) Computer Science: An Overview. 10th ed. Boston: Pearson Education.

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).