Pass Array to Recursive Function While Modifying It C++

Question

I have a recursive function that takes a 2D array as a parameter in C++. The contents of this 2D array are to be unique among all recursive calls of this function.

I would like to modify this array each time before I make the recursive call. How can I do this without modifying the array for both of the 2 recursive calls, just for the current call?

Here is what I am trying to accomplish:

void foo(int a[10][10]) {
  // imagine base case above
  // modify array, i.e. set a[2][2] to '5'
  foo(a);
  // modify array i.e. set a[2][2] to '3'
  foo(a);
}

I tried the following, which resulted in a compiler error:

void foo(int a[10][10]) {
  // imagine base case above
  foo(a[2][2] = 5);
  foo(a[2][2] = 3);
}

The idea is that I want the array to be independent among recursive calls, for example, I don't want the set a[2][2] = 5 to apply to the next recursive call. I want that array modification to be "reverted", in a sense, before I apply the next modification (change).

This is easy to accomplish if I were just passing an int as an argument. For example, I could do:

void foo(int a) {
  // imagine base case above
  // increase a by 1
  foo(a + 1);
  // decrease a by 4
  foo(a - 4);
}

You can see here how easy it is to make the modifications without affecting the following recursive call.

My question here is how I can make changes along the same lines with an array.

So what you really want is to pass the array by value, so each recursive call have its own private copy that it can modify as it pleases, and when the recursive call returns the original array is unmodified? Then I suggest you look into std::array (or std::vector) instead, as those will be much easier to pass by value. — Some programmer dude
– Some programmer dude, Commented May 24, 2020 at 14:17
As for the modification bit, perhaps add an argument which is a function to call to do the modification you want (which you could pass as a lambda). — Some programmer dude
– Some programmer dude, Commented May 24, 2020 at 14:19
Could you please provide an example using std::array or std::vector? Thanks! — coder_jam
– coder_jam, Commented May 24, 2020 at 14:19
I'm not sure if this is what you're asking, but it seems you could do void foo(int a[10][10]) { a[2][2] = 5; foo(a); a[2][2] = 3; foo(a); } — cigien
– cigien, Commented May 24, 2020 at 14:24
@coder_jam: Your example is indeed not the best, as you change the same element, so cigien's proposal (with potential final restoration const auto old = a[2][2], /*..*/; a[2][2] = old;) does the job. — Jarod42
– Jarod42, Commented May 24, 2020 at 14:49

Jarod42 · Accepted Answer · 2020-05-24 14:46:34Z

2

C-array cannot be copied, std::array can :) So I would use std::array.

a[2][2] = 5 mutates array, whereas i - 4 doesn't mutate integer i (so nothing to discard in that case, contrary to f(i -= 4)).

there are no operator on array which allows easy customization, we can create function or lambda for that:

// pass by value
std::array<std::array<int, 10>, 10>
mutated(std::array<std::array<int, 10>, 10> a, int x, int y, int value)
{
    a[x][y] = value;
    return a;
}

void foo(const std::array<std::array<int, 10>, 10>& a) {
  // imagine base case above
  // "modify" array, i.e. set a[2][2] to '5'
  foo(mutated(a, 2, 2, 5));
  // "modify" array i.e. set a[2][2] to '3'
  foo(mutated(a, 2, 2, 3));
}

edited May 24, 2020 at 14:46

answered May 24, 2020 at 14:36

Jarod42

227k15 gold badges214 silver badges350 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

kschnell · Accepted Answer · 2020-05-24 14:34:35Z

When you call foo(a + 1) in your last example, you are not passing the original integer, but a copy of it, to the function. To achieve something similar with arrays, you would have to create a copy of the entire array, and then modify the copy before passing it to the function.

Example

void foo(int a[10][10]) {
  // Create two copies of a
  // We cannot simply do 'int b[10][10] = a;', because that would make 
  // b point to the same memory region as a.
  int b[10][10] = {0};
  int c[10][10] = {0};
  for (int i = 0; i < 10; ++i) {
    for (int j = 0; j < 10; ++j) {
      b[i][j] = a[i][j];
      c[i][j] = a[i][j];
    }
  }

  // Now that we have two copies of a, we can modify them separately
  // and pass the mto the functions

  // modify array, i.e. set [2][2] to '5'
  b[2][2] = 5;
  foo(b);
  // modify array i.e. set [2][2] to '3'
  c[2][2] = 3;
  foo(c);

This function would eat memory fast, since it leads to infinite recursion and creates two new 100-element arrays for each function call. The manual copying of a could also be done using memcpy, but I wrote it out as a nested for loop for clarity.

Collectives™ on Stack Overflow

Pass Array to Recursive Function While Modifying It C++

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related