|
- 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.
- v=sum(3)
- sum:=3+sum(2)
- sum:=2+sum(1)
- sum:=1
- sum:=3
- sum:=6
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)!
-
- 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!
- 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);
- }
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 )
- }
- 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);
- }
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
Do'stlaringiz bilan baham: |
