Является ли рекурсия быстрее, чем зацикливание?

Question

Я знаю, что рекурсия иногда намного чище, чем зацикливание, и я ничего не спрашиваю о том, когда мне следует использовать рекурсию поверх итерации, я знаю, что уже есть много вопросов об этом.

Что яя спрашиваю, является ли рекурсия когда-либо быстрее, чем цикл?Мне кажется, вы всегда сможете уточнить цикл и заставить его работать быстрее, чем рекурсивная функция, потому что цикл отсутствует, постоянно настраивая новые кадры стека.

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

Answer 1

Согласно теории это то же самое. Рекурсия и цикл с одинаковой сложностью O () будут работать с той же теоретической скоростью, но, конечно, реальная скорость зависит от языка, компилятора и процессора. Пример со степенью числа может быть итеративно закодирован с помощью O (ln (n)):

  int power(int t, int k) {
  int res = 1;
  while (k) {
    if (k & 1) res *= t;
    t *= t;
    k >>= 1;
  }
  return res;
  }

Answer 2

Это предположение. Обычно рекурсия, вероятно, не справляется с цикличностью часто или когда-либо при проблемах приличного размера, если оба используют действительно хорошие алгоритмы (не считая сложности реализации), она может отличаться, если используется с языком w / рекурсия хвостового вызова (и хвостовой рекурсивный алгоритм и с циклами также как часть языка) - который, вероятно, будет очень похож и, возможно, даже предпочтет рекурсию иногда.