# ---
# jupyter:
#   jupytext:
#     text_representation:
#       extension: .py
#       format_name: light
#       format_version: '1.5'
#       jupytext_version: 1.14.4
#   kernelspec:
#     display_name: python3 (dev)
#     language: python
#     name: dev
# ---

# # Recursion Notes and Algorithms

# Notes taken from: Data Structures and Algorithms in Python 1st edition by Goodrich, <NAME>., Tamassia, <NAME>, Michael (2013) Hardcover Hardcover – 1732

from nbdev.showdoc import *
from nbdev.imports import *


# +
# default_exp recursion
# -

# ## Examples
#
# Some examples of recursive functions

# ### Factorial

# +
# exports

# O(n) using n+1 activations each of which use O(1) operations
def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n-1)


# -

test_eq(factorial(0), 1)
test_eq(factorial(1), 1)
test_eq(factorial(3), 6)


# ### Draw Ruler
#
# English ruler similar to a fractal. Its shape has a self-repetitive structure. 
#
# In general, an interval with a central tick length $L \le 1$ is composed of:
#
# * An interval with a central tick length $L − 1$
# * A single tick of length L
# * An interval with a central tick length L − 1

# > Note: for $c \ge 0$ a call to draw_interval(c) results in precisely $2^c -1$ lines of output
#
# Base case draw_interval(0): $2^0 -1$ = 0 lines of output
#
# Number of lines printed by draw_interval(c) is one more than twice the number generated by a call to draw_interval(c-1)
#
# > $1 + 2(2^{c-1} -1)  = 1 + 2^c - 2 = 2^c -1$

# +
# exports

# for c >=0 a call to draw_interval(c) results in precisely 2^c - 1 calls
def draw_line(tick_length, tick_label=""):
    """Draw line with given tick length and optional label"""
    line = '-'*tick_length
    if tick_label:
        line += ' ' + tick_label
    print(line)


# -

draw_line(1)
draw_line(2)
draw_line(3)
draw_line(4, "four")


# exports
def draw_interval(center_length):
    """Draw tick length based upon a central tick length"""
    if center_length > 0:
        draw_interval(center_length-1)
        draw_line(center_length)
        draw_interval(center_length-1)


draw_interval(1)

draw_interval(2)

draw_interval(3)


# exports
def draw_ruler(num_inches, major_length):
    """draw english ruler with given number of inches and number of subdivisions"""
    draw_line(major_length, str(0))
    for i in range(1, 1+ num_inches):
        draw_interval(major_length-1)
        draw_line(major_length, str(i))


draw_ruler(2,4)

draw_ruler(0,4)


# ### Binary Search

# +
# exports
def binary_search(data, target, low, high):
    """return True if target is found"""
    if low > high:
        return False
    mid = (low + high) // 2
    print(mid)
    if target == data[mid]:
        return True
    elif target < data[mid]:
        return binary_search(data, target, low, mid-1)        
    else:
        return binary_search(data, target, mid+1, high)


# -

binary_search([0,1,2,3,4,5,6,7],6,0,7)

# ## File Systems

# ```python
# Algorithm DiskUsage(path):
#
#     Input: A string designating a path to a file-system entry
#     Output: The cumulative disk space used by that entry and any nested entries
#     total = size(path)  # {immediate disk space used by the entry}
#     if path represents a directory then
#         for each child entry stored within directory path do
#             total = total + DiskUsage(child) #{recursive call}
#     return total
# ```

# Useful module is os
#
# * os.path.getsize(path): returns immediate disk usage used by file or directory identified as path
# * os.path.isdir(path): returns true if designated string path is a directory
# * os.listdir(path): returns list of strings that are names of all entries within a directory
# * os.path.join(path, filename): joins a path and a filename 

import os


# exports
def disk_usage(path):
    """returns disk usage for a path"""
    total = os.path.getsize(path)
    if os.path.isdir(path):
        for filename in os.listdir(path):
            child_path = os.path.join(path, filename)
            total += disk_usage(child_path)
    print(f"{total:<10} {path}")
    return total

StarcoderdataJupyterScriptsDedupFiltered