Skip to main content

Documentation Index

Fetch the complete documentation index at: https://mintlify.com/tutosrive/ed/llms.txt

Use this file to discover all available pages before exploring further.

Workshop 1 explores four classic recursive problems implemented in Python. Each exercise introduces a distinct recursion pattern — either LIFO (stack/last-in-first-out) or FIFO (tail/first-in-first-out) — building a practical foundation for reasoning about call-stack depth, accumulated state, and memoization. All exercises were authored by Santiago Rivera Marín (4th Semester, Data Structures, UCALDAS) and run in Google Colab.
Open this workshop in Google Colab → https://colab.research.google.com/github/tutosrive/ED/blob/from_colab/workshops/colab/workshop_1_ED.ipynb

​
Exercise 1 — Binary Search (LIFO)

Implement a recursive algorithm that, given a sorted list and a target value, returns the index of the element or -1 if it is not found. The function uses LIFO (stack) recursion: each call pushes a new frame onto the call stack and waits for the recursive result before returning. How it works:
  1. Compute the midpoint medio = (left + right) // 2.
  2. Base case — not found: if medio exceeds the list bounds or right < left, return -1.
  3. Base case — found: if lista[medio] == value, return medio.
  4. Recursive step: narrow the search window to the right half (left = medio + 1) or the left half (right = medio - 1), then recurse.
binary_search.py
from typing import Union

def binary_search(lista: list, value: int, left: int, right: int):
    medio = (left + right) // 2

    # Base Case

    if medio > (len(lista) - 1) or right < left:
        # Value not exists in list
        return -1
    elif lista[medio] == value:
        # Found value
        return medio

    if value > lista[medio]:
        # Carry out the recursion to right side
        left = medio + 1
    else:
        # Carry out the recursion to left side
        right = medio - 1

    return binary_search(lista, value, left, right)

# "Tests"
list_integer: list[int] = [4, 2, 1, 6, 7, 3, 8, 12, 5, 9, 13]
list_integer.sort()
print(f"{list_integer=}")
# list_integer=[1, 2, 3, 4, 5, 6, 7, 8, 9, 12, 13]

int_to_find: int = 127

left, right = 0, len(list_integer)
index: Union[int, None] = binary_search(list_integer, int_to_find, left, right)

print(f"{index=}")
# index=-1
The list must be sorted before calling binary_search. The example above calls list_integer.sort() before searching. Passing an unsorted list produces incorrect results.

​
Exercise 2 — Factorial

Two versions of factorial are implemented to contrast the two main recursion styles.

​
LIFO Version (Stack Recursion)

The LIFO version mirrors classical mathematical recursion. Each call to factorial_pila suspends until the deeper call returns, building the product on the way back up the call stack.
factorial_lifo.py
# If n == 5
# Factorial(n) = 5x4x3x2x1 = 120
# Base Case: n == 2 (Any value by 1 is the same value)

def factorial_pila(n: int):
    if n < 0:
        # Not missing the joker...
        return -1
    elif n == 0:
        return 0
    elif n in [2, 1]:
        return n

    return n * factorial_pila(n - 1)

# Tests
n: int = -10

fact_pila: int = factorial_pila(n)
print(f"The factorial of {n} (Using LIFO), is: {fact_pila}")

​
FIFO Version (Tail / Accumulator Recursion)

The FIFO version uses a mutable list as an accumulator (array[0]). The multiplication happens before the recursive call — the function passes accumulated state forward rather than waiting to multiply on the way back. This is the tail-recursive pattern.
factorial_fifo.py
# If n == 5
# Factorial(n) = 5x4x3x2x1 = 120
# Base Case: n == 2 (Any value by 1 is the same value)

def factorial_cola(n: int, array: list[int]):
    if n < 0:
        # Not missing the joker...
        array[0] = -1
    elif n == 0:
        array[0] = 0
    elif n > 1:
        # Only if array[0] from begin is 1
        # To can get the product (array[0] * n)...
        array[0] *= n   # Accumulate before recursing
        factorial_cola(n - 1, array)

# Tests
n: int = 10

fact_cola: list[int] = [1]

factorial_cola(n, fact_cola)
print(f"The factorial of {n} (Using FIFO), is: {fact_cola[0]}")
The FIFO version passes array by reference (a single-element list acts as a mutable box). This avoids returning a value and lets the accumulator carry state across all recursive frames without waiting for any of them to return.

​
Exercise 3 — List Sum (FIFO)

Compute the sum of all elements in a list using FIFO (tail) recursion. The running total is stored in the single-element list sum, which is updated before each recursive call — no return value is needed.
list_sum.py
# Base Case: When n reaches len(list)

def list_sum(index: int, array: list[int], sum: list[int]) -> None:
    if index >= 0 and index < len(array):
        sum[0] += array[index]
        list_sum(index + 1, array, sum)

# Tests

sum: list[int] = [0]

num_array: list[int] = [0, 1, 2, 3, 4]
i: int = 0

list_sum(i, num_array, sum)

print(f"The addition of all elements is (FIFO): {sum[0]}")
Trace for [0, 1, 2, 3, 4]:
Callindexarray[index]sum[0] after step
1000
2111
3223
4336
54410
65—(base case, stop)

​
Exercise 4 — Fibonacci

Two Fibonacci implementations are presented: a tail-recursive version and a memoized version.

​
Tail-Recursive Version

State is carried forward through the left and right parameters; the result is stored in the mutable accumulator suma. No multiplication or addition happens on the return path.
fibonacci_tail.py
def fibonacci(n: int, suma: list[int] = [0], left: int = 0, right: int = 1):
    # To avoid use the Return
    if not n in [0, 1]:
        suma[0] = left + right

        print(f'{left=} ------ {right=} ------- {suma=}')

        # Like bubble sort
        left, right = right, suma[0]
        fibonacci(n - 1, suma, left, right)

# "Tests"
# left, right = 0, 1

suma = [0]
n: int = 15

fibonacci(n, suma)

print(f"The Fibonacci Serie for {n} is: {suma[0]}")
Default mutable arguments (suma: list[int] = [0]) are shared across calls in Python. Always pass an explicit accumulator when calling fibonacci multiple times in the same session, e.g. fibonacci(15, [0]).

​
Memoized Version

The memoized version uses a dictionary (values) to cache already-computed Fibonacci numbers. Before recursing, the function checks whether the value is already known, avoiding redundant subtree evaluations.
fibonacci_memoized.py
def fibonacci_2(n: int, values: dict):
    # Base Case
    if n in [0, 1]:
        return n

    left, right = n - 1, n - 2

    # Case n-1 values already!
    if values.get(left):
        left = values[left]
    else:
        values[left] = fibonacci_2(left, values)
        left = values[left]

    # Case n-2 values already!
    if values.get(right):
        left = values[right]
    else:
        values[right] = fibonacci_2(right, values)
        right = values[right]

    # Missing the n: x
    return values[n - 1] + values[n - 2]


# Tests

dict_values: dict = {0: 0, 1: 1}
n: int = 15

fibo: int = fibonacci_2(n, dict_values)

print(dict_values)
print(f"The Fibonacci Serie for {n} is: {fibo}")
The memoized version reduces time complexity from O(2ⁿ) (naïve recursion) to O(n) because each subproblem is computed at most once and stored in values.

​
Summary

ExerciseAlgorithmRecursion TypeKey Technique
1Binary SearchLIFO (Stack)Halving search window on each call
2FactorialLIFO / FIFOReturn value vs. mutable accumulator
3List SumFIFO (Tail)Index advance with shared accumulator
4FibonacciFIFO / MemoizedTail state passing + dict cache

Build docs developers (and LLMs) love

Get started for freeTalk to us