Member Avatar for ihatestarch

What would a recursive function (not from a class) that puts some kind of element (like an integer) into a 2D array look like?

I noticed a 2D array seems to be a bit different from a regular array in a function.

Is the first bracket always empty and the second bracket hold the size?

void Array(int array[][10])

How can you change the value in the different rows and columns recursively? Or even how can you manipulate the rows and columns recursively? I feel as if I NEED the for loop. I couldn't find a model example of this in my book.

  • 3 Contributors
  • 4 Replies
  • 2K Views
  • 1 Day Discussion Span
  • Latest Post Latest Post by ihatestarch

Dani AI

Generated

is right about why the leftmost dimension can be left unspecified: the compiler only needs the column count to compute row-to-row offsets. If you must work with a raw 2D array, pass the column size and the row count separately. For this particular task (Pascal-like recurrence), recursion can replace both the element formula and the row/column traversal.

Here is a simple, loop-free, in-place fill. It walks the matrix recursively in row-major order and uses the standard recurrence so each cell depends on the two cells above it. Base cases handle the top row and left column.

template<size_t C>
void fill_pascal(int (*a)[C], int rows, int cols, int i = 0, int j = 0) {
    if (i >= rows) return;                 // done
    if (j >= cols) return fill_pascal(a, rows, cols, i + 1, 0);  // next row

    if (i == 0 || j == 0) {
        a[i][j] = 1;                       // edges are 1s
    } else {
        a[i][j] = a[i - 1][j - 1] + a[i - 1][j];  // recurrence
    }
    fill_pascal(a, rows, cols, i, j + 1);  // next column
}

How to use it: create your array in main, call fill_pascal(arr, rows, cols), then print however you like. If your assignment already pre-fills with 1s, you can keep that, but the base case above makes the function self-contained.

A couple of notes for :

  • Return type: use void for the traversal that mutates the array; if you also want a pure function int cell(i,j) that returns a value, make that a separate helper and have the traversal write its result.
  • Bounds: ensure cols does not exceed the compile-time C. If you cannot use templates, a common alternative is void fill(int a[][MAXC], int rows, int cols, ...).
  • Complexity: this version is O(rows*cols) and avoids the exponential blowup you would get from naively recomputing subproblems, as hinted.

Recommended Answers

All 4 Replies

Member Avatar for vmanes

Ouch - I'm getting a headache just thinking about a recursive 2D function - but it is a technique used in maze running problems. Your main concern is determining your base case and determining in what manner you will modify the parameters in the recursive call.

Concerning the array parameter, yes, you leave the highest order size empty in the parameter list. All lesser sizes (say in 3D, 4D arrays) must be specified. This is because the compiler must be able to know how far in memory it is from the beginning of one row to the beginning of the next. It does not need to explicitly know how many rows there are. In this way, your 2D array handling function can be used with different arrays of any number of rows, as long as they have the same number of columns. You will generally pass the number of rows as an additional parameter to your function.

If your task is just to fill the array, then simple nested for loops is the best solution, both in terms of simplicity and performance.

Can you elaborate on the actual problem statement?

Member Avatar for ihatestarch

I only WISH I could use nested for loops for this problem.

The actual problem? I need to write a recursive function that changes the contents of a 2D array. Main.cpp creates that array and fills it with 1's. I must add the first two numbers and place the answer in the matrix below the second number.

I hope I don't sound too confusing. My for loop does this problem fine:

for(int i=0; i<10; i++)
    {
        for(int j=0; j<10; j++)
        {
            array[i+1][j+1] = array[i][j] + array[i][j+1];
             cout << array[i][j] << "    ";
        }
        cout << endl;
    }

I want to figure out the code recursively, but I don't have a clue how to set up the function so that I can manipulate the rows and columns like I did in the for loop or what the process might appear like in main.

Thanks for the explanation of the 2D array bracket values btw.

Member Avatar for Sky Diploma

I think you will basically need a square matrix, ie: no. of columns = no. of rows. then, You could do somthing like this

Well the recursive function might be applied on only the last row.

you could say somthing like

val(x,y)=val(x-1,y-1)+val(x-1,y);

This would be the function which should end return val = 1 if the position of x or y is out of bounds.....

Hope this is the solution you are looking for.

The Problem is that only half of the area will be filled(correctly) by this function if we execute it for the last element.

Member Avatar for ihatestarch

Well the recursive function might be applied on only the last row.

you could say somthing like

val(x,y)=val(x-1,y-1)+val(x-1,y);

This would be the function which should end return val = 1 if the position of x or y is out of bounds.....

Hope this is the solution you are looking for.

The Problem is that only half of the area will be filled(correctly) by this function if we execute it for the last element.

I knew the formula would look like that, it's just like the loop almost. But I was a bit foggy on the base case. So, when I call a function in main, will the code display like this?

arrayfunction(array, row, col);
    
    for(int i=0; i<row; i++)
    {
        for(int j=0; j<col; j++)
        {
            cout << array[i][j] << "   ";
        }
        cout << endl;
    }

And would the function return an int or would it be void? I'm thinking I pass by reference by using void because I'd use it if I were using a for loop in my function. I'm new to recursion so I'm not sure.

Edited by ihatestarch because: additional question
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.