Analyzing time taken by recursion

Question

I am learning c++. I am currently practicing recursion.

std::vector<int> printNos(int x) {
        static std::vector<int> v;
        if(x!=0)
        {
            v.push_back(x);
            return printNos(x-1);
        }
        else
        return v;
        
        return v;
}

Why is the above code slower than the code given below ?

void recursivefunction(int x,std::vector<int>& v)
{
    if(x==0)
    return;

     v.push_back(x);
     recursivefunction(x-1,v);

}


std::vector<int> printNos(int x) {
        std::vector<int> ans;
        recursivefunction(x,ans);
        return ans;
}

in addition to the question above, I had another doubt about making my vector static , is it a bad practice?

Which C++ textbook offers the first shown code as an example? Your "doubt" has very valid justification. — Sam Varshavchik, Jul 11 '23 at 13:02
Above code is the one i wrote by myself but i wasn't able to clear the question as time limit exceeded. The second one was given as the solution to the problem. — Ervin Ranjan, Jul 11 '23 at 13:05
Which compiler flag do you use? recursive method return many `std::vector`... — Jarod42, Jul 11 '23 at 13:05
I don't know about that as i was practicing this problem on a site. — Ervin Ranjan, Jul 11 '23 at 13:08
Any mention of "time limit exceeded" typically suggests that someone was misled by one of many similar scam sites into believing that one can become a C++ expert by doing a series of random coding puzzles, one after another. This is not true. Noone can effectively learn C++ by doing random coding puzzles, but only by following an organized, guided curriculum [from a good C++ textbook](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list). All that someone will learn by doing coding puzzles is how to do those coding puzzles. — Sam Varshavchik, Jul 11 '23 at 13:08
Aside: why is your function called `print` if it doesn't print anything? Choice of names is important! — Paul Sanders, Jul 11 '23 at 13:12
It might be worth mentioning that a natural fit for recursion is to walk some kind of tree. You recurse to move from one node to the next, until you find the node you want (or reach a leaf node). — Paul Sanders, Jul 11 '23 at 13:21
This is a pity that textbooks and online examples typically don't mention the following. But with experience, I setup a rule for when recursion can be used: *the maximum recursion depth for a recursive function shall be **O(log n)***. Having a **O(n)** depth like your snippet is asking for trouble: it will quickly crash with (not so) big `n`. And this type of recursive function can be very easily converted to a loop, that is easier to understand, easier to debug, safer and faster. — prapin, Jul 11 '23 at 17:54

bolov · Accepted Answer · 2023-07-11T14:02:55.897

I had another doubt about making my vector static , is it a bad practice?

Yes. But so is using recursion (in general in non-functional languages and in particular for this problem). So the point of this exercise is not about teaching you good practices, but to teach you various patterns of recursion. I guess it first teaches you the patterns and I hope it then tells you why and when you should and should not use them. If it does not explain the tradeoffs consider a better learning source (take a look at The Definitive C++ Book Guide and List)

Why is the above code slower than the code given below ?

The first version is objectively worst than the second because each call creates a new vector (the one you return). This will result in many unnecessary allocations.

The second version uses just 1 vector that you pass a reference to so it's more efficient than the 1st. Still it is worst than an iterative solution (non-recursive function with for loop).

A recursion solution for some problems can be easier and simpler to write. However considering performance a recursive solution in C or C++ will almost always be worst than the equivalent efficient non-recursive method. This is because each function call incurs a small performance penalty. The call stack is increased and decreased with each call. Besides the performance burden there is also the very real possibility of quickly exhausting the call stack causing a program crash.

When you find a problem that is more elegantly solved with recursion and you care about performance, every recursive algorithm can be easily transformed into a non-recursive function by using a queue to save the context that would have been saved with each recursive call.

perhaps worth mentioning that the slowness is not due to recursion. It is possible to write a recursive function that does not make such uncessary copies. Though, that doesn change the fact that recursion is the wrong tool here. — 463035818_is_not_an_ai, Jul 11 '23 at 13:17
`recursive solution in C or C++ will always be worst than the equivalent efficient non-recursive method` - this is bold statement. For example note there is tail recursion optimization. — Marek R, Jul 11 '23 at 13:46
In general, if there is a non-recursive way of doing things it is usually better. There may be cases where recursion is better or the only reasonable algorithm, but I avoid recursion whenever possible, as too much can go wrong. It is really worth learning to do, and it is kind of neat (as in cool, NOT as in tidy). I like the definition: a recursive program is one that calls itself recursively! — JosephDoggie, Jul 11 '23 at 14:48

Analyzing time taken by recursion

1 Answers1