# Generated from the published Markdown; run scripts/build_language_examples.py to refresh.
# Independent examples may reuse top-level names. Python remains the explanation language.


# topics/recursion/recursive-calls.md
def sum_to(n):
    if type(n) is not int or n < 0:
        raise ValueError("Expected a nonnegative integer")
    if n == 0:
        return 0
    return n + sum_to(n - 1)

print(sum_to(3))  # 6
print(sum_to(0))  # 0

# topics/recursion/call-stack.md
def trace_calls(n):
    if n == 0:
        print("base")
        return
    print("enter", n)
    trace_calls(n - 1)
    print("leave", n)

trace_calls(2)

# topics/recursion/call-stack.md
def sum_to_iterative(n):
    if type(n) is not int or n < 0:
        raise ValueError("Expected a nonnegative integer")
    total = 0
    for value in range(1, n + 1):
        total += value
    return total

print(sum_to_iterative(3))  # 6

# topics/recursion/divide-and-conquer.md
def merge_sorted(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

def merge_sort(values):
    if len(values) <= 1:
        return values.copy()
    middle = len(values) // 2
    left = merge_sort(values[:middle])
    right = merge_sort(values[middle:])
    return merge_sorted(left, right)

values = [38, 12, 27, 5, 19, 8, 31, 14]
print(merge_sort(values))  # [5, 8, 12, 14, 19, 27, 31, 38]