Предпочтительна ли в этой ситуации рекурсия?

Question

Предположим, у нас есть строка символов, и мы хотим напечатать ее в обратном порядке. В этом случае рекурсия кажется более быстрым выбором, потому что строка «проходит» один раз, в то время как обычный подход l oop делает это дважды.

Есть ли причина не предпочесть рекурсию для такого рода проблем ? Представляет ли рекурсия какой-либо недостаток в случае большого ввода?

Рассмотрим следующий код:

#include <stdio.h>
#include <string.h>

void printReverse_1(const char *str)
{
    if (!*str)
        return;

    printReverse_1(str + 1);
    putchar(*str);
}

void printReverse_2(const char *str)
{
    const char *tmp = str + strlen(str) - 1;

    while (tmp > str)
    {
        putchar(*tmp--);
    }
    putchar(*tmp);
}

int main(void)
{
    printReverse_1("abc");
    putchar('\n');

    printReverse_2("abc");
    putchar('\n');

    return 0;
}

Answer 1

Есть ли причина не отдавать предпочтение рекурсии в подобных задачах? Создает ли рекурсия какой-то недостаток в случае большого ввода?

Рекурсия создает новый стековый фрейм для каждого вызова функции. Для больших входных данных может не хватить места в стеке. По возможности предпочитайте итерацию рекурсии.

Answer 2

В этом случае рекурсия кажется более быстрым выбором, потому что строка «проходит» один раз, в то время как обычный подход l oop делает это дважды.

Когда дело доходит до производительность, никогда ничего не предполагайте. Протестируйте оба подхода и измерьте. Но, как показывает опыт, с циклами это быстрее, чем с рекурсией, поскольку рекурсия означает вызовы функций и настройку фреймов стека. Представляет ли рекурсия какой-либо недостаток в случае большого ввода?

В общем, преимущество рекурсии состоит в том, что их легко писать и легко читать. Они очень редко предпочтительнее по соображениям производительности. И их самый большой недостаток в том, что они имеют тенденцию безумно съедать стек.

В этой конкретной ситуации маловероятно, что производительность действительно является проблемой. Но если это так, то также вероятно, что вызов putchar является самой большой проблемой, потому что вы вызываете его один раз для каждого символа. В этом конкретном примере вам действительно не хватало слона в комнате. Вызов функций может быть дорогостоящим.

Чтобы сделать это как можно быстрее, я бы попробовал следующее:

void printReverse_3(const char *str)
{
        const size_t len = strlen(str);
        // alloca may blow the stack. Use malloc if you want to use this on                                                                                                                                                                   
        // huge strings                                                                                                                                                                                                                       
        char *tmp = alloca(len + 1);

        tmp[len]='\0';
        str = &str[len];

        for(size_t i=0; i<len; i++) {
                str--;
                tmp[i] = *str;
        }

        printf("%s", tmp);
}

Я не пробовал это, но подозреваю, что это быстрее. Вы можете изменить printf на puts, поскольку эта функция работает быстрее, но puts добавляет новую строку позже, поэтому она не будет эквивалентна вашим функциям.

Answer 3

Это ответ на @klutt; размещение этого сообщения в качестве ответа вместо комментария, чтобы код был читабельным.

Использование memchr вместо strlen для строки из 10 000 000 символов занимает 1,5–1,8 мксек по сравнению с 3,2–3,4 мкс, или примерно в половине случаев.

#include <iostream>
#include <chrono>
#include <vector>

size_t len(const char* p)
{
  //return strlen(p);
  char* end = (char*)memchr(p, '\0', -1);
  return end - p;
}

int main()
{
  const int block = 10'000'000;
  std::vector<char> v(block, 'x');
  v[block - 1] = 0;
  auto t1 = std::chrono::high_resolution_clock::now();
  size_t l = len(&v[0]);
  auto t2 = std::chrono::high_resolution_clock::now();
  std::cout << "len() took "
    << std::chrono::duration_cast<std::chrono::microseconds>(t2 - t1).count()
    << " microseconds\n";
  return l;
}