Recursion
Recursion is a problem solving strategy of splitting up a problem into simpler similar subproblems, solving the subproblems, using the same strategy, and finally combining the solutions of the subproblems to obtain a solution of the original problem. If the problem is simple enough then solve it immediately.
This can be expressed as an algorithm:
solve(problem):
if problem is simple then
return solution of problem
else
split problem into subproblem1,…,subproblemn
solution1 ß solve(subproblem1)
. . .
solutionn ß solve(subproblemn)
combine solution1,…,solutionn into solution
return solution
Details about the definition of “simple”, how to split the problem into subproblems, how many subproblems there are, and how to combine the subproblem solutions depend on the actual problem and the ingenuity of the designer. A recursive algorithm is implemented as a function that calls itself.
Example: The factorial problem is often used to illustrate recursion. The problem is to calculate n! = 1´2´3´…´n for n³1 and 0!=1. The recursive step is n! = n´(n-1)! The recursive algorithm is
factorial(n):
if n=0 then
return 1
else
return n ´ factorial(n-1)
The factorial can also be computed iteratively by accumulating the product of successive numbers. Both the recursive and iterative algorithms require the same number of multiplications, however the recursive algorithm is slower due to the compiler overhead of implementing recursion using stacks.
Example: The Fibonacci sequence: 1 1 2 3 5 8 13 … starts off with 1 1, and is continued by taking the sum of the previous two numbers.
The recursive algorithm is
fib(n):
if n £ 2 then
return 1
else
return fib(n-2)+fib(n-1)
The sequence can also be computed iteratively by starting with 1 1, and repeatedly adding the last two numbers. The recursive algorithm is exponentially inefficient because the same subproblem needs to be computed many times. This can be avoided by storing subproblem solutions; if the subproblem is already stored then its solution is accessed immediately, otherwise the subproblem is solved recursively and the solution is stored.
Example: Sorting by “merge sort”. The list is split into two halves, each is sorted recursively, then the resulting sorted lists a re merged together.
The recursive algorithm is
mergeSort(list):
if list has 1 item then
return list
else
split list into two (roughly equal) halfs: list1 list2
sortedList1 ß mergeSort(list1)
sortedList2 ß mergeSort(list2)
sortedList ß merge sortedList1 and sortedList2
return sortedList
The merging requires parallel scanning of the two sorted lists, and requires linear time. The number of comparisons is proportional to n log n, where n is the size of the list.
Example: Consider this game between two players. A player is given a number,n, and has the choice of giving either n-1 or ën/2û to his opponent player. If a player is given the number 1 then he wins.
Here is a recursive algorithm that determines if a number is a winning position, assuming that the players are expert.
win(n):
if n = 1 then
return true
if lose(n-1) then
return true
if lose(ën/2û) then
return true
return false
lose(n):
if win(n) then
return false
else
return true
This can be simplified to:
win(n):
return n=1 or !win(n-1) or !win(ën/2û)
This also suffers from the inefficiency of recalculating problems many times. As a challenge, find a very simple way of computing win(n), by considering the binary representation of n.
References
1. http://www.cs.princeton.edu/introcs/23recursion/
Contains more examples such as Towers of Hanoi, recursive graphics,…
2. http://cs.senecac.on.ca/~leung/btp500.html
See Notes 1 for details of how recursion works using stacks. Use recursion to count the number of 1’s in the binary representation of a number, then look at the discussion and solution. (Can you simplify the solution by using only one call?) The “non-attacking queens” problem is also discussed.