Changing function argument to global variable causes unexpected results

Question

I'm solving a backtracking problem. I have to construct a permutation of length n in such a way that the sum of each adjacent elements are prime. The permutation is circular, the last element is adjacent to first element. Note that all valid permutations should start with 1.

void recurse(int i, int prev, int n, vector<int> prime_ring) {
  if (i == n) {
    prime_ring.insert(prime_ring.begin(), 1);
    
    if (!is_prime[prime_ring.back() + 1])
      return;
      for (auto data : prime_ring)
        cout << data << " ";
      cout << "\n";
    
    prime_ring.clear();
    return;
  }
  for (int next = 2; next <= n; next++) {
    if (!seen[next] && is_prime[prev + next]) {
       prime_ring.push_back(next);
       seen[next] = true;
       recurse(i + 1, next, n, prime_ring);
       seen[next] = false;
       prime_ring.pop_back();
      
    }

  }
}

The above code generates the wanted permutations correctly. For example for n = 4. Permutations should be

1 2 3 4 
1 4 3 2 



void recurse(int i, int prev, int n) {
  if (i == n) {
    prime_ring.insert(prime_ring.begin(), 1);
    
    if (!is_prime[prime_ring.back() + 1])
      return;
      for (auto data : prime_ring)
        cout << data << " ";
      cout << "\n";
    
    prime_ring.clear();
    return;
  }
  for (int next = 2; next <= n; next++) {
    if (!seen[next] && is_prime[prev + next]) {
       prime_ring.push_back(next);
       seen[next] = true;
       recurse(i + 1, next, n);
       seen[next] = false;
       prime_ring.pop_back();
      
    }

  }
}

Changing prime_ring to a global vector, results in runtime error. This problem happened to me many times, I failed to realise what's wrong. I'm not aware of the difference between global vector vs function argument vector.

Every time you call `recurse` a new copy of `prime_ring` is created (pass by value). With a global `prime_ring` there is only one. So the algorithms are different. — Richard Critten, Mar 07 '21 at 18:47
"Changing prime_ring to a global vector, results in runtime error." Then don't do that. You already have a working solution. — Code-Apprentice, Mar 07 '21 at 18:50
`prime_ring.clear();` Why do you clear the state when you found a solution? — ph3rin, Mar 07 '21 at 18:51
@Code-Apprentice Actually my first approach was the global one. That's why I asked the question. — Migo, Mar 07 '21 at 18:52

score 0 · Answer 1 · answered Mar 07 '21 at 18:52

I'm not aware of the difference between global vector vs function argument vector.

The difference is that when you pass a vector as a parameter, the vector is copied. On the other hand when you use a global variable, there is only one `vector.

The solution here is to not use a global variable since you have a working function.

score 0 · Answer 2 · answered Mar 07 '21 at 18:58

Suppose you are on the line

recurse(i + 1, next, n);

where i == n - 1

Suppose when you go into the recurse function, is_prime[prime_ring.back() + 1] is true.

Then you call prime_ring.clear();, and returns.

Afterwards, you call prime_ring.pop_back();

What happens if you try to pop_back() from an empty vector? Well, bad things can happen (namely, Undefined Behaviour)

Changing function argument to global variable causes unexpected results

2 Answers2