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.