← Back to Examples

05 Recursion

Demonstrates recursion with factorial, fibonacci, and list operations

Source Code

# Example 5: Recursive Functions
# Demonstrates recursion with factorial, fibonacci, and list operations

module Recursion do
  export [main/0]
  
  # Import standard library
  import Std.Show [show_int/1]
  import Std.Io [println/1]
  
  # Simple recursive factorial
  def factorial(n: Int): Int =
    match n <= 1 do
      true -> 1
      false -> n * factorial(n - 1)
    end
  
  # Recursive fibonacci
  def fibonacci(n: Int): Int =
    match n <= 1 do
      true -> n
      false -> fibonacci(n - 1) + fibonacci(n - 2)
    end
  
  # Recursive sum of list
  def sum_list(numbers: List(Int)): Int =
    match numbers do
      [] -> 0
      [h | t] -> h + sum_list(t)
    end
  
  # Recursive count of list elements
  def count_list(items: List(Int)): Int =
    match items do
      [] -> 0
      [_ | t] -> 1 + count_list(t)
    end
  
  # Main demonstration
  def main(): Int =
    println("=== Recursion Demo ===")
    println("")
    
    # Test 1: Factorial
    println("Test 1: Factorial of 5")
    let fact5 = factorial(5)
    println("Result: " <> show_int(fact5) <> " (120 expected)")
    println("")
    
    # Test 2: Fibonacci
    println("Test 2: Fibonacci of 7")
    let fib7 = fibonacci(7)
    println("Result: " <> show_int(fib7) <> " (13 expected)")
    println("")
    
    # Test 3: Sum of list
    println("Test 3: Sum of [1, 2, 3, 4, 5]")
    let numbers = [1, 2, 3, 4, 5]
    let total = sum_list(numbers)
    println("Result: " <> show_int(total) <> " (15 expected)")
    println("")
    
    # Test 4: Count list
    println("Test 4: Count elements in [10, 20, 30]")
    let items = [10, 20, 30]
    let count = count_list(items)
    println("Result: " <> show_int(count) <> " (3 expected)")
    println("")
    
    println("=== Demo Complete ===")
    0
end