Как я могу преобразовать этот код в рекурсивную функцию? Анализ базового случая

Question

#include <stdio.h>

int main() {
    int n;
    printf("Enter width: ");
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
       for (int j = 0; j < n; j++) {
           if (i == j || (i + j + 1) == n) {
               printf("X");
           } else {
               printf(" ");
           }
       }
       printf("\n");
    }
    return 0;
}

Как я могу преобразовать этот код в рекурсивную функцию? У меня проблемы с "базовым случаем", я пытаюсь работать с этой строкой

void recursiveProblem(int num, int max) {
    if (num <= (max / 2 + 1))
        ...
}

поэтому, если я достигну половины пути, я смогу напечатать среднюю строку и вернуть ее, но она не работает. Эта функция напечатает большой X из x?

Answer 1

Для решения задач с использованием рекурсии вы можете использовать этот шаблон:

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

В вашем случае задание print_diagonals(width_of_the_square, current_line_number).

Определение этой задачи путем присвоения ей правильного имени и определения параметров и их названий является наиболее важной частью решения такого рода проблем. Намного легче думать о print_diagonals, чем о recursiveProblem, поскольку имена, которые я дал, несут много смысла и точно описывают их назначение.

«Тривиальный случай» в этой задаче может быть «напечатать линию в середине квадрата» или «напечатать нижнюю линию квадрата». Оба будут работать, и программы будут выглядеть одинаково. Попробуйте их обоих, а затем сравните полученные программы. Часть, общая для этих программ, типична для рекурсивных программ.

Используя эту информацию, вы сможете самостоятельно выполнять домашнее задание.

Answer 2

Я не понимаю, почему кто-то хотел бы сделать это рекурсивным. Но это работает.

#include <stdio.h>

void recurse(int i, int j, int n){
    printf(i==j || i+j+1==n ? "X" : " ");
    if (++j == n) {
        printf("\n");
        if (++i == n)
            return;
        j=0;
    }
    recurse(i, j, n);
}

int main(){
    int n;
    printf("Enter width: ");
    scanf("%d",&n);
    recurse(0, 0, n);
    return 0;
}

Если вы заметите, я перемещаю один if блок прямо внутри оператора printf, используя оператор ? :.

Кроме того, обратите внимание, что каждый printf вызывается из своего собственного recurse вызова функции, который находится поверх любого другого вызова функции в стеке. Поэтому, если ваш стек ограничен и n велик, вы можете выйти из стека и потерпеть крах. Это одна из причин, по которой рекурсивные функции следует использовать только с осторожностью.

В качестве альтернативы, вы можете поместить цикл, который увеличивает j в рекурсивную функцию, и только рекурсивно увеличивать i. Это будет использовать намного меньше стека.