Как пройти 2D массив с помощью рекурсии

Question

Я ищу кого-нибудь, кто поможет мне пройти и отобразить 2d массив или матрицу с помощью рекурсии.

void display(int** matrix1,int row, int column)

Вот что я делаю для 1D массива:

void print_array(int arr[], int size, int i)
{

    if (i == size) {
        cout << endl;
        return;
    }
    cout << arr[i] << " ";
    print_array(arr, size, i+1);
}

Я знаю, как пройти 1D массив, но не могу этого сделать. Я хочу отобразить каждый элемент в матрице, используя рекурсию.

Answer 1

Прежде всего, не совсем понятно, зачем вам рекурсивное решение. Возможно, это вопрос времени, но мне трудно писать, читать и отлаживать рекурсию. В любом случае, я позволил себе изменить вашу 1d версию:

#include <iostream>
#include <vector>

void print_array(const std::vector<int>& arr,size_t i = 0) {
    if (i == arr.size()) {
        std::cout << '\n';
        return;
    }
    std::cout << arr[i] << " ";
    print_array(arr, i+1);
}

Я использую size_t вместо int, потому что это тип, который будет использоваться при сравнении с размером контейнеров. Я поставил значение по умолчанию для i, потому что при его вызове вы не хотите передавать индекс, а просто печатаете весь массив. std::endl не только печатает новую строку, но и очищает поток. Это не нужно в большинстве случаев.

Для двумерного случая все, что вам нужно добавить, это второй индекс и условие для go для следующей строки.

То есть, если сигнатура функции

void print_array(const std::vector<std::vector<int>>& arr,size_t i=0,size_t j=0)

, и он печатает arr[i][j], затем вам нужно вернуться, ничего не печатая, когда i == arr.size(), и вам нужно перейти к следующей строке, когда j== arr[i].size(). Это может быть сделано с условием по линии:

    if (j == arr[i].size()) {
        std::cout << '\n';
        print_array( arr, i+1,0);  // start with the first element of next row
        return;
    }

PS , если вы настаиваете на int**, это должно быть легко адаптироваться, но я настоятельно рекомендую используйте vector и, возможно, даже std::vector<std::array>, если все внутренние массивы имеют одинаковый размер.

Answer 2

Я уверен, что вам нужно написать программу C или программу на C ++, но с использованием функциональности C из-за вашего объявления "2D-массива", например int ** .:)

Функция может быть легко реализована, если использовать еще одну вспомогательную рекурсивную функцию.

Вот демонстрационная программа

#include <stdio.h>

void display_row( int *a, size_t column )
{
    column == 0 ? ( void )putchar( '\n' )
                : ( void )( printf( "%2d ", *a ), display_row ( ++a, --column ) );
}

void display( int **a, size_t row, size_t column )
{
    if ( row != 0 )
    {
        display_row( *a, column );
        display( ++a, --row, column );
    }
}

int main(void) 
{
    enum { M = 3, N = 4 };

    int a1[N] = {  1,  2,  3,  4 };
    int a2[N] = {  5,  6,  7,  8 };
    int a3[N] = {  9, 10, 11, 12 };

    int *a[M] = { a1, a2, a3 };

    display( a, M, N );

    return 0;
}

Вывод программы:

 1  2  3  4 
 5  6  7  8 
 9 10 11 12 

Если не используйте вспомогательную функцию, тогда другой подход - использовать переменную stati c внутри рекурсивной функции.

Вот демонстрационная программа, которая использует рекурсивную функцию с переменной stati c.

#include <stdio.h>

void display( int** a, size_t row, size_t column )
{
    static size_t pos = 0;

    if ( row != 0 && column == 0 )
    {
        putchar( '\n' );
        size_t tmp = column;
        column = pos;
        pos = tmp;
        --row;
        ++a;
    }       

    if ( row )  
    {
        printf( "%2d ", a[0][pos++] );
        display( a, row, --column );
    }       
}

int main(void) 
{
    enum { M = 3, N = 4 };

    int a1[N] = {  1,  2,  3,  4 };
    int a2[N] = {  5,  6,  7,  8 };
    int a3[N] = {  9, 10, 11, 12 };

    int *a[M] = { a1, a2, a3 };

    display( a, M, N );

    return 0;
}

Вывод такой же, как показано выше.

Если вам нужна программа на C ++, просто включите заголовки

#include <iostream>
#include <iomanip>

и вместо, например, этого вызова printf

printf( "%2d ", a[0][pos++] );

использование

std::cout << std::setw( 2 ) << a[0][pos++];