Algorithms

Implemented — the algorithm examples are real, runnable programs under examples/algorithms/. The corpus contains 21 programs (absolute_value, bellman, bfs, binary, bubble, dfs, dijkstra, factorial, fibonacci, gcd, heap, kadane, knapsack, lcm, levenshtein, linear, merge, power, quick, sieve, ternary).

The Phase 114/116 flat corpus examples/02-algorithms/ adds a second, teaching-sized set of thirteen single-file programs — linear/binary search, min/max, bubble sort, frequency count, Fibonacci, factorial, GCD, prime sieve, palindrome, plus an array stack, an array queue and a 0/1-knapsack dynamic-programming table — each pinned byte-identical on both engines by pkg/cli/phase114_examples_test.go.

This page documents the classical recursion/iteration set: factorial, fibonacci, gcd, lcm, power and sieve. All outputs below were captured by running each program through karkain run on the default engine.


Fibonacci

examples/algorithms/fibonacci/main.kark — naive recursive Fibonacci:

func fib(n) {
    if (n <= 1) {
        return n
    }
    return fib(n - 1) + fib(n - 2)
}

func main() {
    print("Fibonacci(10):")
    print(fib(10))
    print("Fibonacci(20):")
    print(fib(20))
}

Expected output (verified):

Fibonacci(10):
55
Fibonacci(20):
6765

Factorial

examples/algorithms/factorial/main.kark:

func factorial(n) {
    if (n <= 1) {
        return 1
    }
    return n * factorial(n - 1)
}

func main() {
    print("Factorial of 5:")
    print(factorial(5))
    print("Factorial of 10:")
    print(factorial(10))
}

Expected output (verified):

Factorial of 5:
120
Factorial of 10:
3628800

GCD

examples/algorithms/gcd/main.kark — Euclid’s algorithm:

func gcd(a, b) {
    if (b == 0) {
        return a
    }
    return gcd(b, a % b)
}

func main() {
    print("GCD(48, 36):")
    print(gcd(48, 36))
    print("GCD(270, 192):")
    print(gcd(270, 192))
}

Expected output (verified):

GCD(48, 36):
12
GCD(270, 192):
6

LCM

examples/algorithms/lcm/main.kark — least common multiple via gcd:

func gcd(a, b) {
    if (b == 0) {
        return a
    }
    return gcd(b, a % b)
}

func lcm(a, b) {
    return (a * b) / gcd(a, b)
}

func main() {
    print("LCM(4, 6):")
    print(lcm(4, 6))
    print("LCM(21, 6):")
    print(lcm(21, 6))
}

Expected output (verified):

LCM(4, 6):
12
LCM(21, 6):
42

Power

examples/algorithms/power/main.kark — iterative exponentiation:

func power(base, exp) {
    let result = 1
    let i = 0
    while (i < exp) {
        result = result * base
        i = i + 1
    }
    return result
}

func main() {
    print("2^10:")
    print(power(2, 10))
    print("3^4:")
    print(power(3, 4))
}

Expected output (verified):

2^10:
1024
3^4:
81

Sieve

examples/algorithms/sieve/main.kark — trial-division prime collection:

func is_prime(n) {
    if (n < 2) {
        return 0
    }
    let d = 2
    while (d * d <= n) {
        if (n % d == 0) {
            return 0
        }
        d = d + 1
    }
    return 1
}

func main() {
    let limit = 30
    let primes = []
    let n = 2
    while (n <= limit) {
        if (is_prime(n)) {
            push(primes, n)
        }
        n = n + 1
    }
    print("Primes up to 30:")
    let i = 0
    while (i < len(primes)) {
        print(primes[i])
        i = i + 1
    }
}

Expected output (verified):

Primes up to 30:
2
3
5
7
11
13
17
19
23
29

Array stack and queue

examples/02-algorithms/11_stack.kark — a pointer-based stack over the language’s dynamic array type (push via the array, pop by moving the top pointer):

// Status: Runnable
// Engine: both (Go front end + self-hosted kcc)
// Category: 02 Algorithms
//
// A stack (last-in, first-out) built on the dynamic array type with a moving
// top pointer. push() appends via the array, the top pointer tracks the
// current head, and each pop just walks the pointer back down. This is LIFO
// discipline over the language's arrays, not a library type.
//
// Run:  karkain run examples/02-algorithms/11_stack.kark

func main() {
    let stack = [10, 20, 30]
    var top = len(stack) - 1

    print(len(stack))          // 3 items pushed
    print(stack[top])          // top of stack = 30

    top = top - 1              // pop 30
    print(stack[top])          // 20
    top = top - 1              // pop 20
    print(stack[top])          // 10
    print(top)                 // one item remains (pointer at 0)
}

examples/02-algorithms/12_queue.kark — a FIFO queue with a moving head index:

// Status: Runnable
// Engine: both (Go front end + self-hosted kcc)
// Category: 02 Algorithms
//
// A queue (first-in, first-out) with a moving head index. push() grows the
// tail; dequeuing advances the head without copying the array. The final
// walk drains every live element in FIFO order.
//
// Run:  karkain run examples/02-algorithms/12_queue.kark

func main() {
    var q = [10, 20, 30, 40]
    var head = 0

    print(q[head])          // dequeue 10
    head = head + 1
    print(q[head])          // dequeue 20

    push(q, 50)             // enqueue behind 40
    print(q[len(q) - 1])    // 50 is now the tail

    while (head < len(q)) {
        print(q[head])      // drain 30, 40, 50 in order
        head = head + 1
    }
}

0/1 knapsack (dynamic programming)

examples/02-algorithms/13_knapsack.kark — a two-dimensional DP table built from arrays; answers are exact and deterministic:

// Status: Runnable
// Engine: both (Go front end + self-hosted kcc)
// Category: 02 Algorithms
//
// The 0/1 knapsack problem solved with dynamic programming over a 2D table:
// dp[i][c] is the best value using the first i items with capacity c. The
// table is built from arrays; answers are exact and deterministic.
//
// Run:  karkain run examples/02-algorithms/13_knapsack.kark

func knapsack(capacity, weights, values, count) {
    var dp = []
    let i = 0
    while (i <= count) {
        let row = []
        let c = 0
        while (c <= capacity) {
            push(row, 0)
            c = c + 1
        }
        push(dp, row)
        i = i + 1
    }

    i = 1
    while (i <= count) {
        let c = 1
        while (c <= capacity) {
            let without = dp[i - 1][c]
            if (weights[i - 1] > c) {
                dp[i][c] = without
            } else {
                let with = dp[i - 1][c - weights[i - 1]] + values[i - 1]
                if (with > without) {
                    dp[i][c] = with
                } else {
                    dp[i][c] = without
                }
            }
            c = c + 1
        }
        i = i + 1
    }

    return dp[count][capacity]
}

func main() {
    let weights = [2, 3, 4, 5]
    let values = [3, 4, 5, 6]

    print(knapsack(5, weights, values, 4))   // choose (2,3)+(3,4) = 7
    print(knapsack(7, weights, values, 4))   // best of (2,3)+(5,6) / (3,4)+(4,5)
}

Expected outputs (verified on both engines):

3
30
20
10
0
10
20
50
20
30
40
50
7
9

Note on arrays

Arrays are passed by value into functions. push(primes, n) above mutates a variable in the same scope; to grow an array inside a helper and see the result in the caller, capture the returned array (arr = push(arr, v)). This is a documented behavior, not a defect — see the showcase notes in examples/showcase/README.md.

The graph-algorithm programs (bfs, dfs, dijkstra, bellman) and the sorting programs (bubble, merge, quick, heap) follow the same conventions and are validated by the same gates.

See also

Fundamentals — the language foundation behind these programs. Karkain Language Guide — the language guide.