22. Recursion

A very efficient way of programming is to make the same function work over and over again in order to complete a task.

One way of doing this is to use 'Recursion'.

Recursion is where a function or sub-routine calls itself as part of the overall process. Some kind of limit is built in to the function so that recursion ends when a certain condition is met.

A classic computer programming problem that make clever use of recursion is to find the factorial of a number. i.e. 4 factorial is 4! = 4 x 3 x 2 x 1

Example

Find factorial 3!. The mathematical symbol for factorial is exclamation mark '!'

A function to find the factorial of a number is shown below

fct(n) {
if  (n==0) {
    fct = 1
} else {
    fct = n * fct(n-1)
  }
}    
       

Notice that the function 'fct' above is calling itself within the code. Also notice that each time the function is called, a test is being carried out (if n==0) to see if the recursion should end.

To start it off the following statement is written

p = fct(3)

Step by step, this is what happens

The factorial function is called with argument 3

• 3 is passed as an argument to the factorial function 'fct'
• the test (if n==0) is false and so the else statement is executed
• the statement fct = n * fct(n-1) becomes
• fct = 3 * fct(2)
• In order to resolve this another call is made to factorial with argument 2 this time
• RECURSION happens i.e. the function is calling itself as fct(2)
• 2 is passed as an argument to the factorial function 'fct'
• the test (if n==0) is false and so the else statement is executed
• the statement fct = n * fct(2-1) becomes
• fct = 2 * fctl(1)
• In order to resolve this another call is made to factorial with argument 1 this time
• RECURSION happens i.e. the function is calling itself as fct(1)
• 1 is passed as an argument to the factorial function 'fct'
• the test (if n==0) is false and so the else statement is executed
• the statement fct = n * factorial(1-1) becomes
• fct = 1 * fct(0)
• In order to resolve this another call is made to factorial with argument 0 this time
• RECURSION happens i.e. the function is calling itself as fctl(0)
• the test (if n==0) is TRUE and so the value 1 is returned to the calling function
• now each function call returns a value to the previous one, until the first function called returns a value to 'p'.

Advantage of recursion

• Very efficient use of code

Disadvantage of recursion

• A faulty recursive function would never end and would rapidly run out of memory or result in a stack overflow thus causing the computer to freeze.
• Can be difficult to debug as it can fail many levels deep in the recursion
• Makes heavy use of the stack, which is a very limited resource compared to normal memory.