В чем разница между рекурсивной версией & quot; найти & quot; а не рекурсивный?
В книге Ускоренное программирование на C ++, на странице 205, есть две следующие реализации find
template <class In, class X> In find(In begin, In end, const X& x)
Я заинтересован в том, чтобы узнать, в чем разница между показателями производительности (на самом ли деле после компиляции?) Следующих двух реализаций.
нерекурсивна
template <class In, class X> In find(In begin, In end, const X& x)
{
while (begin != end && *begin != x)
++begin;
return begin;
}
рекурсивный
template <class In, class X> In find(In begin, In end, const X& x)
{
if (begin == end || *begin == x)
return begin;
begin++;
return find(begin, end, x);
}
Используя Compiler Explorer, предложенный Kerrek, я получил следующее
нерекурсивна https://godbolt.org/g/waKUF2
рекурсивный https://godbolt.org/g/VKNnYZ
Вроде бы точно так же после компиляции? (Если я правильно использую инструмент .. Извините, я очень плохо знаком с C ++)
Решение
Рекурсивные функции добавят дополнительные элементы в стек. Это может вызвать ошибки переполнения стека в зависимости от состояния стека перед запуском рекурсии и количества повторов, которые вы выполняете.
Каждый вызов функции помещает данные в стек, который включает адрес возврата. Это продолжается до тех пор, пока данные не будут найдены. В это время все функции начнут возвращать значение, которое вернула последняя функция, пока мы, наконец, не вернемся к функции, вызвавшей оригинал. find,
Точный объем данных, хранимых для каждого вызова функции, зависит от соглашения о вызовах и архитектуры. Кроме того, из-за загрузки данных в стек возникают издержки, которые могут замедлить работу алгоритма, но это зависит от алгоритма.
Это строго для рекурсии, которая не оптимизирована с помощью хвостового вызова.
Другие решения
По большей части рекурсия медленнее и занимает больше стека. Основным преимуществом рекурсии является то, что для таких задач, как обход дерева, алгоритм становится немного проще или более «элегантным».
Проверьте некоторые из сравнений:
Рекурсия против итерации