Recursion in Crystal

Our example demonstrates recursive functions in Crystal. Here’s a classic implementation of factorial:

# This `fact` function calls itself until it reaches the
# base case of `fact(0)`.
def fact(n : Int32) : Int32
  if n == 0
    1
  else
    n * fact(n - 1)
  end
end

puts fact(7)

# Proc objects can also be recursive, but this requires the
# proc to be declared before it's defined.
fib = ->(n : Int32) { Int32 }

fib = ->(n : Int32) {
  if n < 2
    n
  else
    # Since `fib` was previously declared, Crystal
    # knows which proc to call with `fib` here.
    fib.call(n - 1) + fib.call(n - 2)
  end
}

puts fib.call(7)

When you run this program, you’ll see:

$ crystal run recursion.cr
5040
13

This example showcases two types of recursion in Crystal:

1. A standard recursive function fact that calculates the factorial of a number.
2. A recursive Proc object fib that calculates Fibonacci numbers.

The fact function is straightforward: it calls itself with n - 1 until it reaches the base case of 0.

The fib Proc demonstrates how to create a recursive closure in Crystal. We first declare fib with a type signature, then define it. This allows fib to call itself within its own definition.

Crystal’s type system requires explicit type annotations for recursive Procs, which is why we specify the argument and return types.

Remember, while recursion can lead to elegant solutions for some problems, it’s important to be mindful of the stack usage, especially for deep recursions.