I've been trying to attempt a question on recursion pattern and it is pretty easy one but I am not able to getting why I am getting such an unexpected output. I traced the variables and parameters in callstack and my logic seems to be right but still it is printing random numbers.

#include <bits/stdc  .h>
using namespace std;

vector<int> pattern(int);
int main()
{
    int n;
    cin >> n;
    vector <int> ans = pattern(n);

    for (int u: ans)
    {
        cout << u << " ";
        
    }
    cout << "\n";
}
vector<int> sol;
vector<int> pattern(int N)
{
    if (N <= 0)
    {
        // cout << "stopped" << endl;
        sol.push_back(N);
        return sol;
    }

    sol.push_back(N);
    pattern(N-5);
    sol.push_back(N);
    
}

i/p: 10 
expected o/p: 10 5 0 5 10 


but it is giving this result:

6422500 1997786416 -1172770555 0 6422508 1997703885 -1 1997899634 0 0 4199136 2576384 0 32 0 0 0 10672 726272 791648 826264 57158026 0 35651584 0 590440 36175880 524296 590376 36175880 524298 524832 35651584 9 655944 34603080 4718603 721424 34604104 4718597 328208 34604104 71303179 262672 34603080 4718599 262672 34604096 71827463 197252 58785856 -2143289343 66305 34635840 71958539 66434 50495552 -2143289343 524840 38273024 524295 721424 34603016 524293 721424 51512330 -2080374783 560 34866184 3 66322 34635784 655371 721424 50397184 -2147287039 66305  ..... [Truncated]```

CodePudding user response：

You are missing a return statement from pattern() function.

vector<int> pattern(int N)
{
    if (N <= 0)
    {
        // cout << "stopped" << endl;
        sol.push_back(N);
        return sol;
    }

    sol.push_back(N);
    pattern(N-5);
    sol.push_back(N);
    
    return sol;           // <--------- this was missing
}

Let N = 10, so pattern(10) will be called, then:

1. sol = {10}
2. pattern(5)

• sol = {10, 5}
• pattern(0) -> sol = {10, 5, 0} -> return sol -> but you don't store return value of pattern anywhere, so the return value is lost
• sol = {10, 5, 0, 5}
• function returns garbage, but that's also not captured anywhere

3. sol = {10, 5, 0, 5, 10}
4. function returns garbage which is captured by ans.

Actually, your function isn't required to return a vector at all, since your vector is declared as global. You could have void return type and it would work without any return statement. The below code works fine:

#include <iostream>
#include <vector>
using namespace std;

vector<int> sol;
void pattern(int);

int main()
{
    int n;
    cin >> n;
    pattern(n);

    for (auto& u: sol)
    {
        cout << u << " ";
        
    }
    cout << "\n";
}

void pattern(int N)
{
    if (N <= 0)
    {
        // cout << "stopped" << endl;
        sol.push_back(N);
        return;
    }

    sol.push_back(N);
    pattern(N-5);
    sol.push_back(N);
}

Also a side note, it's recommended by many people to not to use:

#include <bits/stdc  .h>

Instead use individual includes:

#include <iostream>
#include <vector>