Рекурсия

int factorial(int n) {
    if (n <= 1) return 1;          // базовое условие
    return n * factorial(n - 1);   // шаг к более простой задаче
}

func factorial(n int) int {
	if n <= 1 {
		return 1 // базовое условие
	}
	return n * factorial(n-1) // шаг к более простой задаче
}

function factorial(n) {
  if (n <= 1) return 1;          // базовое условие
  return n * factorial(n - 1);   // шаг к более простой задаче
}

def factorial(n: int) -> int:
    if n <= 1:
        return 1                    # базовое условие
    return n * factorial(n - 1)     # шаг к более простой задаче

живой пример

public class Factorial {
    static int depth = 0;

    static int factorial(int n) {
        System.out.println("  ".repeat(depth++) + "вызвали factorial(" + n + ")");
        int result = (n <= 1) ? 1 : n * factorial(n - 1);
        System.out.println("  ".repeat(--depth) + "вернули " + result);
        return result;
    }

    public static void main(String[] args) {
        factorial(4);
    }
}

живой пример

package main

import (
	"fmt"
	"strings"
)

var depth = 0

func factorial(n int) int {
	fmt.Printf("%sвызвали factorial(%d)\n", strings.Repeat("  ", depth), n)
	depth++
	result := 1
	if n > 1 {
		result = n * factorial(n-1)
	}
	depth--
	fmt.Printf("%sвернули %d\n", strings.Repeat("  ", depth), result)
	return result
}

func main() {
	factorial(4)
}

живой пример

let depth = 0;

function factorial(n) {
  console.log("  ".repeat(depth++) + `вызвали factorial(${n})`);
  const result = n <= 1 ? 1 : n * factorial(n - 1);
  console.log("  ".repeat(--depth) + `вернули ${result}`);
  return result;
}

factorial(4);

живой пример

depth = 0


def factorial(n: int) -> int:
    global depth
    print("  " * depth + f"вызвали factorial({n})")
    depth += 1
    result = 1 if n <= 1 else n * factorial(n - 1)
    depth -= 1
    print("  " * depth + f"вернули {result}")
    return result


factorial(4)

живой пример

public class Hanoi {
    static long moves = 0;

    static void move(int n, char from, char to, char via) {
        if (n == 0) return;
        move(n - 1, from, via, to);
        moves++;
        move(n - 1, via, to, from);
    }

    public static void main(String[] args) {
        for (int n : new int[]{3, 10, 20}) {
            moves = 0;
            move(n, 'A', 'C', 'B');
            System.out.println(n + " дисков: " + moves + " ходов");
        }
    }
}

живой пример

package main

import "fmt"

var moves int64

func move(n int, from, to, via byte) {
	if n == 0 {
		return
	}
	move(n-1, from, via, to)
	moves++
	move(n-1, via, to, from)
}

func main() {
	for _, n := range []int{3, 10, 20} {
		moves = 0
		move(n, 'A', 'C', 'B')
		fmt.Printf("%d дисков: %d ходов\n", n, moves)
	}
}

живой пример

let moves = 0;

function move(n, from, to, via) {
  if (n === 0) return;
  move(n - 1, from, via, to);
  moves++;
  move(n - 1, via, to, from);
}

for (const n of [3, 10, 20]) {
  moves = 0;
  move(n, "A", "C", "B");
  console.log(`${n} дисков: ${moves} ходов`);
}

живой пример

moves = 0


def move(n: int, source: str, target: str, via: str) -> None:
    global moves
    if n == 0:
        return
    move(n - 1, source, via, target)
    moves += 1
    move(n - 1, via, target, source)


for n in (3, 10, 20):
    moves = 0
    move(n, "A", "C", "B")
    print(f"{n} дисков: {moves} ходов")

живой пример

import java.util.Arrays;

public class MergeSort {
    static void sort(int[] a, int[] buf, int lo, int hi) {
        if (hi - lo < 2) return;
        int mid = (lo + hi) >>> 1;
        sort(a, buf, lo, mid);
        sort(a, buf, mid, hi);
        int i = lo, j = mid, k = lo;
        while (i < mid && j < hi) buf[k++] = a[i] <= a[j] ? a[i++] : a[j++];
        while (i < mid) buf[k++] = a[i++];
        while (j < hi) buf[k++] = a[j++];
        System.arraycopy(buf, lo, a, lo, hi - lo);
    }

    public static void main(String[] args) {
        int[] a = {38, 27, 43, 3, 9, 82, 10};
        sort(a, new int[a.length], 0, a.length);
        System.out.println(Arrays.toString(a));
    }
}

живой пример

package main

import "fmt"

func mergeSort(a, buf []int, lo, hi int) {
	if hi-lo < 2 {
		return
	}
	mid := int(uint(lo+hi) >> 1)
	mergeSort(a, buf, lo, mid)
	mergeSort(a, buf, mid, hi)
	i, j, k := lo, mid, lo
	for i < mid && j < hi {
		if a[i] <= a[j] {
			buf[k] = a[i]
			i++
		} else {
			buf[k] = a[j]
			j++
		}
		k++
	}
	for i < mid {
		buf[k] = a[i]
		i++
		k++
	}
	for j < hi {
		buf[k] = a[j]
		j++
		k++
	}
	copy(a[lo:hi], buf[lo:hi])
}

func main() {
	a := []int{38, 27, 43, 3, 9, 82, 10}
	mergeSort(a, make([]int, len(a)), 0, len(a))
	fmt.Println(a)
}

живой пример

function mergeSort(a, buf, lo, hi) {
  if (hi - lo < 2) return;
  const mid = (lo + hi) >>> 1;
  mergeSort(a, buf, lo, mid);
  mergeSort(a, buf, mid, hi);
  let i = lo, j = mid, k = lo;
  while (i < mid && j < hi) buf[k++] = a[i] <= a[j] ? a[i++] : a[j++];
  while (i < mid) buf[k++] = a[i++];
  while (j < hi) buf[k++] = a[j++];
  for (let t = lo; t < hi; t++) a[t] = buf[t];
}

const a = [38, 27, 43, 3, 9, 82, 10];
mergeSort(a, new Array(a.length), 0, a.length);
console.log(a);

живой пример

def merge_sort(a: list, buf: list, lo: int, hi: int) -> None:
    if hi - lo < 2:
        return
    mid = (lo + hi) // 2
    merge_sort(a, buf, lo, mid)
    merge_sort(a, buf, mid, hi)
    i, j, k = lo, mid, lo
    while i < mid and j < hi:
        if a[i] <= a[j]:
            buf[k] = a[i]
            i += 1
        else:
            buf[k] = a[j]
            j += 1
        k += 1
    while i < mid:
        buf[k] = a[i]
        i += 1
        k += 1
    while j < hi:
        buf[k] = a[j]
        j += 1
        k += 1
    a[lo:hi] = buf[lo:hi]


a = [38, 27, 43, 3, 9, 82, 10]
merge_sort(a, [0] * len(a), 0, len(a))
print(a)

Сортировку слиянием, которую мы только что разобрали, писать самому не нужно — она уже есть в стандартной библиотеке. Но выбирать между вариантами приходится, и для этого полезно знать, что именно вызывается.

Collections.sort(list), list.sort(comparator) и Arrays.sort(Object[]) — это один и тот же алгоритм, TimSort: доработанная сортировка слиянием. Она сначала ищет во входных данных куски, уже идущие по возрастанию или убыванию, и только потом сливает их попарно. На частично упорядоченных данных (а такие в жизни сплошь и рядом — дозагруженный список, чуть изменённая выборка) она приближается к O(N), в худшем случае даёт честные O(N·log N) и при этом устойчива: элементы с равными ключами сохраняют исходный взаимный порядок. Платит она памятью под временный массив, но экономнее классического слияния: тому нужен буфер на весь массив, а TimSort обходится буфером до половины длины.

С примитивами вызывается другое. Arrays.sort(int[]) — не слияние, а быстрая сортировка с двумя опорными элементами и защитой от неудачных входов: она сортирует по месту, но неустойчива. У примитивов устойчивость и не наблюдаема (две одинаковые пятёрки неразличимы), так что подмена безобидна — важно лишь помнить, что за одним именем Arrays.sort живут два разных алгоритма с разными свойствами по памяти.

Грабля у TimSort одна, зато коварная: он полагается на корректность компаратора. Самый частый способ его сломать — сравнение вычитанием, (a, b) -> a.getValue() - b.getValue(): на больших значениях вычитание переполняется, знак получается обратным, порядок перестаёт быть согласованным, и сортировка падает с IllegalArgumentException: Comparison method violates its general contract!. Падает не всегда, а только когда данных достаточно много и легли они неудачно, поэтому ошибка любит вылезать на большом объёме, а не на маленькой проверке. Переполнение видно и на двух числах:

живой пример

public class CompareTrap {
    public static void main(String[] args) {
        int a = 2_000_000_000, b = -2_000_000_000;
        System.out.println("на самом деле a больше b: " + (a > b));
        System.out.println("так не надо, a - b: " + (a - b));
        System.out.println("так надо, Integer.compare: " + Integer.compare(a, b));
    }
}

Разность отрицательна, хотя a больше: вычитание вышло за диапазон int. Поэтому в компараторе берут готовое сравнение — Comparator.comparingInt(Item::getValue).

Второе, что стоит знать, — про сам стек вызовов. Его размер у потока ограничен (по умолчанию порядка мегабайта, задаётся ключом -Xss), и глубокая рекурсия упирается в этот предел ошибкой StackOverflowError. Точную глубину назвать нельзя — она зависит от того, сколько места занимает кадр одного вызова, — но порядок такой: у совсем простого метода стек кончается на десятках тысяч вложенных вызовов, у метода с несколькими локальными переменными заметно раньше. То есть глубина в сотни тысяч в Java недостижима в принципе, и «рекурсия по миллиону элементов» не работает даже там, где выглядит безобидно.

Спасти могла бы хвостовая рекурсия — это когда рекурсивный вызов стоит в методе последним действием и его результат сразу возвращают, ничего с ним больше не делая. Такому вызову кадр на стеке уже не нужен: возвращаться некуда, можно просто прыгнуть в начало метода с новыми аргументами. Некоторые языки так и поступают, и рекурсия у них становится обычным циклом. JVM этого превращения не делает — кадр кладётся на стек в любом случае.

Поэтому глубокую рекурсию в Java переписывают циклом вручную, и свой стек заводят на ArrayDeque (кольцевой массив, push и pop амортизированно O(1)), а не на Stack: внутри последнего синхронизированный Vector из самых первых версий Java, и в новом коде его не берут.

Переписать циклом не всегда значит просто. Факториал и сумма списка укладываются в цикл с накопителем, а обход дерева нет: после спуска в левое поддерево надо вернуться и пойти в правое, и кто-то должен помнить, куда возвращаться. В рекурсии это делает стек вызовов, в цикле его заводят руками:

void walk(Node root) {
    Deque<Node> pending = new ArrayDeque<>();
    pending.push(root);
    while (!pending.isEmpty()) {
        Node node = pending.pop();
        if (node == null) continue;
        visit(node);
        pending.push(node.right);
        pending.push(node.left);
    }
}

Левого потомка кладут последним, чтобы он вышел первым, и порядок посещения совпадает с рекурсивным. Так же переписывают обход графа в глубину и перебор с отсечением, когда глубина может превысить стек потока.

Сортировку слиянием, которую мы только что разобрали, писать самому не нужно — в стандартной библиотеке сортировка есть. Но выбирать между вариантами приходится, и для этого полезно знать, что именно вызывается.

slices.Sort, slices.SortFunc и старые sort.Ints, sort.Slice — это не слияние, а pdqsort: быстрая сортировка с защитой от неудачных входов, которая замечает уже упорядоченные куски и на них приближается к O(N), в худшем случае даёт честные O(N·log N), сортирует по месту без буфера, но неустойчива. Слияние живёт в устойчивой ветке: slices.SortStableFunc и sort.Stable режут данные на блоки по двадцать элементов, каждый сортируют вставками, а потом сливают блоки на месте, без временного массива, за счёт лишних обменов: O(N·log N) сравнений и O(N·log² N) обменов. То есть за устойчивость в Go платят не памятью, как TimSort в других языках, а временем.

Грабля у функции сравнения одна, зато коварная: сортировка полагается на её корректность. Самый частый способ её сломать — сравнение вычитанием, func(a, b Item) int { return int(a.Value - b.Value) }: на 32-битных и беззнаковых типах вычитание переполняется, знак получается обратным, порядок перестаёт быть согласованным. Go договор не проверяет и не паникует: срез просто выходит отсортированным неправильно, и ошибка любит вылезать на большом объёме, а не на маленькой проверке. Переполнение видно и на двух числах:

живой пример

package main

import (
	"cmp"
	"fmt"
)

func main() {
	a, b := int32(2_000_000_000), int32(-2_000_000_000)
	fmt.Println("на самом деле a больше b:", a > b)
	fmt.Println("так не надо, a - b:", a-b)
	fmt.Println("так надо, cmp.Compare:", cmp.Compare(a, b))
}

Разность отрицательна, хотя a больше: вычитание вышло за диапазон int32. Поэтому в функции сравнения берут готовое cmp.Compare.

Второе, что стоит знать, — про сам стек вызовов, и здесь Go устроен иначе, чем большинство языков. Стек горутины растёт: начинается с нескольких килобайт и при нехватке переезжает в область вдвое больше вместе со всеми кадрами, а потолок по умолчанию один гигабайт на 64-битной системе (меняется через debug.SetMaxStack). Поэтому рекурсия глубиной в миллион вызовов в Go обычно проходит там, где другие языки падают на десятках тысяч. Расплата приходит на пределе: превышение потолка это не паника, которую можно поймать через recover, а фатальная ошибка goroutine stack exceeds 1000000000-byte limit, роняющая весь процесс. И каждый переезд стека копирует все кадры, так что глубокая рекурсия ещё и заметно медленнее цикла.

Спасти могла бы хвостовая рекурсия — это когда рекурсивный вызов стоит в функции последним действием и его результат сразу возвращают, ничего с ним больше не делая. Такому вызову кадр на стеке уже не нужен: возвращаться некуда, можно просто прыгнуть в начало функции с новыми аргументами. Некоторые языки так и поступают, и рекурсия у них становится обычным циклом. Компилятор Go этого превращения не делает — кадр кладётся на стек в любом случае.

Поэтому рекурсию с неизвестной глубиной, обход графа из пользовательских данных или разбор вложенного документа, в Go переписывают циклом вручную, а свой стек заводят на срезе: append кладёт, s[:len(s)-1] снимает, амортизированно O(1).

Переписать циклом не всегда значит просто. Факториал и сумма списка укладываются в цикл с накопителем, а обход дерева нет: после спуска в левое поддерево надо вернуться и пойти в правое, и кто-то должен помнить, куда возвращаться. В рекурсии это делает стек вызовов, в цикле его заводят руками:

func walk(root *Node) {
	pending := []*Node{root}
	for len(pending) > 0 {
		node := pending[len(pending)-1]
		pending = pending[:len(pending)-1]
		if node == nil {
			continue
		}
		visit(node)
		pending = append(pending, node.right, node.left)
	}
}

Левого потомка кладут последним, чтобы он вышел первым, и порядок посещения совпадает с рекурсивным. Так же переписывают обход графа в глубину и перебор с отсечением.

Сортировку слиянием, которую мы только что разобрали, писать самому не нужно — она уже есть в стандартной библиотеке. Но полезно знать, что именно вызывается.

array.sort(compareFn) и array.toSorted(compareFn) в движке V8 — это TimSort: доработанная сортировка слиянием. Она сначала ищет во входных данных куски, уже идущие по возрастанию или убыванию, и только потом сливает их попарно. На частично упорядоченных данных (а такие в жизни сплошь и рядом — дозагруженный список, чуть изменённая выборка) она приближается к O(N), в худшем случае даёт честные O(N·log N) и при этом устойчива: элементы с равными ключами сохраняют исходный взаимный порядок, и с ES2019 это требование стандарта. Платит она памятью под временный массив, но экономнее классического слияния: тому нужен буфер на весь массив, а TimSort обходится буфером до половины длины. Отдельная сортировка есть только у типизированных массивов: Int32Array.prototype.sort без функции сравнения сортирует числа как числа и делает это заметно быстрее.

Грабля у TimSort одна, зато коварная: он полагается на корректность функции сравнения, а без неё сравнивает строки. Самый частый способ получить мусор — забыть функцию для чисел: [10, 9, 2].sort() сравнивает "10", "9" и "2" как текст. Второй — вернуть из функции true или false вместо знака: сортировка никогда не услышит «меньше», и результат стандартом не определён. Переполнения при вычитании в JavaScript нет: числа дробные, целые точны до 2⁵³, так что (a, b) => a - b для чисел безопасно. Обе грабли видны на пяти числах:

живой пример

const numbers = [10, 9, 2, 33, 1];
console.log("так не надо, sort() без функции:", [...numbers].sort());
console.log("так не надо, true/false:", [...numbers].sort((a, b) => a > b));
console.log("так надо, a - b:", [...numbers].sort((a, b) => a - b));

Первая строка отсортирована как текст: 1, 10, 2, 33, 9. Вторая может остаться как была, а может и перемешаться, движок не обещает ничего. Третья честная.

Второе, что стоит знать, — про сам стек вызовов. У V8 он ограничен примерно мегабайтом (ключ --stack-size его меняет, но безопасный предел упирается в стек операционной системы), и глубокая рекурсия упирается в него ошибкой RangeError: Maximum call stack size exceeded. Точную глубину назвать нельзя — она зависит от того, сколько места занимает кадр одного вызова, — но порядок такой: у простой функции стек кончается на десяти с небольшим тысячах вложенных вызовов. То есть «рекурсия по миллиону элементов» в Node не работает даже там, где выглядит безобидно. Ошибка при этом обычная, её ловит try/catch, но полагаться на это нельзя: прилететь она может внутри чужого кода посреди работы.

Спасти могла бы хвостовая рекурсия — это когда рекурсивный вызов стоит в функции последним действием и его результат сразу возвращают, ничего с ним больше не делая. Такому вызову кадр на стеке уже не нужен: возвращаться некуда, можно просто прыгнуть в начало функции с новыми аргументами. Стандарт ES2015 даже требует этого превращения, но V8 его так и не реализовал, и в Node оно не работает.

Поэтому глубокую рекурсию переписывают циклом вручную, а свой стек заводят на обычном массиве: push кладёт, pop снимает, амортизированно O(1).

Переписать циклом не всегда значит просто. Факториал и сумма списка укладываются в цикл с накопителем, а обход дерева нет: после спуска в левое поддерево надо вернуться и пойти в правое, и кто-то должен помнить, куда возвращаться. В рекурсии это делает стек вызовов, в цикле его заводят руками:

function walk(root) {
  const pending = [root];
  while (pending.length > 0) {
    const node = pending.pop();
    if (node === null) continue;
    visit(node);
    pending.push(node.right, node.left);
  }
}

Левого потомка кладут последним, чтобы он вышел первым, и порядок посещения совпадает с рекурсивным. Так же переписывают обход графа в глубину и перебор с отсечением, когда глубина может превысить стек.

Сортировку слиянием, которую мы только что разобрали, писать самому не нужно — она уже есть в стандартной библиотеке. Но полезно знать, что именно вызывается.

sorted(iterable) и list.sort() — это TimSort, и придуман он был именно для Python: доработанная сортировка слиянием. Она сначала ищет во входных данных куски, уже идущие по возрастанию или убыванию, и только потом сливает их попарно. На частично упорядоченных данных (а такие в жизни сплошь и рядом — дозагруженный список, чуть изменённая выборка) она приближается к O(N), в худшем случае даёт честные O(N·log N) и при этом устойчива, и это гарантия языка. Платит она памятью под временный массив, но экономнее классического слияния: тому нужен буфер на весь массив, а TimSort обходится буфером до половины длины. Других сортировок в стандартной библиотеке нет: и для чисел, и для объектов вызывается одна и та же, разница только в цене сравнения.

Грабля у TimSort одна, зато коварная: он полагается на корректность сравнения. Переполнения при вычитании в Python нет, целые растут сколько нужно, зато сравнение падает на разнотипных элементах: 3 < "10" это TypeError, и вылезает он не при вызове sort, а посреди слияния, когда данных достаточно много, чтобы эти два элемента встретились. То же с None в ключе: None < 5 невозможно. Поэтому ключ делают одного типа для всех элементов и обрабатывают пустые значения явно, например key=lambda o: (o.price is None, o.price or 0).

Второе, что стоит знать, — про сам стек вызовов, и в Python он самый короткий из четырёх языков. Интерпретатор считает глубину сам и по умолчанию обрывает её на тысяче вложенных вызовов ошибкой RecursionError, задолго до того, как кончится настоящий стек. Предел меняется через sys.setrecursionlimit, но до версии 3.12 слишком большой предел ронял интерпретатор целиком, когда кончался стек операционной системы; с 3.12 вызовы функций Python не тратят стек C, и поднимать предел стало безопаснее. Всё равно «рекурсия по миллиону элементов» в Python не работает даже там, где выглядит безобидно. Предел виден сразу:

живой пример

import sys


def dive(n: int) -> int:
    return dive(n + 1)


try:
    dive(0)
except RecursionError as e:
    print("предел по умолчанию:", sys.getrecursionlimit(), "вызовов ->", e)

Спасти могла бы хвостовая рекурсия — это когда рекурсивный вызов стоит в функции последним действием и его результат сразу возвращают, ничего с ним больше не делая. Такому вызову кадр на стеке уже не нужен: возвращаться некуда, можно просто прыгнуть в начало функции с новыми аргументами. Некоторые языки так и поступают. Python этого превращения не делает намеренно: авторы языка ценят честную трассировку стека выше.

Поэтому глубокую рекурсию в Python переписывают циклом вручную, а свой стек заводят на обычном list: append кладёт, pop() снимает, амортизированно O(1).

Переписать циклом не всегда значит просто. Факториал и сумма списка укладываются в цикл с накопителем, а обход дерева нет: после спуска в левое поддерево надо вернуться и пойти в правое, и кто-то должен помнить, куда возвращаться. В рекурсии это делает стек вызовов, в цикле его заводят руками:

def walk(root):
    pending = [root]
    while pending:
        node = pending.pop()
        if node is None:
            continue
        visit(node)
        pending.append(node.right)
        pending.append(node.left)

Левого потомка кладут последним, чтобы он вышел первым, и порядок посещения совпадает с рекурсивным. Так же переписывают обход графа в глубину и перебор с отсечением, когда глубина может превысить предел.

• Библиотечная сортировка объектов это TimSort, устойчивый и близкий к O(N) на почти упорядоченных данных; компаратор через вычитание ломает её с IllegalArgumentException; стек потока около мегабайта (-Xss), свой стек заводят на ArrayDeque.

• slices.Sort это pdqsort, неустойчивый и без буфера; устойчивость даёт slices.SortStableFunc ценой лишних обменов; стек горутины растёт до гигабайта, а его исчерпание это фатальная ошибка, не паника; свой стек заводят на срезе.

• sort это TimSort, устойчивый по стандарту, но без функции сравнения сортирует как строки; стек V8 около мегабайта, RangeError на десятке тысяч вызовов, хвостовые вызовы не оптимизируются; свой стек заводят на массиве.

• sorted это TimSort, устойчивый по гарантии языка, разнотипные элементы дают TypeError; предел рекурсии тысяча вызовов (RecursionError, sys.setrecursionlimit), хвостовых вызовов нет намеренно; свой стек заводят на list.