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 min-max function required for this is best implemented using 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 on entry into the function. 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 ultimatley 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

      PROBLEM:

      Write a recursive function to perform multiplication of two positive integers (m and n) using only addition. The function will take as its arguments two integers to multiply together ( m x n ) and will return the product.

      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

      This could be extended to the general case that 
      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:

      Euclids algorithm for calculating the greatest common dividor (GCD) of two positive integers, GCD(m,n) is defined recursively below. The greatest common divisor of two integers is teh largest integer that duvides them both.
      • 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

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

      

      

      ITERATIVE SOLUTION
      

      






      

      


      PROBLEM 3:
      
Write a recursive function to calculate the factorial of n (n!)

      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:
      

      


      
long factorial (int n)
{
        long result;

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

      

      

      

      

      ITERATIVE SOLUTION
      

      

      


      

      

      


      

      
Back to Main Page for Lecture 6