Recursions

  1. What is recursion?
  2. Recursion in computer science is a way of thinking about and solving problems. In fact, recursion is one of the central ideas of computer science. Solving a problem using recursion means the solution depends on solutions to smaller instances of the same problem.
  1. C++ programming language supports recursion by allowing one to define a call to a function within the definition of the function itself.
  1. Recursion is often considered the opposite to Iteration; Iteration is where the solution to a problem can be constructed by applying the same method a number of times. (e.g. using a while/for loop)
  1. A simple example:get sum of integers from 1 to n.
  2. Using loop (Iteration solution):

int GetSum(int n)

{

int sum=0;

for (int i=1; i<=n, i++)

sum+=i;

return sum;

}

  1. Recursive solution:

int GetSum(int n)

{

if (n==1) return n;

return n+GetSum(n-1);

}

recursive procedure of GetSum(4):

GetSum(4)

return 4+GetSum(3)

return 3+GetSum(2)

return 2+GetSum(1)

if (1==1) return 1

return 2+1

return 3+3

return 4+6

  1. Another example: Print a C-string reversely. (Note although we know the fixed size of the array, we do not know the length of the C-String.)

e.g. If user input is “Tom”, the output should be “moT”.

aUsing loop:

void PrintReverse(char A[])

{

int count=0;

while (A[count]!=’/0’)

count++;

for (int i=count-1; i>=0; i--)

std::cout<A[i]<’ ’;

}

bRecursive solution:

void PrintReverse(char A[], int s)

{

if (A[s]==’\0’) return;

PrintReverse(A, s+1);

Std::cout<A[s]<’ ‘;

}

  1. Creating recursive solutions:
  2. How to define the problem in terms of a smaller problem of the same type.
  3. How each recursive call reduces the size of the problem.
  4. What instance of the problem can serve as the base case?
  5. As the problem size diminishes, will you reach this base case?
  • Given a problem P:
  • If P is trivial then solve it immediately
  • If P is non-trivial, divide P into subproblems P1 ,..., Pn
  • Observe if Pi (i=1..n) are of the same nature as P
  • If so, use the overall problem solving idea on each of P1 ... Pn
  • Combine solutions of the subproblems P1 ... Pn to a solution of the overall problem P
  1. Examples:

(1)Calculating Factorial of a number (n!)

e.g. 5 factorial (also written as 5!) = 5 * 4 * 3 * 2 * 1 = 120

cUsing loop:

int Factorial(int n)

{

int mul=1;

for (int i=1; i<=n; i++)

mul*=i;

return mul;

}

dRecursive solution:

int Factorial(int n)

{

if (n>0)

return n*Factorial(n-1);

else

return 1;

}

  • With recursive functions we can write an equation called a Recurrence Relation which defines the output of the function in terms of the smaller instances it solves.
  • With the Factorial example the Recurrence relation when n=5 would look like this:

Factorial(5) = 5 * Factorial(4)

= 5 * 4 * Factorial(3)

= 5 * 4 * 3 * Factorial(2)

= 5 * 4 * 3 * 2 * Factorial(1)

= 5 * 4 * 3 * 2 * 1 * Factorial(0)

= 5 * 4 * 3 * 2 * 1 * 1

= 120

(2)Fibonacci Sequence:

0 1 1 2 3 5 8 13 21 …

Suppose we want to calculate the nth number of the Fibonacci Sequence

Where

Fib(n-1) + Fib(n-2) if n > 1

Fib(n) = 1if n=1

0if n=0

e.g. Fib(3) = Fib(2) + Fib(1)

= Fib(1) + Fib(0) + Fib(1)

= 2

  • For this problem (as with many others)–writing the recursive solution is easy – we can pretty much follow the definition of the sequence. Writing the iterative one is a bit more tricky.

aThe Recursive Solution:

int Fib(n)

{

if(n == 1) return 1;

if(n == 0) return 0;

return Fib(n-1) + Fib(n-2);

}

bThe Iterative Solution:

int Fib(n)

{

int previous=0, current=1, next;

if (n==0) return 0;

if (n==1) return 1;

for (int i=2; i=n; i++)

{

next:= current+previous;

previous=current;

current=next;

}

return current;

}

#include <iostream>

//INV.:

//f1 = f(n-2)

//f2 = f(n-1)

//return f(n)

int fib(int n, int f1, int f2)

{

if (n == 0) return f1;

return fib(n-1, f2, f1+f2);

}

int fib(int n)

{

if (n == 0) return 0;

if (n == 1) return 1;

return f(n-1) + f(n-2);

}

int main()

{

for (int i = 0; i < 10; ++i) {

std::cout < fib(i, 0, 1) < " ";

}

std::cout < std::endl;

}

(3)Binary Search: searching one element in a sorted list (static array):

  • Search for an element in an sorted array:
  • Sequential search
  • Binary search
  • Binary search:
  1. Compare the search element with the middle element of the array
  2. If the search element is same as the middle element, return the index of the middle element.
  3. If the search element is less than the middle element, then apply binary search to left half of the array (if not empty) where the search element would be.
  4. If the search element is larger than the middle element, then apply binary search to right half of the array (if not empty) where the search element would be.
  5. If the search element cannot be found in the array, return -1

aRecursive solution:

int BinarySearch(const int data[], int start, int end, int key)

{

mid=(start+end)/2;

if (data[mid]==key) return mid;

else if(start>=end) return -1;

else if (data[mid]<key) return BinarySearch(data, mid+1, end, key);

else return BinarySearch(data, start, mid-1, key);

}

bThe Iterative Solution:

int bsearch(const int data[], int size, int key)

{

int first, last, upper;

first = 0;

last = size - 1;

while (true) {

middle = (first + last) / 2;

if (data[middle] == key)

return middle;

else if (first >= last)

return -1;

else if (key < data[middle])

last = middle - 1;

else

first = middle + 1;

}

}

(4)The Tower of Hanoi:

  • Only one disc could be moved at a time
  • A larger disc must never be stacked above a smaller one
  • One and only one extra needle could be used for intermediate storage of discs

void Hanoi(char source, char destination, char spare, int n)

{

if (n==1)

cout<“move disk ”<n<“from ”<source<“ to ”<destination<endl;

else

{

Hanoi(source, spare, destination, n-1);

cout<“move disk ”<n<“from ”<source<“ to ”<destination<endl;

Hanoi(spare, destination, source, n-1);

}

}

  1. Comparisons between Recursion and Iteration:
  2. However everything that can be computed using iteration can be done using recursion and vice-versa.
  1. As with many other problems, the recursive solution here is less efficient.This is because it takes time and memory to make a function call and the recursive solution here has to recalculate some things many times.

For example if we call Fib(100) – we will end up calling Fib(1) hundreds of times over, however the iterative solution only has to “calculate” the value of Fib(1) once when working out the value of Fib(100).

  1. It is often the case that the Recursive solution is more Elegant (easy to understand, short, etc.) whereas the Iterative one is more Efficient (although not always).
  1. More Examples:

(1)Searching the largest element in an unsorted list (static array):

aUsing loop:

int SearchLargest(int A[], int size)

{

int largest=A[0];

for (int i=1; i<size; i++)

if (largest < A[i])

largest=A[i];

return largest;

}

bRecursive solution 1:

int SearchLargest(int A[], int size)

{

if (size==1)

return A[0];

else

return max{A[size-1], SearchLargest(A, size-1)};

}

cRecursive solution 2:

int SearchLargest(int A[], int start, int end)

{

if (start=end)

return A[start];

else

return max{SearchLargest(A, start, (start+end)/2), SearchLargest(A, (start+end)/2+1, end)};

}

(2)Choosing k balls out of n balls:

Recursive relationship:

C(n-1, k) + C(n-1, k-1) if n > k > 0

C(n,k) = 1 if n = k

1 if k = 0

0 if n k