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

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

Ответ

Бытует мнение, что рекурсия является очень выразительным|естественным|няшечка|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; }