Recursion in Nim

Our example demonstrates recursive functions in Nim. Here’s a classic implementation of factorial calculation using recursion.

import std/strformat

# This `fact` function calls itself until it reaches the
# base case of `fact(0)`.
proc fact(n: int): int =
  if n == 0:
    return 1
  return n * fact(n - 1)

proc main() =
  echo fmt"Factorial of 7 is {fact(7)}"

  # In Nim, we can define recursive anonymous functions (lambdas)
  # directly without needing to declare them separately.
  let fib = proc(n: int): int =
    if n < 2:
      return n
    return fib(n - 1) + fib(n - 2)

  echo fmt"7th Fibonacci number is {fib(7)}"

main()

In this example, we define two recursive functions:

1. fact: A classic factorial function that recursively calculates the factorial of a given number.
2. fib: A Fibonacci sequence generator implemented as an anonymous recursive function.

The fact function demonstrates simple recursion, calling itself with a decremented value until it reaches the base case of 0.

For the Fibonacci sequence, we use an anonymous function (lambda) that’s assigned to the fib variable. In Nim, we can define recursive anonymous functions directly, which is a bit simpler than some other languages that require forward declarations.

To run this program, save it as recursion.nim and use the Nim compiler:

$ nim c -r recursion.nim
Factorial of 7 is 5040
7th Fibonacci number is 13

This example showcases how Nim supports recursive functions, both named and anonymous, providing flexibility in implementing algorithms that benefit from recursive approaches.