tail-recursion.md

Item 57: Prefer Tail-Recursive Generic Types

Things to Remember

• Aim to make your recursive generic types tail recursive. They're more efficient and have greater depth limits.
• Recursive type aliases can often be made tail recursive by rewriting them to use an accumulator.

Code Samples

function sum(nums: readonly number[]): number {
  if (nums.length === 0) {
    return 0;
  }
  return nums[0] + sum(nums.slice(1));
}

console.log(sum([0, 1, 2, 3, 4]));

💻 playground

---

const arr = Array(7875).fill(1);
console.log(sum(arr));

💻 playground

---

function sum(nums: readonly number[], acc=0): number {
  if (nums.length === 0) {
    return acc;
  }
  return sum(nums.slice(1), nums[0] + acc);
}

💻 playground

---

type GetChars<S extends string> =
    S extends `${infer FirstChar}${infer RestOfString}`
    ? FirstChar | GetChars<RestOfString>
    : never;

type ABC = GetChars<"abc">;
//   ^? type ABC = "a" | "b" | "c"

💻 playground

---

type Long = GetChars<"abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWX">;
//          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
//          Type instantiation is excessively deep and possibly infinite.

💻 playground

---

type ToSnake<T extends string> =
    string extends T
    ? string  // We want ToSnake<string> = string
    : T extends `${infer First}${infer Rest}`
    ? (First extends Uppercase<First>  // Is First a capital letter?
      ? `_${Lowercase<First>}${ToSnake<Rest>}`  // e.g. "B" -> "_b"
      : `${First}${ToSnake<Rest>}`)
    : T;

type S = ToSnake<'fooBarBaz'>;
//   ^? type S = "foo_bar_baz"

type Two = ToSnake<'className' | 'tagName'>;
//   ^? type Two = "class_name" | "tag_name"

💻 playground

---

type Long = ToSnake<'reallyDescriptiveNamePropThatsALittleTooLoquacious'>;
//          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
//          Type instantiation is excessively deep and possibly infinite.

💻 playground

---

type ToSnake<T extends string, Acc extends string = ""> =
  string extends T
  ? string  // We want ToSnake<string> = string
  : T extends `${infer First}${infer Rest}`
  ? ToSnake<
      Rest,
      First extends Uppercase<First>
      ? `${Acc}_${Lowercase<First>}`
      : `${Acc}${First}`
    >
  : Acc;

type S = ToSnake<'fooBarBaz'>;
//   ^? type S = "foo_bar_baz"

type Two = ToSnake<'className' | 'tagName'>;
//   ^? type Two = "class_name" | "tag_name"

type Long = ToSnake<'reallyDescriptiveNamePropThatsALittleTooLoquacious'>;
//   ^? type Long = "really_descriptive_name_prop_thats_a_little_too_loquacious"

💻 playground