def sum_list(items):
    """Sum all elements by reducing the problem one element at a time."""
    if not items:          # Base case: empty list sums to 0
        return 0
    return items[0] + sum_list(items[1:])  # Current + solution to smaller problem

def fibonacci(n):
    """Fibonacci needs TWO base cases because it references two prior values."""
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

# Calling factorial(4):

# Recursive — O(2ⁿ) time, O(n) stack space
def fib_recursive(n):
    if n <= 1:
        return n
    return fib_recursive(n - 1) + fib_recursive(n - 2)

# Iterative — O(n) time, O(1) space
def fib_iterative(n):
    if n <= 1:
        return n
    prev, curr = 0, 1
    for _ in range(2, n + 1):
        prev, curr = curr, prev + curr
    return curr

# NOT tail-recursive: multiplication happens AFTER the recursive call returns
def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)  # must multiply after return

# Tail-recursive: accumulator carries the result forward
def factorial_tail(n, accumulator=1):
    if n == 0:
        return accumulator
    return factorial_tail(n - 1, n * accumulator)  # nothing after this call

def power(base, exp):
    """Calculate base^exp using recursive halving — O(log n)."""
    if exp == 0:
        return 1
    if exp % 2 == 0:
        half = power(base, exp // 2)
        return half * half
    else:
        return base * power(base, exp - 1)

def binary_search(arr, target, low=0, high=None):
    """Search sorted array recursively — O(log n)."""
    if high is None:
        high = len(arr) - 1
    if low > high:
        return -1  # Base case: not found

    mid = (low + high) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search(arr, target, mid + 1, high)
    else:
        return binary_search(arr, target, low, mid - 1)

class TreeNode:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def inorder(node):
    """Left → Root → Right (gives sorted order for BSTs)."""
    if node is None:
        return []
    return inorder(node.left) + [node.value] + inorder(node.right)

def preorder(node):
    """Root → Left → Right (useful for copying/serialising trees)."""
    if node is None:
        return []
    return [node.value] + preorder(node.left) + preorder(node.right)

def tree_height(node):
    """Height = 1 + max height of subtrees."""
    if node is None:
        return 0
    return 1 + max(tree_height(node.left), tree_height(node.right))

import os

def find_files(directory, extension):
    """Recursively find all files with a given extension."""
    results = []
    for entry in os.listdir(directory):
        full_path = os.path.join(directory, entry)
        if os.path.isdir(full_path):
            results.extend(find_files(full_path, extension))  # Recurse into subdirectory
        elif entry.endswith(extension):
            results.append(full_path)
    return results

# Usage: find_files("/home/user/projects", ".py")

def permutations(items):
    """Generate all orderings of items."""
    if len(items) <= 1:
        return [items]
    result = []
    for i, item in enumerate(items):
        rest = items[:i] + items[i+1:]
        for perm in permutations(rest):
            result.append([item] + perm)
    return result

# permutations([1, 2, 3]) → [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

def inorder_iterative(root):
    """Iterative in-order traversal using an explicit stack."""
    result = []
    stack = []
    current = root

    while current or stack:
        while current:
            stack.append(current)
            current = current.left
        current = stack.pop()
        result.append(current.value)
        current = current.right

    return result