Recursion | |

Recursion is a topic which is easy to pick up but difficult to master. Recursion is where a function will call itself in order to perform a task. It will always have a loop clause and a terminator. The loop clause will be where the function calls itself The terminator is where it stops. Consider the following recursive algorithm. Can you guess what it is trying to do? Product (value As Integer) If product = 1 then Return 1 Else Return value * Product( value -1) End if End What this code will do is multiply all the values from 1 to value. So if I made the function call product(3) I would get the answer 1 * 2 * 3 = 6. It is possible to write a recursive algorithm as a iterative one. That is, using a for or while loop. Below is the exact same algorithm in its iterative form Dim total As integer= 1 For a =2 to value Total = value * total Next a In this case the iterative version seems to be much simpler to understand. All recursive algorithms can be converted into iterative ones. So the question is why bother with recursion at all? The answer is easy. There are some algorithms which are much more simple and elegant in recursive form than they are in iterative form. More over a lot of algorithms rely heavily on the mechanics of recursion to ensure there efficiency. For example quick sort and binary trees searches. The classic example, which is always used to explain recursion, is factorial. Below is the recursive code for factorial. Factorial of a number, written using a exclamation mark, adds up all of the numbers up to and including the number specified. So 5! = 1 + 2 + 3 + 4 + 5 = 15. Factorial (x as Integer) If x = 1 then Return 1 Else Return x + factorial (x-1) End if end Now it is time to examine how this function is working. In order to fully appreciate recursion it will be necessary to perform a trace through the code. We are going to start off with trying to do 4!. TODO PUT THE EXAMPLE AS A PDF!!!! Factorial(4) was the first function to be called and as such is the last one to finish. It will return the answer of 10. This is correct as 4! = 1 + 2 + 3 + 4 = 10. Notice that it is not until we reach the terminator until we actually start returning values or doing any form of adding up. This is why the terminator is so important. If there was no terminator then the function would keep calling itself and eventually cause the system to crash. A runaway iterative loop will cause the computer to become unresponsive. A runaway recursive method would simply crash. This is due to the stack. |