Recursion


## Review: Running time and big-$\mathcal{O}$: Recursive Algorithms for Computing Powers

As example of the use of linear recursion, we consider the problem of raising a number $x$ to an arbitrary nonnegative integer, $n$. That is, we wish to compute the power function, defined as $power(x,n) = xn$. (We use the name “power” for this discussion, to differentiate from the built-in Python function _pow_ that provides such functionality.) We will consider two different recursive formulations for the problem that lead to algorithms with very different performance.
A trivial recursive definition follows from the fact that $x^n = x \cdot x^{n−1}$ for $n > 0$.


\begin{equation}
power(x,n) ==\left\{
                \begin{array}{ll}
                        1 \ if \ n = 0\\
                        x \ power(x, n − 1) \ otherwise.
                \end{array}
              \right.
\end{equation}

This definition leads to a recursive algorithm shown below:


```python
def basicpower(x, n):
    '''Compute the value x**n for integer n.''' 
    if n == 0:
        return 1 
    else:
        return x  * power(x, n-1)
```

A recursive call to this version of power(x,n) runs in $\mathcal{O}(n)$ time.


```python
def power(x, n):
    '''Compute the value x**n for integer n.''' 
    if n == 0:
        return 1 
    else:
        partial = power(x, n // 2) 
        result = partial * partial
    if n % 2 == 1:
        result *= x 
    return result
```

To analyze the running time of the revised algorithm, we observe that the exponent in each recursive call of function power(x,n) is at most half of the preceding exponent. As we saw with the analysis of binary search, the number of times that we can divide $n$ in half before getting to one or less is $\mathcal{O}(log n)$. Therefore, our new formulation of the power function results in $\mathcal{O}(logn)$ recursive calls. Each individual activation of the function uses $\mathcal{O}(1)$ operations (excluding the recursive calls), and so the total number of operations for computing power(x,n) is O(logn). This is a significant improvement over the original $\mathcal{O}(n)$-time algorithm.

**Exercise:** Test the two functions with a timer and see the difference. Identify the base case and stopping conditions.

# Exercise: Fibonacci

The sequence, in which each number is the sum of the two preceding numbers is known as the Fibonacci sequence: $1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, \cdots$ (each number is the sum of the previous two, e.g., $144=55 + 89$).

As you covered Fibonacci in Semester 1, this should be familiar. The twist is we are going to look at a variety of ways of implementing it and the complexity of execution for each.

A direct implementation of the description above would lead to pseudo code like this:
function: fibonacci(n)
---------------------
INPUT n, a natural number
OUTPUT the n'th Fibonacci number 

   if n <= 1 then
        return n
   else
        fibonacci(n-1) + fibonacci(n-2)
   endif

Two recursive solutions for a Fibonacci function are coded in Python below. The pseudo code version is given a function name bad_fibonacci.

1. Run the two solutions with timers. Which one has a faster running time and why is one considered bad and the other good? What is the big-$\mathcal{O}$ complexity for bad_fibonacci?
2. Is good_fibonacci tail recursive? Explain your answer. What is the big-$\mathcal{O}$ complexity?
3. Implement a tail recursive solution. **Hint:** use two "accumulators", one (say, **acc2**) for the previous value in the sequence ($n-1$ if you're computing the $n$-th number) and one (say, **acc1**) for the value before that in the sequence ($n-2$ if you're computing the $n$-th element of the sequence). Thus the function becomes **fibo_tail(n,acc1,acc2)** and in the algorithm you have a recursive call to **fibo_tail(n-1,acc2,acc2+acc1)**?: you decrease $n$ until the stopping condition ($n=1$) and accumulate in the two other parameters. **Hint 2:** If you follow this, the initial call will be **fibo_tail(n,1,1)**?. 
4. Implement an iterative version of fibonacci using a for or while loop. What is the big-$\mathcal{O}$ complexity?
5. Write another iterative version of Fibonacci using the concept we (briefly) introduced in the lecture under "dynamic programming": use an array $my\_array$ of size $n$ starting with $my\_array[0]=1$ and $my\_array[1]=1$ and for each $i>1$  set $my\_array[i]=my\_array[i-1]+my\_array[i-2]$. 



```python
def bad_fibonacci(n):
  """Return the nth Fibonacci number."""
  if n <= 1:
    return n
  else:
    return bad_fibonacci(n-2) + bad_fibonacci(n-1)

def good_fibonacci(n):
  """Return pair of Fibonacci numbers, F(n) and F(n-1)."""
  if n <= 1:
    return (n,0)
  else:
    (a, b) = good_fibonacci(n-1)
    return (a+b, a)
```

## Fibonacci Solutions

1. timing


```python
%%time

bad_fibonacci(20)
```

    CPU times: user 4.48 ms, sys: 442 µs, total: 4.92 ms
    Wall time: 4.54 ms





    6765




```python
%%time

good_fibonacci(20)
```

    CPU times: user 17 µs, sys: 6 µs, total: 23 µs
    Wall time: 29.1 µs





    (6765, 4181)



2. It is not tail recursive becuase there is something to do after returning the values (adding them together). We can use 2 accumulators to avoid this.


```python
def fibo_tail(n, acc2, acc1):
    # Base case
    if n ==1:
        # Return accumulator
        return acc2
    else:
        # Accumulators are updated at each recursive call. 
        return fibo_tail(n-1, acc1, acc2+acc1)
```


```python
%%time

fibo_tail(20,1,1)
```

    CPU times: user 13 µs, sys: 1 µs, total: 14 µs
    Wall time: 20 µs





    6765



Example using a helper to hide the accumulator parameters.


```python
def fib_rectail(n):
    def fib_helper(n, acc2, acc1):
        return fib_helper(n-1, acc1, acc2+acc1) if n > 0 else acc1
    return fib_helper(n-1, 0, 1)        
```


```python
fib_rectail(20)
```




    6765



In each non-base case we make two recursive calls to the fibonacci function! Computing the $n^{th}$ Fibonacci number in this way requires an exponential number of calls to the function.

Why?

Let $c_n$ denote the number of calls performed in the execution of bad_fibonacci(n). How will the sequence progress for $c_0$ to $c_8$?

$
\begin{align}
c_0 & = 1 \\
c_1 & = 1 \\
c_2 & = 1+c_0+c_1=1+1+1=3 \\
c_3 & = 1+c_1+c_2=1+1+3=5 \\
c_4 & = 1+c_2+c_3=1+3+5=9 \\
c_5 & = 1+c_3 +c_4 = 1+5+9 = 15 \\
c_6 & = 1+c_4 +c_5 = 1+9+15 = 25\\
c_7 & = 1+c_5 +c_6 = 1+15+25 = 41\\
c_8 & = 1+c_6 +c_7 = 1+25+41 = 67
\end{align}
$
 
Examining this sequence we see by induction that the number of calls more than doubles for each two consecutive indices. Thus, $c_n > 2^{n/2}$, which is $\mathcal{O}(2^n)$ or $\mathcal{O}(c^n)$.

The good_fibonacci(n) is $\mathcal{O}(n)$ because other than the recursive call the function runs in constant time.


```python
# With for loop
def fibonacci_for(n):
    fib = 1
    fib1, fib2 = 1, 1
    if n > 2:
        for i in range(2, n):
            fib = fib1 + fib2
            fib1, fib2 = fib2, fib
    return fib

# With while loop
def fibonacci_while(n):
    fib = 1
    fib1, fib2 = 1, 1
    i = 2
    while i < n:
        fib = fib1 + fib2
        fib1, fib2 = fib2, fib
        i+=1
    return fib
```

We can see here that in both iterative solutions, the loops will run $n-2$ times. Not taking into account constants, we can see that the Big-$\mathcal{O}$ complexity will be $\mathcal{O}(n)$.


```python
def dynamic_fibonacci(n):
    # First two elements of series are placed in index 0 and 1 of our array.
    my_array = [1, 1]
    # We add the elements at the previous two indexes to get the element of the next index.
    for i in range(2, n):
        my_array.append(my_array[i-1] + my_array[i-2])
    return my_array[n-1]
```


```python
%%time
dynamic_fibonacci(20)
```

    CPU times: user 16 µs, sys: 1 µs, total: 17 µs
    Wall time: 23.1 µs





    6765



# Example: An English Imperial Ruler 

Graduations on a twelve inch imperial scale ruler. This is an example to show you that there is more to recursion than Fibonacci!


```python
def draw_line(tick_length, tick_label=''):
  """Draw one line with given tick length (followed by optional label)."""
  line = '-' * tick_length
  if tick_label:
    line += ' ' + tick_label
  print(line)

def draw_interval(center_length):
  """Draw tick interval based upon a central tick length."""
  if center_length > 0:                   # stop when length drops to 0
    draw_interval(center_length - 1)      # recursively draw top ticks
    draw_line(center_length)              # draw center tick
    draw_interval(center_length - 1)      # recursively draw bottom ticks

def draw_ruler(num_inches, major_length):
  """Draw English ruler with given number of inches and major tick length."""
  draw_line(major_length, '0')            # draw inch 0 line
  for j in range(1, 1 + num_inches):
    draw_interval(major_length - 1)       # draw interior ticks for inch
    draw_line(major_length, str(j))       # draw inch j line and label
    
    
draw_ruler(3,4)
```

    ---- 0
    -
    --
    -
    ---
    -
    --
    -
    ---- 1
    -
    --
    -
    ---
    -
    --
    -
    ---- 2
    -
    --
    -
    ---
    -
    --
    -
    ---- 3


# Example: Binary Search


Binary search is a classic recursive algorithm to find a target value within a sorted sequence. This is among the most important of computer algorithms, and it is the reason that we so often store data in sorted order.

e.g. For the sorted sequence below stored in a Python list with indexes above:

<table>
<tr><th>0</th><th>1</th><th> 2</th><th>3</th><th>4</th><th> 5</th><th>6</th><th>7</th><th> 8</th><th>9</th><th>10</th><th> 11</th> </tr>
<tr><td>2</td><td>4</td><td> 5</td><td>6</td><td>8</td><td> 9</td><td>15</td><td>16</td><td> 17</td><td>22</td><td>30</td><td> 31</td> </tr>
</table>

If the sequence was unsorted a simple solution is a _sequential search algorithm_: use a loop to examine every element. You either reach the end of the list or find the target.

It is linear complexity, running in $\mathcal{O}(n)$ time as worst case it inspects every element in the sequence.

A sorted sequence allows a much faster approach. Think about how you would accomplish this task by hand: divide in two, and choose the middle digit as a candidate to compare to the target. Everything to the left of the candidate is lower than it and everything to the right is higher. Compare the target to the candidate and discard the left if the candidate is lower and the right if it is higher. Then repeat your _binary search_ algorithm. This is much more efficient, running in $\mathcal{O}($log$n$) time.

Review the iterative and recursive binary search algorithm implementations below.


```python
def binary_search_iterative(data, target):
  """Return True if target is found in the given Python list."""
  low = 0
  high = len(data)-1
  while low <= high:
    mid = (low + high) // 2
    if target == data[mid]:         # found a match
      return True
    elif target < data[mid]:
      high = mid - 1                # only consider values left of mid
    else:
      low = mid + 1                 # only consider values right of mid
  return False                      # loop ended without success
```


```python
def binary_search(data, target, low, high):
  """Return True if target is found in indicated portion of a Python list.

  The search only considers the portion from data[low] to data[high] inclusive.
  """
  if low > high:
    return False                    # interval is empty; no match
  else:
    mid = (low + high) // 2
    if target == data[mid]:         # found a match
      return True
    elif target < data[mid]:
      # recur on the portion left of the middle
      return binary_search(data, target, low, mid - 1)
    else:
      # recur on the portion right of the middle
      return binary_search(data, target, mid + 1, high)
```

When a function makes two recursive calls, we say that it uses binary recursion. Clearly the binary_search above is a binary recursion. Drawing the English ruler and the bad fibonacci function are also examples of binary recursion.


```python
data=[2,4,5,6,8,9,15,16,17,22,30,31]

rec_ans = binary_search(data,5,0,len(data))
iter_ans = binary_search_iterative(data,100)

print(rec_ans,iter_ans)
```

    True False


# Example: Directory Size
File system traversal is a classic example of using recursion to navigate a data structure (the file system). We will look at an example of finding the total file size of the current directory and any sub-directories. Remember that directories can be nested arbitrarily deeply within other directories and you can have 0 or more sub-directories in a directory. Python allows us to use the **os** module to write code that will execute on any OS.  Run it on your machine and compare it to other students running a diffent OS at your table.


```python
import os

def disk_usage(path):
  """Return the number of bytes used by a file/folder and any descendents."""
  total = os.path.getsize(path)                  # account for direct usage
  if os.path.isdir(path):                        # if this is a directory,
    for filename in os.listdir(path):            # then for each child:
      childpath = os.path.join(path, filename)   # compose full path to child
      total += disk_usage(childpath)             # add child's usage to total

  print ('{0:<7}'.format(total), path)           # descriptive output (optional)
  return total  

disk_usage('.')
```

f5dda00207c11f6d438651d5f9570504e436a626
ipynb
Jupyter Notebook
Recursion.ipynb
AbhishekSinhaCoder/Data-Structures-Concepts-through-Notebook
e3ae1caa066dc004e50f0a3743f2715be1c4ce8a
MIT
2019-12-30T21:58:04.000Z
2020-10-26T16:22:15.000Z
Recursion.ipynb
AbhishekSinhaCoder/Data-Structures-Concepts-through-Notebook
e3ae1caa066dc004e50f0a3743f2715be1c4ce8a
MIT
2021-03-19T04:23:49.000Z
2022-03-12T00:08:31.000Z
Recursion.ipynb
AbhishekSinhaCoder/Data-Structures-Concepts-through-Notebook
e3ae1caa066dc004e50f0a3743f2715be1c4ce8a
MIT
2020-04-01T05:52:24.000Z
2020-10-25T16:41:26.000Z
Qwen/Qwen-72B
1. YES
2. YES