Recursion

These pages contain some further examples of recursion and may help those students who undertake the coursework for AI given by Dr Nick Taylor. The minimax function required for this is best implemented using recursion.

Hints from Nick about the minimax function

What is recursion?

Recursion is a technique whereby functions can call themselves. Simple recursive functions always have an if..else type of structure. The condition of the if provides an exit from the recursion and is always tested before the recursive call. If this condition is not true, the else part calls the function again, but this time the value of one of the arguments sent to the function will have changed (typically the value of the variable tested in the condition). The value of the argument is changed in such a manner that ultimately the base condition will be true.

This is explained more easily by considering the following examples. For each problem both a recursive and an iterative solution to the problem are presented - compare the structures of each!

Recursion Examples

	Example 1	Multiplication by repeated addition
	Example 2	Euclids Algorithm for Greatest Common Divisor
	Example 3	Factorial Example
	Example 4	Fibonacci Sequence

PROBLEM:

Hint: consider the following:

6 x 1  =  6
6 x 2  =  6 + (6 x 1)
6 x 3  =  6 + (6 x 2) = 6 + [6 + (6 x 1)] = 6 + 6 + 6

SOLUTION

m x n = m + (m x (n-1))

Therefore, from the above we can repeat the multiplication process by repeatedly calling the function, each time with n decreasing by 1.

The function stops calling itself once n reaches 1. This therefore gives the condition to stop calling the function, since m x 1 is simply m and the result m is returned.

int multiply(int m, int n)
{
	int result;

	if (n == 1)
		result =  m;
	else
		result =  m + multiply(m, n-1);
	return(result);
}

A recursive function always has a structure using an if..else statement. This allows the function to repeatedly call itself, but provides the condition on which to stop.

EXAMPLE OF OPERATION

Consider what would happen if this function is called for m=6 and n=3. The function tests if n is equal to 1, it isn't so

result = 6 + multiply(6,2);

so the function is recalled this time with m = 6 and n = 2. The function tests if n is equal to 1, it isn't so

result = 6 + multiply(6,1);

so the function is recalled this time with m = 6 and n = 1. The function tests if n is equal to 1, it is so it sets

result = 6;

and returns this value. This then completes the statement

result = 6 + multiply(6,1);

providing the value result equal to 12. This value is then returned, and this then completes the statement

result = 6 + multiply(6,2);

and finally the answer of 18 is returned.

ITERATIVE SOLUTION

This problem could also have been tackled using an iterative solution. An iterative solution uses a loop.

int multiply (int m, int n)
{
	int tot =0;

	while ( n > 0O
	{
		tot += m;
		n--;
	}
	return tot;
}

PROBLEM 2:

• GCD(m,n) is n if n<= m and n divides m
• GCD(m,n) is GCD(n,m) if m < n
• GCD(m,n) is GCD(n, remainder of m divided by n) otherwise.

Write a C++ function to implement this algorithm.

SOLUTION

In this case we require an else..if structure because there are 3 possible routes depending on the values of m and n.

1. If n is less than m and n divides m exactly (ie n%m ==0), then we can stop and the answer is n.

2. If m is less than n, then recall the function but swap m and n

3. otherwise, recall function with arguments n and the remainder of m divided by n (m%n)

This is implemented below.

int GCD (int m, int n)
{
	if (n<=m && m%n == 0)
		return n;
	else if (m < n)
		return GCD(n,m);
	else 
		return GCD (n, m%n);
}

PROBLEM 3:

0! = 1
1! = 1
2! = 2 x 1 = 2 x 1!
3! = 3 x 2 x 1 = 3 x 2! 
4! = 4 x 3 x 2 x 1 = 4 x 3! 
5! = 5 x 4 x 3 x 2 x 1 = 5 x 4! 
etc.

n! = n x (n-1)!

SOLUTION:

From the above it is obvious to see a pattern emerging and

n! = n x (n-1)!

Therefore, we can calculate the factorial of n, by multiplying the factorial of n-1 by n. We can calculate the factorial of n-1, by calling the function again, but this time sending it n-1.

This is then repeated since,

(n-1)! = (n-1) x (n-2)!

We want to stop repeatedly calling the function, once n is 0. Hence the condition on the if statement is that the recursion is terminated once n is equal to 0. Otherwise, it recalls the function, but with n-1.

long factorial (int n)
{
        long result;

        if (n==0)
                result = 1;
        else
                result = n * factorial(n-1);
        return(result);
}

ITERATIVE SOLUTION

This could also be implemented iteratively using a loop.

long factorial (int n)
{
	long result;
	int i;

	result = 1;
	for (i=n; i >0 ; i--)
		result *= i;

	return (result);
}

PROBLEM 4:

	1 1 2 3 5 8 13 21 .......

Write a recursive function which returns the nth Fibonacci number (Fn), where n is sent to the function as an argument.

SOLUTION:

The Fibonacci sequence can be generated by repeated calls to the function. We want to keep on calling the function to calculate the 2 previous numbers in the sequence. We want to stop calling the function if n is 1 or n is 2, whereby we know the 1st Fibonacci number (F1) is 1 and the 2nd Fibonacci number (F2) is 1.

int fib (int n)
{
	if (n == 1 || n == 2)
		return 1;
	else
		return (fib(n-1) + fib(n-2));
}

Iterative Solution

This could also have been implemented iteratively as:-

int fib_iterative (int n)
{
	int fib, fib_old1, fib_old2, i;

	if (n <= 2 )
		return 1;
	else
	{
		fib_old1 = 1;
		fib_old2 = 1;
		for (i=3; i <=n; i++)
		{
			fib = fib_old1 + fib_old2;
			fib_old2 = fib_old1;
			fib_old1 = fib;
		}
		return (fib);
	}
}	

Compare this to the Recursive Solution.