Структуры данных

Рекурсивно-определенная (рекурсивная) структура данных включает в себя одну или более компонент, относящихся к тому же типу, что и сама структура.

Примеры – арифметическое выражение, DOM, список в функциональных языках программирования.

Элементы такой структуры чаще всего относятся к двум типам – лист и узел, который содержит один или более указателей на другие узлы.

Односвязный список: List = Nil | Node(Int head, List tail)

Арифметическое выражение: ArTree = Leaf(Int n) | Node(Char op, ArTree left, ArTree right)

Для обработки рекурсивных структур данных используются рекурсивные функции.

Недостаток – память для стека вызовов, время на передачу аргументов.

    int iterSum(int n) // Сумма чисел через цикл
    {   int sum = 0;
        for (int i = 1; i <= n; i++)
            sum += i;
        return sum;
    }

    int recSum(int n) // Сумма чисел через рекурсию, неэффективный способ
    {   if (n == 0)
            return 0;
        return n + recSum(n - 1);
    }

Хвостовая рекурсия — это частный случай рекурсии, при котором рекурсивный вызов единственен и является последней инструкцией функции. При этом функция, вызвавшая "саму себя", должна возвратить результат рекурсивного вызова, не выполняя с ним никаких преобразований. Компилятор часто сам выполняет оптимизацию хвостовой рекурсии.

    int tailRecSum(int n, int sum) // Сумма чисел через рекурсию, эффективный способ
    {  if (n == 0)  return sum;
       return tailRecSum (n - 1, sum + n);
    }

компилируется в

    int tailRecSum(int n, int sum)
    { loop: if (n == 0) return sum;
        sum = sum + n;
        n = n - 1;
        goto loop;
    }