Recursion B3.9HR1 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 Multiplication by repeated addition 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;
}
Back to top of page Euclid's Algorithm for Greatest Common Divisor PROBLEM 2: Euclids algorithm for calculating the greatest common divisor (GCD) of two positive integers, GCD(m,n) is defined recursively below. The greatest common divisor of two integers is the largest integer that divides them both. For example, the GCD of 9 and 30 is 3. 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. If n is less than m and n divides m exactly (ie n%m ==0), then we can stop and the answer is n. If m is less than n, then recall the function but swap m and n 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);
}
Back to top of page Factorials 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: 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);
}
Back to top of page Fibonacci Sequence PROBLEM 4: The Fibonacci numbers are generated by adding together the two previous numbers in the sequence, initialising the 1st two numbers (F1 and F2) to 1. The sequence
1 1 2 3 5 8 13 21 .......
is then produced, where F3=F2+F1=2, F4 = F3+F2 =3, F5= F4+F3 = 5 etc. 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. Back to top of page Back to Main Page for Lecture 6
