<jupyter_start><jupyter_text>Recursion examplesadopted from: https://github.com/rasbt/algorithms_in_ipython_notebookshttps://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 PowersAs 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:<jupyter_code># in case we did not know about Pythons x**n statement :)
2**8
# 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
2**0
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<jupyter_output><empty_output><jupyter_text>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<jupyter_code>basicpower(2,8)<jupyter_output><empty_output><jupyter_text>A recursive call to this version of power(x,n) runs in $\mathcal{O}(n)$ time.<jupyter_code>%%timeit
basicpower(2,1000)
%%timeit
basicpower(2,2000)
%%timeit
basicpower(2,2500)
# not satisfied with performance of our basic power we have an improvement in mind

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
power(2,8)
power(2,9)
import math

math.log2(1024)
math.log2(1024*1024)
math.log2(10**100) # log n of googool 
# 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
%%timeit
power(2,1000)
%%timeit
power(2,2000)
%%timeit
power(2,2_000_000)<jupyter_output><empty_output><jupyter_text>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.<jupyter_code># 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
%%timeit
power(2,100_000)
%%timeit
2**100_000
%%timeit
power(2,1_000_000)
%%timeit
2**1_000_000<jupyter_output><empty_output><jupyter_text>We humans operate better on visual data - 1 picture and 1000 words<jupyter_code># 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)}")
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()
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()
math.pow(2,800_000)<jupyter_output><empty_output><jupyter_text>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<jupyter_code># so again base case for stopping will be 1
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
math.factorial(0)
# regular loop based algorithm should need less memory
def factorial_loop(x):
    res = 1
    while x > 1:
        res *= x
        x -=1
    return res
factorial_loop(5)
factorial(5)
factorial(1)<jupyter_output><empty_output><jupyter_text>5! = 5 x 4 x 3 x 2 x 1 = 120<jupyter_code>factorial(5)
%%timeit
factorial(10)
%%timeit
factorial(100)
%%timeit
factorial_loop(100)
%%timeit
factorial(1000)
%%timeit
factorial(2000)
%%timeit
factorial_loop(1000)
%%timeit
factorial_loop(2000)
factorial(5000)
%%timeit
factorial(5000) #
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()
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()<jupyter_output><empty_output><jupyter_text>Exercise: FibonacciThe 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:<jupyter_code>def bad_fibonacci(n):
  """Return the nth Fibonacci number."""
  if n <= 1:
    return n
  else:
    return bad_fibonacci(n-2) + bad_fibonacci(n-1)
for n in range(10):
    print(bad_fibonacci(n))
%%timeit
bad_fibonacci(10)
%%timeit
bad_fibonacci(12)
%%timeit
bad_fibonacci(16)
%%timeit
bad_fibonacci(20)
%%timeit
bad_fibonacci(24)
%%timeit
bad_fibonacci(32)
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()
# so bad_fibonacci looks like an exponational complexity
arr = [2**n for n in range(30)]
plt.plot(list(range(30)), arr)
plt.show()
# sure smells like exponential
# 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 

2**32 # he could count half a board
2**64 # not likely for a human...


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)
%%timeit
good_fibonacci(10)
%%timeit
good_fibonacci(20)
%%timeit
good_fibonacci(30)
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()
import sys
print(sys.getrecursionlimit())
#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())
good_fibonacci(5_000)
## Fibonacci Solutions

1. timing
def fibonacci_loop(n):
    a, b = 1, 1
    cnt = 3
    while cnt <= n:
        a, b = a+b, a
        cnt += 1
    return a
fibonacci_loop(2)
fibonacci_loop(10)
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()
# 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.<jupyter_output><empty_output><jupyter_text>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:01 234 567 8910 11 24 568 91516 172230 31 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.<jupyter_code>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
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)<jupyter_output><empty_output><jupyter_text>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.<jupyter_code>data=[2,4,5,6,8,9,15,16,17,22,30,31]
iter_ans = binary_search_iterative(data,100)
iter_ans
binary_search_iterative(data,15)
binary_search_iterative(data,7)
%%timeit
binary_search_iterative(list(range(1_000_000)), 9000)
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()
# 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
arr = list(range(1_000_000))
big_arr = list(range(100_000_000))
%%timeit
binary_search(arr, 9000, 0, len(arr)-1)
%%timeit
binary_search_iterative(arr, 9000)
%%timeit
binary_search(big_arr, 9000, 0, len(big_arr)-1)
%%timeit
binary_search(big_arr, 50_000_000, 0, len(big_arr)-1) # so this should hit with 1 comparison
%%timeit
binary_search_iterative(big_arr, 9000)
%%timeit
binary_search_iterative(big_arr, 50_000_000) # so this should hit with 1 comparison
# 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
# all recursive algorithms can be transformed to regular loop based algorithms
# worst case you build your stack for holding the function calls<jupyter_output><empty_output><jupyter_text>Length of an array<jupyter_code># in case we forgout about len() function ...
def array_len(x):
    if x == []:
        return 0
    else:
        return 1 + array_len(x[1:])
array_len([])
array_len([1, 2, 3])
array_len(list(range(2961))) # so it looks like 3000 limit is actually 2961 (presumably stack needs space for other functions)<jupyter_output><empty_output><jupyter_text>Sum of the elements in an array<jupyter_code># in case we forgot about sum() function ...
def array_sum(x):
    if x == []:
        return 0
    else:
        return x[0] + array_sum(x[1:])
array_sum([])
array_sum([5])
array_sum([1, 2, 3, 4, 5])
array_sum(list(range(101))) # remember the formula for summing arithmethic series n(n-1)/2
array_sum(list(range(2961)))<jupyter_output><empty_output><jupyter_text>Tower of Hanoi![tower](https://upload.wikimedia.org/wikipedia/commons/thumb/0/07/Tower_of_Hanoi.jpeg/600px-Tower_of_Hanoi.jpeg)* 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<jupyter_code>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)
quicksort([])
quicksort([5])
quicksort([5, 4])
quicksort([1, 2, 7, 5, 4])
quicksort([5, 4, 3, 2])<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.09334298118668596, 'fraction_numerical': 0.037014360458644105, 'mean_word_length': 4.081165158371041, 'pattern_counts': {'":': 0, '<': 62, '<?xml version=': 0, '>': 57, 'https://': 5, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '13', 'dir': 'jupyter-structured-clean-dedup', 'id': '522577', 'license': 'MIT', 'n_tokens_mistral': 6065, 'n_tokens_neox': 5463, 'n_words': 2188, 'path': 'recursion-examples.ipynb', 'repo_name': 'ValRCS/RTU_Algorithms_DIP321', 'size': '17966'}