-2

I expected the code below to print the sequence 0 1 2 3.

Instead I got a recursion call runtime error (causing a stack overflow).

Can you explain why ?

#include <bits/stdc++.h>

using namespace std;

#define ll long long
void print(int n)
{
    if (n < 0)
        return;
    if (n == 0)
    {
        cout << n << " ";
        return;
    }
    print(n--);
    cout << n << " ";
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int num = 3;
    print(num);
    return 0;
}
wohlstad
  • 12,661
  • 10
  • 26
  • 39
Durgesh Saini
  • 1
  • What is the actual error? – Scott Hunter Apr 20 '22 at 13:45
  • 11
    Every time a compiler encounters `#define ll long long`, a fairy dies. In fact the first three non-blank lines reduce a grown man to tears. – Bathsheba Apr 20 '22 at 13:45
  • 6
    And every time I see `#include ` I kill a fairy myself. See https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h – ChrisMM Apr 20 '22 at 13:47
  • 7
    Please do not learn how to code from "competition websites". They teach absolute _trash_ programming. – Mike Vine Apr 20 '22 at 13:47
  • 8
    With `print(n--);` you are always calling the `print` function with the ***same value***. After the call returns, the local `n` will be 1 less, but that value is lost. Look up the difference between post-increment and pre-increment operators. – Adrian Mole Apr 20 '22 at 13:47
  • 1
    What do you think the value of `n--` is? – Scott Hunter Apr 20 '22 at 13:47
  • 1
    and every time I see [`using namespace std;` many fairies die](https://stackoverflow.com/q/1452721/995714) – phuclv Apr 20 '22 at 13:48
  • 1
    the problem would be known right away with a debugger. You must learn how to debug. See [What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/q/25385173/995714), [How to debug small programs](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/) – phuclv Apr 20 '22 at 13:50
  • You should learn to use a debugger. Setting a breakpoint at the beginning of `print` would show you that `n` never changes and that your recursion would never and leading to exceeding of the stack. – t.niese Apr 20 '22 at 13:50
  • 1
    *according to me it should run fine and my output is 0 1 2 3* -- That's not how computer programming works. The computer does exactly what you tell it -- it has no idea what your desired output is -- all it does is follow the instructions given. If the instructions given are faulty, then it's time for you to learn how to debug your code to see where *your* fault is. – PaulMcKenzie Apr 20 '22 at 13:53
  • 1
    I recommend you get out of the habit of using [`using namespace std;`](https://stackoverflow.com/q/1452721/10077) and [`#include `](https://stackoverflow.com/q/31816095/10077). They're bad individually, but especially insidious together. – Fred Larson Apr 20 '22 at 13:55
  • 2
    Don't write `n--` or `--n` when you mean `n-1`. Don't write `n++` or `++n` when you mean `n+1`. (Mutation is bad, mmkay?) You don't even save a keystroke by doing it. – molbdnilo Apr 20 '22 at 13:57
  • 5
    `#define ll long long` -- There is no need for stuff like this, when C++ already has `int64_t`. The `int64_t`, not only describes that it is an integer, it also tells you the number of bits (64). Using crazy macros like `ll` that look like the number `11` is unnecessary. – PaulMcKenzie Apr 20 '22 at 13:59
  • @PaulMcKenzie: `std::int64_t` even tells you something about the complementing scheme, although so does `long long` too from C++20. Although note well the common misconception that large values wrap around - the behavior of signed integral type overflow is still undefined. – Bathsheba Apr 20 '22 at 14:04
  • @AdrianMole: if you have found a duplicate, by all means VTC. – Fred Larson Apr 20 '22 at 14:04

1 Answers1

2

Look at this:

print(n--);

Here, the recursive call is made with the same value of n as it was called with. The decrement isn't performed until after the recursive call returns. The recursion is therefore theoretically infinite.

Rather, I don't believe you need to increment or decrement n at all. Just use n-1:

print(n-1);
Fred Larson
  • 60,987
  • 18
  • 112
  • 174