CODEWITHSUNDEEP
cperformancerecursion
machine_1
machine_1

Reputation: 4454

Is recursion preferred in this situation?

Suppose we have a string of characters and we want to print it in reverse order. Recursion seems to be the faster choice in this case because the string is "walked" once, while the usual loop approach does it twice.

Is there any reason not to prefer recursion for these kind of problems? Does recursion pose some sort of disadvantage in case of big input?

Consider the following code:

#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;
}

Upvotes: 1

Views: 138

Answers (3)

Vlad Feinstein
Vlad Feinstein

Reputation: 11311

This is in response to @klutt; posting this as an answer instead of the comment to make the code readable.

Using memchr instead of strlen for a 10,000,000 character string takes 1.5us-1.8us compared to 3.2us-3.4us, or about half the time.

#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;
}

Upvotes: 0

klutt
klutt

Reputation: 31296

Recursion seems to be the faster choice in this case because the string is "walked" once, while the usual loop approach does it twice.

When it comes to performance, never assume anything. Test both approaches and measure. But as a rule of thumb, it's quicker with loops than recursion, since recursion means function calls and setting up stack frames.

Is there any reason not to prefer recursion in these kind of problems? Does recursion pose some sort of disadvantage in case of big input?

In general, the benefit of recursion is that they are easy to write and easy to read. They are very rarely preferable for performance reasons. And their biggest drawback is that they tend to eat up the stack like crazy.

In this particular situation, it's unlikely that performance actually is an issue. But if it is, it's also likely that the call to putchar is the biggest problem because you call it once for every character. So in this particular example, you really missed the elephant in the room. Function calls can be expensive.

In order to do this as fast as possible, I'd try this:

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);
}

I have not tried this out, but I do suspect that it is quicker. You could change printf for puts since that function is quicker, but puts adds a newline afterwards, so it would not have been equivalent to your functions.

Upvotes: 4

Maxim Egorushkin
Maxim Egorushkin

Reputation: 136208

Is there any reason not to prefer recursion in these kind of problems? Does recursion pose some sort of disadvantage in case of big input?

Recursion creates a new stack frame for each function invocation. For large inputs it may run out of stack space. Prefer iteration to recursion, when possible.

Upvotes: 5

Related Questions