Recursion What is Recursion?

Execution trace and variable allocation of a recursive procedure

• Example: To sum the integers from 1 to n.
• We define a function, sum(n), that can call itself:
• If n = 1, sum(n) = 1.
• If n > 1, sum(n) = n + sum(n-1).

• Thus, a problem of magnitude n is reduced to a problem of magnitude (n-1). This can be continued until we reach the “base case”: a problem of magnitude 1, which can be solved directly.

• Execution Trace

• v:=sum(3);

• v:=sum(3);

• sum:=3+sum(2);
• end;

• {

• v:=sum(3);

• sum:=3+sum(2);
• end;

• {

• v:=sum(3);

• v:=sum(3);

• v:=6;

• v:=sum(3);

• sum:=3+sum(2);
• end;

• {

• sum:=3+sum(2);
• end;

• {

• sum:=3+3;
• end;

• {

• sum:=2+sum(1);
• end;

• {

• sum:=2+sum(1);
• end;

• {

• {

• sum:=1;
• end;

• {

• sum:=2+1;
• end;

• Variable Allocation

• v=sum(3)
• sum:=3+sum(2)
• sum:=2+sum(1)
• sum:=1
• sum:=3
• sum:=6

sum?	sum?
n 3	n 2

sum?	sum?	sum?
n 3	n 2	n 1

sum?	sum?	sum?
n 3	n 2	n 1

sum?	sum?
n 3	n 2

sum?

n 3

sum?

n 3

There are four elements of any recursive procedure

• 1. Termination condition (or base case)
• In the example of n factorial, the termination condition is “when n=1”. There may be more than one condition or case, but there will be at least one for which the answer is known.
• Termination case value (or base case value)
• This is the value of the termination case. In our example, it is 1.

Recursion expression

• Recursion expression
• It is somehow simpler.
• If recursion is to ultimately fins a value, the simpler case must ultimately be one of the termination case.
• In the n! example, given that n is initially a positive integer greater than 1, then (n-1)! is closer to 1! And therefore a simpler case
• After-computation expression involving the recursive expression
• Given the value of the simpler case, then there is some computation to compute the current case. In the n! example, once we have (n-1)! We multiply it by n.
• Thus, the expression involving the recursive expression is: n*(n-1)!

Well-founded Recursion

• Without the base case, there can be no final definition and the recursion is infinite:
• E.g., without the base case
• public int factorial ( int n )
• {
• return ( n * factorial(n – 1));
• }
• factorial(5), for example, doesn’t terminate
• This is called not well-founded

Convergent Recursion

• If the recursive step does not move towards the base case, the recursion is infinite
• E.g., with the definition as before
• public int factorial ( int n )
• {
• if (n == 0)
• return 1;
• else
• return ( n * factorial(n – 1));
• }
• factorial(-5), for example, doesn’t terminate
• This is called divergent recursion

• Therefore, there is an implicit pre-condition on this method:
• // pre: n >= 0

Recursion Example

• Factorial:
• factorial n can be defined in terms of factorial of n – 1
• I.e., assuming there exists some way of calculating fact(n-1), we can calculate fact(n):
• fact(n) = n * fact(n-1)
• So, factorial can be defined in terms of itself!

Recursive Definition of Factorial

• n! = n*(n-1)!, if n>0
• n! = 1, if n=0

• Notice the recursive definition comes in two parts:
• the recursive part and the trivial part (base case)
• Recursion is logically equivalent to mathematical induction.
• For background material, consult your Discrete Maths text on induction and/or recursion.

Recursive Factorial in Java

• public int factorial ( int n )
• {
• if ( n == 0 )
• return 1;
• else
• return n * factorial(n-1);
• }

• n = 3
• result = 6

• n = 2
• result = 2

• n = 1
• result = 1

• n = 0
• result = 1

More Recursion

• Problem: calculate the sum of an array of integers
• Familiar loop solution:
• public int sumArray ( int [ ] a )
• {
• int sum = 0;
• for ( int i = 0; i < a.length; i++)
• sum = sum + a[ i ];
• return sum;
• }

• sum {2, 7, 3, 5, 11}
• = 2 + 7 + 3 + 5 + 11
• But,
• sum {7, 3, 5, 11}
• = 7 + 3 + 5 + 11
• I.e.,
• sum { 2, 7, 3, 5, 11}
• = 2 + sum {7, 3, 5, 11}
• = 7 + sum {3, 5, 11}
• = 3 + sum {5, 11}
• …

More Recursion

• So,
• sum {2, 7, 3, 5, 11} can be defined in terms of sum {7, 3, 5, 11}
• I.e., assuming there is a way of calculating sum {7, 3, 5, 11}, we can calculate sum {2, 7, 3, 5, 11}:
• sum {2, 7, 3, 5, 11} = 2 + sum {7, 3, 5, 11}
• So, sum can be defined in terms of itself

Array Sum Recursion

• The sum of the elements in an array
• Let S( i ) represent the sum of the elements in the array from position 0 up to and including position i.
• Then,
• S(0) = a[0]
• S(1) = a[0] + a[1] = S(0) + a[1]
• S(2) = a[0] + a[1] + a[2] = S(1) + a[2]
• :
• S(i) = a[0] + … + a[i] = S(i – 1) + a[i]

Array Sum Recursion

• Recursive definition of S( i ):
• For any i:
• S( i ) = a[ i ] + S( i – 1 )
• When do we know an answer?
• S( 0 ) = a[0]
• Thus:
• base case:
• S(0) = a[0]
• recursive step:
• S( i ) = a[i] + S(i -1), (for i > 0)

• In Java:
• public int sumArray ( int [ ] a, int i )
• {
• if ( i == 0 )
• return a[0];
• else
• return ( a[i] + sumArray(a, i - 1) );
• }

Recursive Selection Sort

• Selection sort of array A:
• Find smallest element of array from A[0] to end
• Swap with first element
• Repeat for array from A[1] to end
• I.e.,
• recursive step:
• selSort(A, i): find smallest in A from i to end
• swap with position i
• selSort(A, i+1)
• base case:
• i == A.length – 1
• nothing left to sort

Recursive Selection Sort

• // Perform a selection sort of the array A
• public void selSort ( int [ ] A ) {
• // for each element of the array
• for ( int i = 0; i < A.length – 1; i++)
• {
• // find position, k, of smallest
• int k = i;
• for (int j = i+1; j < A.length; j++)
• if ( A[j] < A[k] )
• k = j;
• // swap elements at k and i
• int temp = A[i];
• A[i] = A[k];
• A[k] = temp;
• }
• }

• // Recursive selection sort of A from i to end
• public void selSort ( int [ ] A, int i ) {
• if ( i == A.length – 1)
• return;
• else
• {
• // find position, k, of smallest
• int k = i;
• for (int j = i+1; j < A.length; j++)
• if ( A[j] < A[k] )
• k = j;
• // swap elements at k and i
• int temp = A[i];
• A[i] = A[k];
• A[k] = temp;
• // make recursive call
• selSort( A, i + 1);
• }
• }

Complexity

• Complexity of nested for-loop selection sort: O(n2)
• Complexity of recursive selection sort:O(n2)
• I.e., the recursion is doing the same work as the outer loop
• Theoretical result: iteration  recursion
• there is no loop for which you cannot write an equivalent recursion
• there is no recursion for which you cannot write an equivalent loop

Recursive Linear Search

• Find whether element x is in array A:
• public boolean isIn( int [ ] A, int x )
• {
• boolean found = false;
• for (int i = 0; i < A.length && !found; i++)
• {
• if ( A[ i ] == x )
• found = true;
• }
• return found;
• }

• Recursive linear search:
• public boolean isIn( int [ ] A, int x, int i )
• {
• if ( i >= A.length )
• return false;
• else if (A[ i ] == x )
• return true;
• else
• return isIn(A, x, i+1);
• }

• call: isIn(A, 5)

• call: isIn(A, 5, 0)

• note: two base cases
• (because two conditions for exiting loop)

Another Example of Recursion

• Greatest Common Divisor of x and y:
• public int GCD( int x, int y )
• {
• while (x != y)
• {
• if ( x > y )
• x = x – y;
• else
• y = y – x;
• }
• return x;
• }

• Recursive GCD:
• public int GCD( int x, int y )
• {
• if (x == y)
• return x;
• else
• {
• if ( x > y )
• return GCD(x – y, y);
• else
• return GCD(x, y – x);
• }
• }

• note: two recursive steps
• (because two cases in loop)

Summary

• Recursion: defining a solution to a problem in terms of itself
• recursion involves defining the solution to a problem in terms of the solution to a similar, but simpler problem
• solve a little piece of the problem at a time
• i.e., assuming the simpler problem is solved, show how to solve the more complex problem
• called the recursive step
• in order to work, need to define an absolute solution for the simplest case
• i.e., there must be a case for which the answer is known
• called the base case
• with this case defined, the recursion is called well-founded