Recursion
• Sometimes, the best way to solve a problem is by solving a smaller version of the same
problem first
• Recursion is a technique that solves a problem by solving a smaller problem of the
same type
• In programming recursion is a method call to the same method.
• In other words, a recursive method calls itself.
• Recursive algorithms are simple to understand and prove correct, easy to
implement
• But! Recursive calls can result in an infinite loop of calls
• Infinite recursion will result in a crash, when stack frames
overrun the limit
• Recursion needs a base case in order to stop
• Make sure the recursion stops at some point
• Many tasks can be done with either recursion or with iteration
• Iteration involves a loop, but not recursive calls
• Make sure the recursion stops at some point
Content of a Recursive Method
• With each recursive call, the parameter controlling the
recursion should move closer to the base case
• Base case(s).
• There is a base case (or cases) that is tested upon
entry
• Values of the input variables for which we
perform no recursive calls are called base
cases (there should be at least one base
case).
• Every possible chain of recursive calls must
eventually reach a base case.
• Recursive calls.
• Calls to the current method.
• Each recursive call should be defined so that it
makes progress towards a base case.
Example
• Write a function that computes the sum of numbers from 1 to n
int sum (int n)
1. use a loop
2. recursively
//recursively
//with a loop
int sum (int n) {
int sum (int n) {
int s = 0;
if (n == 1)
for (int i=1; i<=n;i++)
return 1;
s+= i;
else
return s;
return n + sum(n-1);
}
}
Example
• Write a function that computes the sum of numbers from 1 to n, using
• Loop
• Recursive function
How to write a recursive function?
• Determine the size factor
• how the problem size is reduced with each recursive call.
• E.g. For calculating factorial, the size factor is reducing the number n by 1 with each recursive call (i.e., n becomes n−1).
• Determine the base case(s)
• (the one for which you know the answer)
• When the base case is reached, the recursion stops.
• E.g. For calculating factorial, the base case is when n is 0 or 1. We know that 0! and 1! both equal 1
• Determine the general case(s)
• (the one where the problem is expressed as a smaller version of itself)
• E.g. For factorial calculation, the general case is: !n!=n×(n−1)!. So, the function calls itself with n−1.
• Verify the algorithm
• (use the "Three-Question-Method") - next slide
Three-Question Verification Method
1. Does the function always reach the base case?
• Ensure that the recursion progress leads to the base case to prevent
infinite recursion
2. Does the function correctly solve the base case?
• Verify that the base case solution is correct.
3. Does the function correctly combine results of recursive
calls to solve the general case?
• Ensure that the recursive calls and their results are combined
accurately to solve the overall problem.
Problems defined recursively
There are many problems whose solution can be defined recursively
Example: n factorial
1 if n = 0
n!= (recursive solution)
(n-1)!*n if n > 0
1 if n = 0
n!= (closed form solution)
1*2*3*…*(n-1)*n if n > 0
Coding the factorial function (cont.)
Iterative implementation
Coding the factorial function
Recursive implementation
NB: For n > 12 this function will return an incorrect value as the final result is too big to fit in an integer
Trace of Recursion: Factorial
A Recursive Binary Search Function
• Assume an array a that is sorted in ascending order, and
an item X to search for
• We want to write a function that searches for X within
the array a, returning the index of X if it is found, and
returning -1 if X is not in the array
• Searching an array could be divided into searching
the first and second halves of the array
• Searching each half is a smaller version of searching
the whole array
Recursive Binary Search
A recursive strategy for searching a portion of the array from index lo
to index hi is to
set m to the index of the middle element of the array:
lo m hi
Recursive Binary Search
lo m hi
If a[m] == X, we found X, so return m
If a[m] > X, recursively search a[lo..m-1]
If a[m] < X, recursively search a[m+1..hi]
Binary Search Algorithm Steps
1. if array is empty
2. return -1 as result
3. else if middle element matches
4. return index of middle element as result
5. else if target < middle element
6. return result of searching lower portion of array
7. else
8. return result of searching upper portion of array
14
Binary Search - Recursive
Binary Search - Iterative
Deciding whether to use a recursive solution
• When the depth of recursive calls is relatively "shallow“
• Recursive solutions involve function calls that are added to the call stack.
• Shallow recursive call doesn't lead to excessive memory usage or performance issues.
• the function doesn’t call itself too many times before reaching a base case
• When the recursive version does about the same amount of work as the nonrecursive
version
• Choosing recursion might lead to more elegant and readable code without
significantly affecting performance.
• When the recursive version is shorter and simpler than the nonrecursive solution
• Improves the readability and maintainability of the code.
