text: ---
  title: Recursion
  ---
  
  There are three places recursion is commonly used: bindings, types, and modules.
  
  Feature  | Recursive           | Non-recursive
  ---------|---------------------|--------------
  Bindings | `let rec fn = ...`  | `let fn = ...`
  Types    | `type t = ...`      | `type nonrec t = ...`
  Modules  | `module rec A ...`  | `module A ...`
  
  ## Recursive Bindings
  
  By default the name of a binding is not available for use on the right side of
  that binding. This applies to all `let` bindings, including function
  definitions. This behavior is required for
  [Binding Shadowing](let-binding.md#binding-shadowing) to work:
  
  ```reason
  let x = 10;
  /* If bindings were recursive by default this would form a cycle and break */
  let x = x + 10;
  ```
  
  The natural way to write a recursive function will have an error:
  
  ```reason
  let infiniteRecursion = () => {
    /* Error: Unbound value infiniteRecursion */
    infiniteRecursion();
  };
  ```
  
  Opt-in to a recursive binding using the `rec` keyword:
  
  ```reason
  let rec infiniteRecursion = () => {
    infiniteRecursion();
  };
  ```
  
  ## Mutual Recursion
  
  Mutually recursive functions use the `and` keyword:
  
  ```reason
  let rec function1 = () => {
    function2();
  }
  and function2 = () => {
    function3();
  }
  and function3 = () => {
    function1();
  };
  ```
  
  - Note: The `and` keyword is not specific to recursion, it can be used without
  the `rec` keyword. Doing so would cause all bindings to be created
  simultaneously but _not_ visible to each other.
  
  ## Recursive Types
  
  Types, unlike bindings, are recursive by default. This is because it is
  common for types to be recursive and uncommon for types to be shadowed. A
  recursive type could be used to define a binary tree:
  
  ```reason
  type tree =
    | Leaf
    | Node(tree, tree);
  ```
  
  Opt-out of recursive types using the `nonrec` keyword:
  
  ```reason
  type t = string;
  type nonrec t = list(t);
  
  /* t is now list(string) */
  let x: t = ["hello", "world"];
  ```
  
  ## Mutually Recursive Types
  
  Types can be mutually recursive just like bindings using the `and` keyword:
  
  ```reason
  type node = {
    value: string,
    edges: list(edge),
  }
  and edge = {
    weight: int,
    next: node,
  };
  ```
  
  ## Mutually Recursive Modules
  
  Sometimes functions will be organized across modules and both modules need
  functions from each other. Use the `module rec` and `and` keywords for this
  kind of mutual recursion.
  
  _Note: Recursive modules require an explicit module type annotation._
  
  ```reason
  module type X = {
    let x: unit => int;
    let y: unit => int;
  };
  
  module rec A: X = {
    let x = () => 1;
    let y = () => B.y() + 1;
  }
  and B: X = {
    let x = () => A.x() + 2;
    let y = () => 2;
  };
  ```
  