cs1001.py , Tel Aviv University, Spring 2020

Recitation 6

Recursion recursion recursion!

We saw two recursive functions for finding the maximal element in a list. We discussed quicksort. Then we wrote three recursive functions: subset sum, change and counting paths. We've briefly discussed a combinatorial solution for the counting paths problem.

Takeaways:

  • The recursive algorithms we've seen have a similar structure. Given a problem to solve recursively:
    • Find the cases where the problem is solved easily (base cases, halting conditions)
    • Find a method of taking a big problem and reducing it to (one ore more) smaller problems
    • Find how to relate the solution to the smaller problems into the big problem
  • The recursion tree helps in bounding the recursion depth and time complexity. Each tree node represents a call to the recursive function. We write the relevant size of the input inside the tree node, and for each node we also keep the total amount of work done for this input, not including the time spent on the recursive call.
  • The recursion depth of a recursive function is the maximal number of open recursive calls at a given moment. Note that python has a limit on this value. Analyzing the recursion depth is analogous to computing the length of the longest root-leaf path in the recursion tree.
  • The time complexity of a recursive function is the total amount of work performed by all the tree nodes.
  • The space complexity of a recursive function is the total amount of space used by the "heaviest" root-leaf path in the tree.

Code for printing several outputs in one cell (not part of the recitation):

In [1]:
from IPython.core.interactiveshell import InteractiveShell
InteractiveShell.ast_node_interactivity = "all"

Max1

The maximum is the maximal value between lst[0] and the result of recursively finding the max in lst[1:].

Let $n$ denote the size of lst.

Recursion depth: $O(n)$

Time complexity: $O(n^2)$

In [2]:
def max1(L): 
    if len(L) == 1:
        return L[0]
    
    without_first = max1(L[1:])
    
    if without_first > L[0]:
        return without_first
    else:
        return L[0]
    
    
    
    
    
    

Max2

The maximum is the maximal value between the result of recursively finding the max in lst[:n//2] and the result of recursively finding the max in lst[n//2:], where $n$ denotes the size of lst.

Recursion depth: $O(\log{n})$

Time complexity: $O(n\log{n})$

In [3]:
def max2(L): 
    if len(L) == 1:
        return L[0]
    
    l = max2(L[:len(L) // 2])
    r = max2(L[len(L) // 2:])
    
    if l > r:
        return l
    else:
        return r

Now without slicing

Since slicing is a costly action we can do things better. Instead of slicing the list each time we will maintain indices for the "active" part of the list (like we did for binary search) and simply recurse after updating the indices according to the same logic.

We also add envelope functions for a more user-friendly code.

How does time/depth change for each function? The depth is clearly unaffected. Time, however, is much better.

Since we only do $O(1)$ work in the function, the runtime is analogous to computing the size of the tree which is $O(n)$ in both cases.

In [4]:
def max11(L,left,right): 
    if left == right:
        return L[left]
    
    without_left = max11(L, left + 1, right)
    
    if without_left > L[left]:
        return without_left
    else:
        return L[left]

    
    
def max22(L, left, right): 
    if left == right:
        return L[left]
    
    mid = (left + right) // 2
    l = max22(L, left, mid)
    r = max22(L, mid + 1, right)
    
    if l > r:
        return l
    else:
        return r

def max1_noslice(L):
    return max11(L, 0, len(L) - 1)

def max2_noslice(L):
    return max22(L, 0, len(L) - 1)

comparison in running times

In [6]:
import time
import random
import sys
sys.setrecursionlimit(3000)


for f in [max1, max2]:
    print(f.__name__)
    for n in [500, 1000, 2000]:
        L = [i for i in range(n)]
        random.shuffle(L)
        tic = time.process_time()
        for x in range(10):
            m = f(L)
        toc = time.process_time()
        print("n=", n, ": ",toc - tic)
        
        
max1
n= 500 :  0.015625
n= 1000 :  0.109375
n= 2000 :  0.484375
max2
n= 500 :  0.015625
n= 1000 :  0.015625
n= 2000 :  0.046875

Quick Sort

The logic

Quicksort has a very simple recursive logic:

  • A list of size 1 is trivially sorted
  • Otherwise, pick some element $x \in L$ and let:
    • $less = \{y \in L : y < x\}$
    • $eq = \{y \in L : y = x\}$ (note: $eq$ is trivially sorted)
    • $more = \{y \in L : y > x \}$
  • Recursively sort $less, more$ and return $less+eq+more$

Random:

In [5]:
import random
def quicksort(lst):
    """ quick sort of lst """
    if len(lst) <= 1: 
        return lst
    else:
        pivot = random.choice(lst)         # select a random element from list
        smaller = [elem for elem in lst if elem < pivot] 
        equal = [elem for elem in lst if elem == pivot]      
        greater = [elem for elem in lst if elem > pivot]
        return quicksort(smaller) + equal + quicksort(greater) #two recursive calls

Deterministic:

In [6]:
def det_quicksort(lst):
    """ sort using deterministic pivot selection """
    if len(lst) <= 1: 
        return lst
    else:
        pivot = lst[0]      # select first element from list
        smaller = [elem for elem in lst if elem < pivot] 
        equal = [elem for elem in lst if elem == pivot]      
        greater = [elem for elem in lst if elem > pivot]
        return det_quicksort(smaller) + equal + det_quicksort(greater) #two recursive calls

Analysis

The worst case and best case analyses were discussed in class. It is interesting to note that:

  • The worst case for quicksort has a recursion tree similar to that of $max1$, i.e. - in each recursive call we reduce the input size by $1$ giving a running time of $O(n^2)$
  • The base case for quicksort has a recursion tree similar to that of $max2$, i.e. - each instance of the function on input of size $n$ recurses twice on inputs of size roughly $n/2$, giving a running time of $O(n \cdot \log n)$

Subset sum

The subset sum problem is described as follows: given a list of integers $L$ and a value $s \in \mathbb{Z}$, is there a subset $T \subseteq L$ such that: $$\sum_{x \in T} x = s$$ If such an $T$ exists we return True, otherwise False.

Examples:

  • For $L = [4, -7, 12, 5, 1], s = 6$ we will say yes, as $-7+1+12 = 6$ (also, $5+1=6$).
  • For $L = [1, 2, 4, 8, 16], s= 32$ we will say no as all elements are positive and $\sum_{x \in L} = 31$

The recursive structure

The base cases are pretty straight-forward:

  • If we need to reach $s = 0$ then we have succeeded (i.e. - return True)
  • If we need to reach some $s \neq 0$ but $L = []$ then we have failed (i.e. - return False)

What about the recursive call? Well, if $s \neq 0, L \neq []$ then the following holds:

  • Either there's a way of "reaching" $s$ by taking the first element in $L$
  • Or there's a way of "reaching" $s$ by not taking the first element in $L$
  • If both of the above fail, there is no way of "reaching" $s$ using $L$

So what do we do? We recursively check if either $L[1:], s - L[0]$ or $L[1:], s$ can be solved, and we only return False if both fail. Let's code:

In [7]:
def subset_sum(L, s):
    if s == 0:
        return True
    if L == []:
        return False
    
    with_first = subset_sum(L[1:], s - L[0])
    without_first = subset_sum(L[1:], s)
    return with_first or without_first

# Sanity checks
L1 = [4, -7, 12, 5, 1]
L2 = [1, 2, 4, 8, 16]
s1 = 6
s2 = 32

print(subset_sum(L1, s1))
print(subset_sum(L2, s2))
True
False

Analysis

What is the running time of the code in relation to the size of the list $|L| = n$?

We can implement a solution that does not make use of slicing. Let's analyze it:

The recurrence relation is clearly $T(n) = 2 \cdot T(n-1) + O(1)$, which yields $T(n) = 2^n$.

In class we've seen how to transform recursive algorithms which run in exponential time into iterative algorithms that run in linear time (i.e. - Fibonacci, factorial).

Can you think of a better solution? One that works in time $O(n^2)$? How about $O(n^{100})$?

Incredibly, there is a wide held belief that this problem yields no algorithm which runs in time $\mathrm{poly}(n)$. More on that later (much later, say, next year in computational models)...

Change problem

A bus driver needs to give an exact change and she has coins of limited types. She has infinite coins of each type. Given the amount of change ($amount$) and the coin types (the list $coins$), how many ways are there?

  • There are two base cases:
    • If $amount == 0$ then there is one way of returning change - not giving any coins (return 1)
    • If $amount < 0$ or $coins = []$ (and $amount > 0$), there are no ways of return change (return 0)
  • Otherwise, the logic is very similar to that of the subset sum problem. We pick one coin from the list (say, the last one this time), and we again have two options:
    • Either we use the last coin and then check how many ways we have of returning the rest of the amount
    • We don't use the last coin at all and check how many ways we have of returning the amount
  • Summing the two options above gives the total number of ways to return the change
In [ ]:
def change(amount, coins):
    if amount == 0:
        return 1
    elif amount < 0 or coins == []:
        return 0
    return change(amount, coins[:-1]) +\
        change(amount - coins[-1], coins)
    
change(5, [1,2,3])

Recursion tree for change(5, [1, 2, 3])

Recursion Tree for change(5, [1,2,3])

Analysis

Consider the case where $amount = n^2, coins = [1,2,\ldots, n]$. When we call $change(amount, coins)$ the first level of the recursion calls $change([1,\ldots, n-1], n^2)$ and $change([1,\ldots, n], n^2 - n)$. This means that the list size in the recusrive calls is at least $n-1$ and $amount \geq n^2 -n$.

One can show (using induction) that in the first $k \leq n$ levels of recursion the list size is at least $n - k$ and $amount \geq n k$, thus there are two recursive calls at each of these layers.

This gives a running time of at least $2^n$ by the same argument as that we applied in the subset sum problem.

Subset sum vs. Change

It is interesting to note that while the two problem share some similarities, one major difference is that in the subset sum problem we are asking whether a solution exists while in the change problem we are trying to count the number of valid solutions to a problem.

This is a recurring theme in CS that we will encounter many times in the future.

Counting paths

Question 2(a) from the 2015 fall semester exam (Moed B).

Given a list $L$ of non-negative integers with $len(L) = d$ we consider $L$ as a point in a $d$-dimensional space.

For example: $L = [0, 0, 0]$ represents the origin in a $3$-dimensional space.

Our goal is to find how many ways we have of getting from $[0, \ldots, 0]$ to $L$ by advancing only forward.

For example, if $L=[1, 2]$ then we have three such paths:

  • $[0,0] \to [1, 0] \to [1, 1] \to [1,2]$
  • $[0,0] \to [0, 1] \to [1, 1] \to [1,2]$
  • $[0,0] \to [0, 1] \to [0, 2] \to [1,2]$

Again, we first think of the base case, and then reduce big problems to smaller ones.

  • If $L$ has only zeros then there is a single possible path - not taking any steps.
  • Otherwise, we have the following relation, let $L = [a_1, \ldots, a_n]$, then: $$paths([a_1, \ldots, a_n]) = \sum_{i : a_i > 0}paths([a_1,\ldots, a_i - 1, \ldots, a_n])$$

This gives rise to a simple recursive algorithm:

In [ ]:
def cnt_paths(L):
    if all_zeros(L):
        return 1
    
    result = 0
    for i in range(len(L)):
        if L[i] != 0:
            L[i] -= 1
            result += cnt_paths(L)
            L[i] += 1
    return result

def all_zeros(L):
    for i in L:
        if i != 0:
            return False
    return True


print(cnt_paths([3,4,5]))

Analysis

We will show that this solution is intractable. That is, the time complexity is at least exponential in the input size.

Let's look at a simple case where $d = |L|= 2$ and $L = [n, n]$. Consider the recursion tree for this input. In the first $n-1$ levels of the tree each node has exactly 2 children (why?). The overall number of nodes in the first $n$ levels of the tree is $\Sigma_{i=0}^{n-1}{2^i} = 2^n - 1$. Note that there are many more nodes in the tree that we did not count.

Suppose that the amount of work for each node is $O(1)$, then the overall time complexity of the function is at least $\text{num_of_nodes} \times \text{work_per_node}$. That is the time complexity is at least exponential in $n$.

Now, let's look at a slight generalization, where $L = [n, n, \ldots, n]$ and $|L| = d$. I.e. - we are in a $d$-dimensional space and we want to get to $[n, \ldots, n]$. As before, the number of nodes in the first $n$ levels of the tree is $\Sigma_{i=0}^{n-1}{d^i} \approx d^n = 2^{\log{d^n}} = 2^{n\log{d}}$. Therefore, the time complexity is at least exponential in both $n, \log{d}$.

Another way to bound (from below) the number of nodes in the tree is to count the number of leaves in the tree. Since at each leaf we return 1, the number of leaves is actually the number $cnt$ of "legal paths" that we count.

It can be shown (combinatorically) that $cnt$ is at least exponential in $d,n$.

In [ ]: