如何将此代码转换为递归功能?基本案例分析

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;
}

如果您会注意到，我使用? :操作员在printf语句中移动一个if块。

另外，请注意，每个printf都是从其自己的recurse函数调用中调用的，该调用位于堆栈上的所有其他功能调用中。因此，如果您的堆栈有限，并且n很大，则可能用完堆栈和崩溃。这是仅应谨慎使用递归功能的原因之一。

另外，您可以将 j递增的循环放在递归函数中，而只能恢复为递增i。那将使用少量堆栈。