Для обработки рекурсивных структур данных используются рекурсивные функции.
Недостаток -- память для стека вызовов, время на передачу аргументов.
--
```c++
int iterSum(int n) // Сумма чисел через цикл
{ int sum = 0;
for (int i = 1; i <= n; i++)
sum += i;
return sum;
}
```
```c++
int recSum(int n) // Сумма чисел через рекурсию, неэффективный способ
{ if (n == 0)
return 0;
return n + recSum(n - 1);
}
```
--
*Хвостовая рекурсия* — это частный случай рекурсии, при котором рекурсивный вызов единственен
и является последней инструкцией функции. При этом функция, вызвавшая "саму себя", должна возвратить
результат рекурсивного вызова, не выполняя с ним никаких преобразований. Компилятор часто сам выполняет оптимизацию хвостовой рекурсии.
```c++
int tailRecSum(int n, int sum) // Сумма чисел через рекурсию, эффективный способ
{ if (n == 0) return sum;
return tailRecSum (n - 1, sum + n);
}
```
компилируется в
```c++
int tailRecSum(int n, int sum)
{ loop: if (n == 0) return sum;
sum = sum + n;
n = n - 1;
goto loop;
}
```
Начало
Учебные материалы
Структуры данных