Skip to content

Instantly share code, notes, and snippets.

# Edald123/recursion.py

Created August 3, 2021 04:38
Recursion in Python
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 """ 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)
to join this conversation on GitHub. Already have an account? Sign in to comment