Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Recursion in Python
"""
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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment