Monday, 28 October 2013

Recursion

If a function, procedure or program calls itself, this is known as recursion.

Recursion can be used to solve problems which use a tree-search algorithm. If you look at my solutions to the eight queens problem and the knight's tour, you will see that I solved them without using recursion. If I had used recursion, the solutions may have been easier to implement.

It is a feature you have to use with care because, if you have an error in your recursive logic, your code might call itself indefinitely. If this happens, it is only a matter of time before all your machine's memory is used up and this might make it fall over.

Some languages e.g. BASIC and COBOL do not support recursion but it is allowed in C as you can see in the example below.

A global variable called counter is set to 1. Then a function called recursive_function is executed. This displays the value of counter, adds 1 to it then, as long as counter is less than 6, the function calls itself again:

UBUNTU: cat test6.c
#include <stdio.h>
int counter=1;
void recursive_function();
main()
{
recursive_function();
}
void recursive_function()
{
printf("Entered recursive_function\n");
printf("Counter = %d\n",counter);
counter++;
if (counter<6)
  recursive_function();
}
UBUNTU: cc test6.c -o test6
UBUNTU: ./test6
Entered recursive_function
Counter = 1
Entered recursive_function
Counter = 2
Entered recursive_function
Counter = 3
Entered recursive_function
Counter = 4
Entered recursive_function
Counter = 5
UBUNTU:

No comments: