<jupyter_start><jupyter_text>Recursion templates Sum of all numbers smaller than n Base Case: the scenario when recursion endsRecursive steps: the recursive lines that performs the recursion<jupyter_code>def sum_to_one(n):
  if n == 1:
    return n
  print("Recursing with input: {0}".format(n))
  return n + sum_to_one(n - 1)

# uncomment when you're ready to test
print(sum_to_one(7))<jupyter_output><empty_output><jupyter_text>Product of all numbers small than n<jupyter_code>def factorial(n):
  if n <= 1:
    return 1
  else:
    return n * factorial(n - 1)<jupyter_output><empty_output><jupyter_text>producing a list of all subsets of the values in a list<jupyter_code>def power_set(my_list):
    # base case: an empty list
    if len(my_list) == 0:
        return [[]]
    # recursive step: subsets without first element
    power_set_without_first = power_set(my_list[1:])
    # subsets with first element
    with_first = [ [my_list[0]] + rest for rest in power_set_without_first ]
    # return combination of the two
    return with_first + power_set_without_first
  
universities = ['MIT', 'UCLA', 'Stanford', 'NYU']
power_set_of_universities = power_set(universities)

for set in power_set_of_universities:
  print(set)<jupyter_output><empty_output><jupyter_text>flatten nested lists into a single, spread out list<jupyter_code>def flatten(my_list):
  result = []
  for el in my_list:
    if isinstance(el, list):
      print("list found!")
      flat_list = flatten(el)
      result += flat_list
    else:
      result.append(el)
  return result


### reserve for testing...
planets = ['mercury', 'venus', ['earth'], 'mars', [['jupiter', 'saturn']], 'uranus', ['neptune', 'pluto']]
print(flatten(planets))<jupyter_output><empty_output><jupyter_text>Fibonacci - the next value is the sum of previous 2 values<jupyter_code># define the fibonacci() function below...

def fibonacci(n):
  # base cases
  if n == 1:
    return n
  if n == 0:
    return n
  
  # recursive step
  print("Recursive call with {0} as input".format(n))
  return fibonacci(n - 1) + fibonacci(n - 2)


fibonacci(5)
# set the appropriate runtime:
# 1, logN, N, N^2, 2^N, N!
fibonacci_runtime = "2^N"<jupyter_output><empty_output><jupyter_text>Recursive data tree structure, like a decision tree<jupyter_code>def build_bst(my_list):
  if len(my_list) == 0:
    return "No Child"

  middle_idx = len(my_list) // 2
  middle_value = my_list[middle_idx]
  
  print("Middle index: {0}".format(middle_idx))
  print("Middle value: {0}".format(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
  
sorted_list = [12, 13, 14, 15, 16]
binary_search_tree = build_bst(sorted_list)
print(binary_search_tree)

# fill in the runtime as a string
# 1, logN, N, N*logN, N^2, 2^N, N!
runtime = "N*logN"<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.12211668928086838, 'fraction_numerical': 0.013229308005427409, 'mean_word_length': 4.671153846153846, 'pattern_counts': {'":': 1, '<': 26, '<?xml version=': 0, '>': 25, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '6', 'dir': 'jupyter-structured-clean-dedup', 'id': '653495', 'license': 'Apache-2.0', 'n_tokens_mistral': 1117, 'n_tokens_neox': 1070, 'n_words': 279, 'path': 'Data_Structure_and_Algo/Recursion.ipynb', 'repo_name': 'DieJobDeathCar/Teaching_Myself', 'size': '2948'}