# Recursion examples

adopted from: https://github.com/rasbt/algorithms_in_ipython_notebooks

https://github.com/AbhishekSinhaCoder/Data-Structures-Concepts-through-Notebook

# Examples using Recursion

**Important Note**

For most cases, using function recursion should be avoided in Python are better be implemented using for/while loops most of the time (although, I must admit that recursive solutions do look elegant). One of the reasons is that stacking recursive calls can easily blow up memory or at least result in the popular yet nasty "RuntimeError: maximum recursion depth exceeded". Also, keep in mind that Python does not optimize tail recursion in favor of having the full tracebacks for debugging; related to that, please see Guido van Rossums blog posts "[Tail Recursion Elimination](http://neopythonic.blogspot.com.au/2009/04/tail-recursion-elimination.html)" and "[Final Words on Tail Calls](http://neopythonic.blogspot.com.au/2009/04/final-words-on-tail-calls.html)." If you do like to play around with recursion more efficiently, I highly recommend taking a look at [Haskell](https://www.haskell.org) or other functional programming languages. That being said, below are some examples of recursive function implementations in Python for illustrative purposes.

## 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
# in case we did not know about Pythons x**n statement :)
```


```python
2**8
```


```python
# so the idea is to reduce the problem to a simpler instance of the same problem
## to start with we need a base case
## so base case for power would be x to 0 which is 1
```


```python
2**0
```


```python
def basicpower(x, n):
    '''Compute the value x**n for integer n.''' 
    if n == 0:
        return 1 # base case without base case our recursive function will run forever
    else:
        return x  * basicpower(x, n-1) # our recursive call so we are calling the function on itself on a smaller problem space
```

# How to make a recursive function in two easy steps
* figure out the base case
* figure out how to reduce problem to a subset of the same problem


```python
basicpower(2,8)
```

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


```python
%%timeit
basicpower(2,1000)
```


```python
%%timeit
basicpower(2,2000)
```


```python
%%timeit
basicpower(2,2500)
```


```python
# not satisfied with performance of our basic power we have an improvement in mind
```


```python

def power(x, n):
    '''Compute the value x**n for integer n.''' 
    if n == 0: # this is our base case
        return 1 
    else:
        partial = power(x, n // 2) # remember that x^4*x^4 == x^8
        result = partial * partial
    if n % 2 == 1:
        result *= x 
    return result
```


```python
power(2,8)
```


```python
power(2,9)
```


```python
import math

```


```python
math.log2(1024)
```


```python
math.log2(1024*1024)
```


```python
math.log2(10**100) # log n of googool 
```


```python
# so if we were playing the guess the number with yes and no questions we could figure out any number up to googool in 333 questions

# not bad when we consider that number of atoms in Universe is something 10**80
```


```python
%%timeit
power(2,1000)
```


```python
%%timeit
power(2,2000)
```


```python
%%timeit
power(2,2_000_000)
```

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.


```python
# so we got the famous stack overflow
# technically we could adjust the recursion depth in Python but it would not really help in the long run
```


```python
%%timeit
power(2,100_000)
```


```python
%%timeit
2**100_000
```


```python
%%timeit
power(2,1_000_000)
```


```python
%%timeit
2**1_000_000
```

# We humans operate better on visual data - 1 picture and 1000 words


```python
# in python we can pass functions as arguments
import matplotlib.pyplot as plt
import time
def automatic_time(input_array, func_name):
    # input_array contains all elements of input,
    #   preferably sorted from small to big,
    #   each element could also be a tuple, which is requried
    #   for functions that need more than 1 input
    # func_name is the name of the function (as object, not str)
    # this function also suppresses printing output from the {func_name}
    ret = []
    for val in input_array:
#         print(time.process_time_ns())
#         start = time.process_time()
        start = time.time()
        from IPython.utils import io as iuio
        with iuio.capture_output() as suppressed:
            if isinstance(val, tuple):
                _ = func_name(*val) #unrolling the tuple to pass multiple arguments to our function
            else:
                _ = func_name(val) # just a single argument function
                
        ret.append((time.time() - start)) # 10e9 converts unit from second to nanosecond
    return ret

# my_input_arr = [(2,1_000),(2,2_000)]
# print("testing function_1 with the automatic measure")
# print(F"run-time for function 1 result in nanoseconds: \n{automatic_time(my_input_arr, basicpower)}")
```


```python

```


```python
input_arr = [(2,i) for i in range(100, 2_500, 100)]

# input_arr_t = [(i,i) for i in range(1, 1000)]

# fun1 = automatic_time(input_arr, function_1)
results = automatic_time(input_arr, basicpower)
# fun3 = automatic_time(input_arr, function_3)
# fun4 = automatic_time(input_arr_t, function_4)
# fun5 = automatic_time(input_arr_t, function_5)

plt.plot([el[1] for el in input_arr], results) # we only want to see the i as x
plt.xlabel("input size")
plt.ylabel("running time in seconds")
plt.show()
```


```python
input_arr = [(2,i) for i in range(100_000, 20_000_000, 100_000)]

results = automatic_time(input_arr, power)
# mathpow_results = automatic_time(input_arr, math.pow) # math.pow does n ot like large powers

plt.plot([el[1] for el in input_arr], results)
# plt.plot([el[1] for el in input_arr], mathpow_results)
plt.xlabel("input size")
plt.ylabel("running time in seconds")
plt.show()
```


```python
math.pow(2,800_000)
```

# so it certainly looks linear but the jumps in our speed indicates how OS and computer hardware might affect an algorithm in real life

## Factorial


```python
# so again base case for stopping will be 1
```


```python
def factorial(x):
    if x <= 1:
        return 1 # not x! as factorial of 0 is considered 1!
    else:
        return x * factorial(x-1) # so we want to be sure that our problem space keeps getting smaller
```


```python
math.factorial(0)
```


```python
# regular loop based algorithm should need less memory
def factorial_loop(x):
    res = 1
    while x > 1:
        res *= x
        x -=1
    return res
```


```python
factorial_loop(5)
```


```python
factorial(5)
```


```python
factorial(1)
```

5! = 5 x 4 x 3 x 2 x 1 = 120


```python
factorial(5)
```


```python
%%timeit
factorial(10)
```


```python
%%timeit
factorial(100)
```


```python
%%timeit
factorial_loop(100)
```


```python
%%timeit
factorial(1000)
```


```python
%%timeit
factorial(2000)
```


```python
%%timeit
factorial_loop(1000)
```


```python
%%timeit
factorial_loop(2000)
```


```python
factorial(5000)
```


```python
%%timeit
factorial(5000) #
```


```python
input_arr = [i for i in range(1_000, 30_000, 1_000)]

fun2 = automatic_time(input_arr, factorial_loop)
plt.plot(input_arr, fun2)
plt.xlabel("input size")
plt.ylabel("running time in seconds")
plt.show()
```


```python
input_arr = [i for i in range(100, 2_500, 100)]

fun2 = automatic_time(input_arr, factorial_loop)
plt.plot(input_arr, fun2)
fun1 = automatic_time(input_arr, factorial)
plt.plot(input_arr, fun1)
plt.xlabel("input size")
plt.ylabel("running time in seconds")
plt.show()
```


```python

```

# 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:


```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)
```


```python
for n in range(10):
    print(bad_fibonacci(n))
```


```python
%%timeit
bad_fibonacci(10)
```


```python
%%timeit
bad_fibonacci(12)
```


```python
%%timeit
bad_fibonacci(16)
```


```python
%%timeit
bad_fibonacci(20)
```


```python
%%timeit
bad_fibonacci(24)
```


```python
%%timeit
bad_fibonacci(32)
```


```python
input_arr = [i for i in range(1, 35, 1)]

fun2 = automatic_time(input_arr, bad_fibonacci)
plt.plot(input_arr, fun2)
plt.xlabel("input size")
plt.ylabel("running time in seconds")
plt.show()
```


```python
# so bad_fibonacci looks like an exponational complexity
```


```python
arr = [2**n for n in range(30)]
plt.plot(list(range(30)), arr)
plt.show()
```


```python
# sure smells like exponential
```


```python
# what is so bad about bad fibonacci ?
# so for each recursive call you get new 2 recursive calls
# it is like that story of inventor of chess in India
# he asked for 1 grain of rice on first square
# 2 on 2nd , 4 on 3rd, 8 on 4th,
# the story modification is that king realized the problem
# to get out of it king said ok, you have to count the rice 

```


```python
2**32 # he could count half a board
```


```python
2**64 # not likely for a human...
```


```python


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) # looks linear here
    return (a+b, a)
```


```python
%%timeit
good_fibonacci(10)
```


```python
%%timeit
good_fibonacci(20)
```


```python
%%timeit
good_fibonacci(30)
```


```python
input_arr = [i for i in range(100, 3_000, 100)]

fun2 = automatic_time(input_arr, good_fibonacci)
plt.plot(input_arr, fun2)
plt.xlabel("input size")
plt.ylabel("running time in seconds")
plt.show()
```


```python
import sys
print(sys.getrecursionlimit())
```


```python
#https://stackoverflow.com/questions/3323001/what-is-the-maximum-recursion-depth-in-python-and-how-to-increase-it
sys.setrecursionlimit(100_000)
print(sys.getrecursionlimit())
```


```python
good_fibonacci(5_000)
```


```python
## Fibonacci Solutions

1. timing
```


```python
def fibonacci_loop(n):
    a, b = 1, 1
    cnt = 3
    while cnt <= n:
        a, b = a+b, a
        cnt += 1
    return a
```


```python
fibonacci_loop(2)
```


```python
fibonacci_loop(10)
```


```python
input_arr = [i for i in range(1000, 200_000, 2000)]

fun2 = automatic_time(input_arr, fibonacci_loop)
plt.plot(input_arr, fun2)
plt.xlabel("input size")
plt.ylabel("running time in seconds")
plt.show()
```


```python
# 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.
```

# 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: # so while array/list pointers do not meet we keep going
        mid = (low + high) // 2 # // meaning even half
        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: # target > data[mid]
        # 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]
iter_ans = binary_search_iterative(data,100)
iter_ans
```


```python
binary_search_iterative(data,15)
```


```python
binary_search_iterative(data,7)
```


```python
%%timeit
binary_search_iterative(list(range(1_000_000)), 9000)
```


```python

```


```python
input_arr = [(list(range(i)), 9000) for i in range(100_000, 1_000_000, 50_000)]

fun1 = automatic_time(input_arr, binary_search_iterative)
plt.plot([len(el[0]) for el in input_arr], fun1)
# fun2 = automatic_time(input_arr, binary_search) # the recursive one
# plt.plot([len(el[0]) for el in input_arr], fun2)
plt.xlabel("input size")
plt.ylabel("running time in seconds")
plt.show()
```


```python
# so binary search is in log n time we would need a trulyl large data sets to see difference
# most of our time is spent linearly setting up our data sets
```


```python
arr = list(range(1_000_000))
big_arr = list(range(100_000_000))
```


```python
%%timeit
binary_search(arr, 9000, 0, len(arr)-1)
```

    9.56 µs ± 246 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)



```python
%%timeit
binary_search_iterative(arr, 9000)
```

    7.23 µs ± 120 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)



```python
%%timeit
binary_search(big_arr, 9000, 0, len(big_arr)-1)
```

    17.3 µs ± 483 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)



```python
%%timeit
binary_search(big_arr, 50_000_000, 0, len(big_arr)-1) # so this should hit with 1 comparison
```

    16 µs ± 150 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)



```python
%%timeit
binary_search_iterative(big_arr, 9000)
```

    13.2 µs ± 513 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)



```python
%%timeit
binary_search_iterative(big_arr, 50_000_000) # so this should hit with 1 comparison
```

    12.6 µs ± 468 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)



```python
# so creating a recursive algorithm yourself
# check if problem is already solved
# otherwise reduce problem to simpler instance of the same problem
# in other words Simplify and Delegate the problem
```


```python
# all recursive algorithms can be transformed to regular loop based algorithms
# worst case you build your stack for holding the function calls
```

## Length of an array


```python
# in case we forgout about len() function ...
```


```python
def array_len(x):
    if x == []:
        return 0
    else:
        return 1 + array_len(x[1:])
```


```python
array_len([])
```




    0




```python
array_len([1, 2, 3])
```




    3




```python
array_len(list(range(2961))) # so it looks like 3000 limit is actually 2961 (presumably stack needs space for other functions)
```




    2961



## Sum of the elements in an array


```python
# in case we forgot about sum() function ...
```


```python
def array_sum(x):
    if x == []:
        return 0
    else:
        return x[0] + array_sum(x[1:])
```


```python
array_sum([])
```




    0




```python
array_sum([5])
```




    5




```python
array_sum([1, 2, 3, 4, 5])
```




    15




```python
array_sum(list(range(101))) # remember the formula for summing arithmethic series n(n-1)/2
```




    5050




```python
array_sum(list(range(2961)))
```




    4382280



# Tower of Hanoi


* must not move more than one disc at a time 
* must place this disc on a needle so that there is no smaller disc below it

## Quicksort - more about sorting later on


```python
def quicksort(array):
    if len(array) < 2:
        return array
    else:
        pivot = array[0]
        smaller, bigger = [], []
        for ele in array[1:]:
            if ele <= pivot:
                smaller.append(ele)
            else:
                bigger.append(ele)
        return quicksort(smaller) + [pivot] + quicksort(bigger)
```


```python
quicksort([])
```


```python
quicksort([5])
```


```python
quicksort([5, 4])
```


```python
quicksort([1, 2, 7, 5, 4])
```


```python
quicksort([5, 4, 3, 2])
```

1587d81a1fd3a90a376ce4858be4554eddde3ff7
ipynb
Jupyter Notebook
recursion-examples.ipynb
ValRCS/RTU_Algorithms_DIP321
6711ba5b0bad2d50f0c80cbe3218368ef430fde7
MIT
2022-02-02T06:36:40.000Z
2022-02-02T06:36:40.000Z
recursion-examples.ipynb
ValRCS/RTU_Algorithms_DIP321
6711ba5b0bad2d50f0c80cbe3218368ef430fde7
MIT
recursion-examples.ipynb
ValRCS/RTU_Algorithms_DIP321
6711ba5b0bad2d50f0c80cbe3218368ef430fde7
MIT
2021-03-16T13:26:01.000Z
2021-05-08T10:00:11.000Z
Qwen/Qwen-72B
1. YES
2. YES