Recursion in Python

recursion.py

"""
A function that takes an integer as input and returns
the sum of all numbersfrommm the input down to 1. 
Runtime in big-O is O(N), since it calls it self 
once per function.
"""


def sum_to_one(n):
    if n == 1:
        return n
    print(f"Recursing with input: {n}")
    return sum_to_one(n - 1) + n


# uncomment when you're ready to test
print(sum_to_one(7))

"""
Given a positive integer as input , returns the product
of every integer from 1 up to the input. If the input 
is less than 2 it will return 1. That would be the base 
case. Also a big-O complexity of O(N)
"""


def factorial(n):
    if n < 2:
        return 1
    print(f"Recursing with input: {n}")
    return factorial(n - 1) * n


print(factorial(12))


"""
A function that removes nested lists within a list but
keeps the values contained.
"""


def flatten(my_list):
    result = []
    for elem in my_list:
        if isinstance(elem, list):
            print("list found!")
            flat_list = flatten(elem)
            result += flat_list
        else:
            result.append(elem)
    return result


# reserve for testing...
planets = ['mercury', 'venus', ['earth'], 'mars', [
    ['jupiter', 'saturn']], 'uranus', ['neptune', 'pluto']]

print(flatten(planets))

"""
The implementation of fibonacci with recursion!

Fibonacci numbers are integers which follow a specific 
sequence: the next Fibonacci number is the sum of the 
previous two Fibonacci numbers.
This problem has a complexity of O(2^N) since the function
calls itself twice per function. 
"""


def fibonacci(n):
    if n == 1:
        return 1
    if n == 0:
        return 0

    print(n)
    return fibonacci(n - 1) + fibonacci(n - 2)


print(fibonacci(6))

"""
A recursive function to build a binary search tree. 
This takes O(N logN), N is the lenght of the input list
and the tree will be logN levels deep. 
"""


def build_bst(my_list):
    if not my_list:
        return 'No Child'

    middle_idx = len(my_list) // 2
    middle_value = my_list[middle_idx]
    print(f'Middle index: {middle_idx}')
    print(f'Middle value: {middle_value}')

    tree_node = {"data": middle_value}
    tree_node["left_child"] = build_bst(my_list[:middle_idx])
    tree_node["right_child"] = build_bst(my_list[middle_idx + 1:])
    return tree_node


# For testing
sorted_list = [12, 13, 14, 15, 16]
binary_search_tree = build_bst(sorted_list)
print(binary_search_tree)