# Recursion and Functional Composition

This guide shows how to express recursion (including mutual recursion) and how to build programs by composing small functions...probably read the [documentation about functional programming](./01_functional.md) before this.

## Simple Recursion
```baba
// Factorial
factorial : n ->
  when n is
    0 then 1
    1 then 1
    _ then n * (factorial (n - 1));

// Fibonacci
fibonacci : n ->
  when n is
    0 then 0
    1 then 1
    _ then (fibonacci (n - 1)) + (fibonacci (n - 2));
```

## Tail-Recursion with an Accumulator
```baba
// Sum of digits using an accumulator
sumDigits : n acc ->
  when n is
    0 then acc
    _ then sumDigits (n / 10) (acc + (n % 10));

sumDigitsStart : n -> sumDigits n 0;
```

## Mutual Recursion
```baba
// Using with rec in a header to define mutually recursive locals
isEvenOdd : z -> with rec (
  isEven : n ->
    when n is
      0 then true
      _ then isOdd (n - 1);
  isOdd : n ->
    when n is
      0 then false
      _ then isEven (n - 1);
) -> { even: isEven 10, odd: isOdd 7 };
```

## Function Composition

Baba Yaga provides built-in function combinators for composition. For detailed documentation, see [Functional Programming](./01_functional.md#function-combinators).

```baba
inc    : x -> x + 1;
double : x -> x * 2;

// Built-in compose (right-to-left): f(g(x))
composed : compose inc double;
r1 : composed 3; // inc (double 3) = 7

// Built-in pipe (left-to-right): value |> function  
r2 : pipe 3 inc;        // inc 3 = 4
r3 : pipe 4 double;     // double 4 = 8
```

## Composing Many Functions

You can compose an arbitrary list of unary functions using `reduce`.

```baba
// composeAll [f, g, h] = x -> f (g (h x))
composeAll : funcs ->
  reduce (acc fn -> (x -> acc (fn x))) (x -> x) funcs;

inc    : x -> x + 1;
double : x -> x * 2;

combo : composeAll [inc, double];
res   : combo 3; // inc (double 3) = 7
```

## Recursion with Utility Functions

Using the enhanced utility functions for recursive algorithms:

```baba
// Recursive data processing with validation
processNumbers : numbers ->
  when (validate.notEmpty numbers) is
    false then []
    true then
      with (
        sorted : sort.by numbers (x -> x);
        chunks : chunk sorted 3;
        processed : map (chunk -> reduce (acc x -> acc + x) 0 chunk) chunks;
      ) ->
        processed;

// Recursive tree traversal with debugging
traverseTree : tree ->
  with rec (
    // Debug each node we visit
    visitNode : node ->
      when (validate.notEmpty (keys node)) is
        false then (debug.print "Empty node"; 0)
        true then 
          with (value : node.value;) ->
            (debug.print "Visiting" value; value);
    
    // Recursive traversal
    traverse : node ->
      when (validate.notEmpty (keys node)) is
        false then 0
        true then 
          (visitNode node) + 
          (traverse node.left) + 
          (traverse node.right);
  ) ->
    traverse tree;

// Generate and process sequences recursively
fibonacci : n ->
  when (validate.range 0 100 n) is
    false then (assert false "n must be 0-100"; 0)
    true then
      when n is
        0 then 0
        1 then 1
        _ then (fibonacci (n - 1)) + (fibonacci (n - 2));

// Generate fibonacci sequence using range and recursion
fibSequence : count ->
  with (indices : range 0 (count - 1);) ->
    map fibonacci indices;

// Example: fibSequence 10 generates [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
```