c++ - 写一个简单的数字三角形的建议，只有递归，没有循环？

Question

所以我已经编写了一个函数来使用多个 for 循环编写一个可变高度的数字金字塔，它运行得非常好。

这是我所说的那种金字塔的例子:

用户输入 4

      1 

    1 2 1

  1 2 3 2 1 

1 2 3 4 3 2 1 

所以我确实需要用空格填充左侧。

我的问题是我无法让它只使用递归，没有循环。就递归而言，我什至想不出从哪里开始，真的。我知道我需要一个基本案例，以及处理该基本案例的方法。

我应该写多个递归函数，还是只写一个递归函数？ (除了 main，我是说。)

这是我目前所拥有的(一点也不多):

void givepyramid(int lines);  //lines = Number of lines in pyramid (4 in example above)
{
     if lines == 1;
        cout << (//all the spaces needed)<<1;
     else
         cout << (I'm not too sure on how to go about this here.)
}

如有任何建议，我们将不胜感激!谢谢。

Answer 1

这是一个简单的解决方案，它可以在不使用循环的情况下绘制漂亮的三角形:

#include <iostream>

void printRowNumbers( unsigned int n, unsigned int max )
{
    if ( n < max ) {
        std::cout << n << ' ';
        printRowNumbers( n + 1, max );
    }
    std::cout << n << ' ';
}

void drawTriangle( unsigned int n, unsigned int indent = 0 )
{
    if ( n > 1 ) {
        drawTriangle( n - 1, indent + 2 );
    }
    std::cout << std::string( indent, ' ' );
    printRowNumbers( 1, n );
    std::cout << "\n";
}

主要思想是您通常会使用循环来解决两个问题:

1. 打印一行数字(没有任何特定缩进)，如 1 2 3 2 1 或 1 2 3 4 5 4 3 2 1。关键思想是，您不仅打印数字到最大值并返回，实际上您打印的数字是从某个起始值(这里似乎总是 1)到一个最大值，然后回到起始值。

   洞察力是从 1 到 5 打印这样一个“数字镜像”并返回与打印 1，然后从 2 到 5 打印一个镜像，然后再次打印 1 是一样的。从 2 到 5 打印镜像与打印 2，然后从 3 到 5 镜像，然后再次打印 2 相同。依此类推，直到最小值与最大值相同，在这种情况下，您只需打印该数字(这是您的基本情况)。

2. 打印多次，每次都换行，缩进越来越小。我们需要一个可以多次打印某物(例如，一封信)的函数 - 每次都在自己的行上并且缩进不断减少。最后一行根本没有缩进。简单的情况是只打印一行——在这种情况下你根本没有任何缩进。打印两行与先打印一行，缩进为 2，然后再次打印该行是一样的。打印三行意味着首先打印两行缩进为 2(这反过来意味着打印一行缩进为四!)，然后是第三行不缩进。

   我们的代码恰好不打印一些随机字母，drawTriangle 函数负责正确缩进(并打印换行符)，但让 printRowNumbers 打印实际数字。

如您所见，我没有使用非常复杂的分析方法(可以将任何循环重写为递归，因此您可以编写一个循环，然后通过遵循一些规则将其机械地转换为递归)。相反，我只是手工做了一些实验，比如“做两次和只做一次有什么不同，做三次和做两次有什么不同”，然后找出一个模式。