В чем польза рекурсии?

#cpp #алгоритм #рекурсия

Читал что "рекурсия обычно замедляет работу программы и расходует лишнюю память".
Это во всех случаях? И какая еще от нее есть польза кроме как компактной записи кода?
И в каких случаях она необходима?
    

Ответы

Ответ 1

Бытует мнение, что рекурсия является очень выразительным|естественным|няшечка|etc
средством для реализации некоторых действий.
Рекурсия общего вида:

Замедляет, т.к. много ( в т.ч. бесконечно ) вызовов функций.
Расходует память, т.к. каждый вызов функции хранит данные в стеке

Есть ещё, т.н., хвостовая рекурсия. ( ИМХО - не рекурсия вовсе, а просто сахар для
цикла ):
Суть в том, что результат вызова итерации хвостовой рекурсии - не обрабатывается
предыдущим шагом, и копилятор/интерпритатор может заменить работу с такой функцией
- на цикл, который лишён недостатков указанных выше.
1) Пример хвостовой рекурсии ( JS, факториал ):
function fact( step, res ){
    if ( step < 2 ) return res;
    else return fact( step - 1, res * step );
}

fact_10 = fact( 10, 1 );

2) Тот-же смысл, но обычная рекурсия:
function fact( step ){
    if ( step < 2 ) return 1;
    else return step * fact( step - 1 );
}

fact_10 = fact( 10 );

Разница, как уже указывал:

Результат вызова никак не используется ( просто проброс на уровень выше )
Результат вызова перед возвращением подвергается некой операции.

Вариант 1 легко ( алгоритм простой ) оптимизируется до такого кода:
function fact( num ){
  var res = 1;

  while( num > 1 ){
    res *= num;
    num--;
  }

  return res;
}

Либо совсем кратко ( но в asm - тоже самое ):
function fact( num ){
  var res = 1;

  while( num > 1 ) res *= num--;

  return res;
}


Ответ 2

Некоторые задачи (например обход дерева, перебор вариантов и т.д.) достаточно просто
(я бы даже сказал, элегантно) решаются с помощью рекурсии. Те же задачи могут решаться
с помощью цикла, но с бОльшими усилиями со стороны программиста и примерно с такими
же затратами памяти на запоминание предыдущих состояний.
Если компилятор языка программирования не поддерживает оптимизацию хвостовых рекурсий,
то хвостовую рекурсию лучше преобразовать в цикл вручную.