ALGORITHMS AND COMPLEXITY
farhankhan
Week3part2.pptxWeek 3: Recursion
Dr Cat Kutay
Click on Insert > new slide to choose your cover, then delete this page.
1
What Is Recursion?
Recursion is a method of solving problems that involves breaking a problem down into smaller and smaller subproblems until you get to a small enough problem that it can be solved trivially.
Recursion involves a function calling itself.
While it may not seem like much on the surface, recursion allows us to write elegant solutions to problems that may otherwise be very difficult to program.
Click on Insert > new slide to choose your cover, then delete this page.
Calculating the Sum of a List of Numbers
We will begin our investigation with a simple problem that you already know how to solve without using recursion.
Suppose that you want to calculate the sum of a list of numbers such as: [1,3,5,7,9].
An iterative function that computes the sum is shown here.
The function uses an accumulator variable (total) to compute a running total of all the numbers in the list by starting with 0 and adding each number in the list.
Click on Insert > new slide to choose your cover, then delete this page.
Premise of Recursion
Pretend that you do not have while loops or for loops. How would you compute the sum of a list of numbers?
If you were a mathematician you might start by recalling that addition is a function that is defined for two parameters, a pair of numbers. To redefine the problem from adding a list to adding pairs of numbers, we could rewrite the list as a fully parenthesized expression. Such an expression looks like this:
((((1+3)+5)+7)+9)
Click on Insert > new slide to choose your cover, then delete this page.
Premise of Recursion
We can also parenthesize the expression the other way around: (1+(3+(5+(7+9))))
Notice that the innermost set of parentheses, (7+9), is a problem that we can solve without a loop or any special constructs. In fact, we can use the following sequence of simplifications to compute a final sum.
total= (1+(3+(5+(7+9))))
total= (1+(3+(5+16)))
total= (1+(3+21))
total= (1+24)
total= 25
Click on Insert > new slide to choose your cover, then delete this page.
A Different Approach
How can we take this idea and turn it into a program, like Python?
First, let’s restate the sum problem in terms of Python lists.
We might say the sum of the list numList is the sum of the first element of the list (numList[0]), and the sum of the numbers in the rest of the list (numList[1:]).
listSum(numList)=first(numList) + listSum(rest(numList))
first(numList) returns the first element of the list
rest(numList) returns a list of everything but the first element
Click on Insert > new slide to choose your cover, then delete this page.
Example Recursive Program
Click on Insert > new slide to choose your cover, then delete this page.
Program Execution Logic
Click on Insert > new slide to choose your cover, then delete this page.
The Three Rules of Recursion
All recursive algorithms must obey three important rules
A recursive algorithm must have a base case.
A recursive algorithm must change its state and move toward the base case.
A recursive algorithm must call itself, recursively.
Click on Insert > new slide to choose your cover, then delete this page.
The Rules!
First, a base case is the condition that allows the algorithm to stop recursing. A base case is typically a problem that is small enough to solve directly.
In the list_sum algorithm the base case is a list of length 1.
Second, we must arrange for a change of state that moves the algorithm toward the base case. A change of state means that some data that the algorithm is using is modified. Usually the data that represents our problem gets smaller in some way.
In the list_sum algorithm our primary data structure is a list, so we must focus our state-changing efforts on the list. Since the base case is a list of length 1, a natural progression toward the base case is to shorten the list.
Third, the algorithm must call itself.
Click on Insert > new slide to choose your cover, then delete this page.
Self Test
How many recursive calls are made when computing the sum of the list [2,4,6,8,10]?
(A) 6
(B) 5
(C) 4
(D) 3
The first recursive call passes the list [4,6,8,10], the second [6,8,10] and so on until [10].
Click on Insert > new slide to choose your cover, then delete this page.
Factorial
Suppose you are going to write a recursive function to calculate the factorial of a number.
fact(n) returns n * n-1 * n-2 * ... Where the factorial of zero is defined to be 1. What would be the most appropriate base case?
(A) n == 0
(B) n == 1
(C) n >= 0
(D) n <= 1
n <= 1 this is the most efficient, and even keeps your program from crashing if you try to compute the factorial of a negative number.
Click on Insert > new slide to choose your cover, then delete this page.
12
Recursive Factorial Example
Here is a recursive Python function to compute the factorial of n.
The first line of the function constitutes the base case.
If the value <= 1, then answer is always 1.
If the value > 1, then the function calls itself to find the answer for (n − 1)
Click on Insert > new slide to choose your cover, then delete this page.
Fibonacci Sequence
Each new term in the Fibonacci sequence is generated by adding the previous two terms. So, for example, starting with 1 and 2, the first 9 numbers in the sequence would be:
0, 1, 1, 2, 3, 5, 8, 13, 21
Click on Insert > new slide to choose your cover, then delete this page.
Fibonacci Sequence
We can write a recursive program to get the nth number from the Fibonacci Sequence.
Click on Insert > new slide to choose your cover, then delete this page.
Examine Recursive Calls to Function
We can see that the subtree f(2) appears 3 times and the subtree for the calculation of f(3) two times.
If you imagine extending this tree for f(6), you will understand that f(4) will be called two times, f(3) three times and so on. This means, our recursion doesn't remember previously calculated values.
Click on Insert > new slide to choose your cover, then delete this page.
Big O
The Fibonacci sequence is O(2n).
Remember the definition of Big-O: f(n) is O(g(n)) iff there exist constants C and k (positive integers) such that f(x) <= C*|g(x)| for all x >= k.
So we know that Fibonacci is f(n) = f(n-1) + f(n-2), f(0) = 0, f(1) = 1.
Let g(n) = 2^n.
f(n) <= g(n) starting at some x. Then solve for C.
Click on Insert > new slide to choose your cover, then delete this page.
Memoization of Calculated Values
We can implement a "memory" for our recursive version by using a dictionary to save the previously calculated values.
What is the Big-O complexity now?
O(n)
Click on Insert > new slide to choose your cover, then delete this page.
18
Dynamic programming
Divide a problem into sub problems
Cache the results of these sub problems if used multiple times or called in sequence
eg fib(10)=fib(9)+fib(8)
Click on Insert > new slide to choose your cover, then delete this page.
Linked Lists: Recursion
How do we count the number of nodes in a linked list recursively?
How do we print out the nodes in a linked list recursively?
How do we find out a node in a linked list recursively?
How do we insert a node in a linked list recursively?
How do we delete a node in a linked list recursively?
Click on Insert > new slide to choose your cover, then delete this page.
Tail Recursion
Tail recursion is characterized by the use of only one recursive call at the very end of a method implementation
def tail(value):
if value > 0:
print(value)
tail(value - 1)
This form saves Python interpreter keeping track of the state of each nested call (see Hanoi Tower)
Click on Insert > new slide to choose your cover, then delete this page.
Efficiency
Example of removing tail recursion:
def non_recursion(value):
for value in range(10, 0, -1): print value
Click on Insert > new slide to choose your cover, then delete this page.
Backtracking
Backtracking is a technique for returning to a given position (e.g., entry point) after trying other avenues that are unsuccessful in solving a particular problem
Backtracking is a form of recursion. But it involves choosing only one option out of any possibilities. We begin by choosing an option and backtrack from it, if we reach a state where we conclude that this specific option does not give the required solution.
We repeat these steps by going across each available option until we get the desired solution.
Click on Insert > new slide to choose your cover, then delete this page.
Example:
Finding all possible order of arrangements of a given set of letters. When we choose a pair we apply backtracking to verify if that exact pair has already been created or not. If not already created, the pair is added to the answer list else it is ignored.
Click on Insert > new slide to choose your cover, then delete this page.
24
Checking duplicates
Click on Insert > new slide to choose your cover, then delete this page.
Towers of Hanoi
The Tower of Hanoi puzzle was invented by the French mathematician Edouard Lucas in 1883
Tower of Hanoi, is a mathematical puzzle which consists of three towers (pegs) and more than one rings
These rings are of different sizes and stacked upon in an ascending order, i.e. the smaller one sits over the larger one. There are other variations of the puzzle where the number of disks increase, but the tower count remains the same.
Rules
The mission is to move all the disks to some another tower without violating the sequence of arrangement.
Only one disk can be moved among the towers at any given time.
Only the "top" disk can be removed.
No large disk can sit over a small disk.
Click on Insert > new slide to choose your cover, then delete this page.
Tower of Hanoi puzzle with n disks can be solved in minimum 2n−1 steps. This presentation shows that a puzzle with 3 disks has taken 23 - 1 = 7 steps.
Click on Insert > new slide to choose your cover, then delete this page.
The Math Behind The Towers of Hanoi
To move all discs from one pin to another takes 2D-1 moves where "D" is the number of discs. Therefore the number of discs moves is approximately doubled every time you put another one on it.
Click on Insert > new slide to choose your cover, then delete this page.
Algorithm
First we need to learn how to solve this problem with lesser amount of disks, say → 1 or 2. We mark three towers with name, source, destination and aux (only to help moving the disks). If we have only one disk, then it can easily be moved from source to destination peg.
If we have 2 disks −
First, we move the smaller (top) disk to aux peg.
Then, we move the larger (bottom) disk to destination peg.
And finally, we move the smaller disk from aux to destination peg.
Click on Insert > new slide to choose your cover, then delete this page.
Algorithm cont.
More than two disks. We divide the stack of disks in two parts. The largest disk (nth disk) is in one part and all other (n-1) disks are in the second part.
Our ultimate aim is to move disk n from source to destination and then put all other (n1) disks onto it. We can imagine to apply the same in a recursive way for all given set of disks.
The steps to follow are −
Step 1 − Move n-1 disks from source to aux
Step 2 − Move remaining disk nth from source to dest
Step 3 − Move n-1 disks from aux to dest
Click on Insert > new slide to choose your cover, then delete this page.
30
Pseudo Code
START
Procedure Hanoi(disk, source, dest, helper)
IF disk == 1, THEN
move disk from source to dest
ELSE
Hanoi(disk - 1, source, helper, dest) // Step 1
move disk from source to dest // Step 2
Hanoi(disk - 1, helper, dest, source) // Step 3
END IF
END Procedure
STOP
Click on Insert > new slide to choose your cover, then delete this page.
31
Tower of Hanoi Example
Click on Insert > new slide to choose your cover, then delete this page.
32
See stack trace
https://www.cs.cmu.edu/~cburch/survey/recurse/hanoiimpl.html
What is the space complexity?
Click on Insert > new slide to choose your cover, then delete this page.
Recursion types
Liner, Binary and Multiple Recursion – defined by the number of recursion in one call to the function
Binary is a two-branching tree
Developing a recursive function requires removing “odd” cases and finding a similar structure through each enumeration of the function
Iterative sequences are ideal for this where xn+1 = F(xn) eg n!
Designing Recursive Algorithms
Eliminating Tail Recursion .
Click on Insert > new slide to choose your cover, then delete this page.
Thank you [email protected]
Click on Insert > new slide to choose your cover, then delete this page.
