在这种情况下首选递归吗？

Question

假设我们有一个字符串，我们想以相反的顺序打印它。在这种情况下，递归似乎是更快的选择，因为字符串被“遍历”一次，而通常的循环方法会“遍历”两次。

对于这类问题，有什么理由不喜欢递归？在大输入的情况下，递归是否会造成某种不利？

考虑以下代码：

#include <stdio.h>
#include <string.h>

void printReverse_1(const char *str)
{
    if (!*str)
        return;

    printReverse_1(str + 1);
    putchar(*str);
}

void printReverse_2(const char *str)
{
    const char *tmp = str + strlen(str) - 1;

    while (tmp > str)
    {
        putchar(*tmp--);
    }
    putchar(*tmp);
}

int main(void)
{
    printReverse_1("abc");
    putchar('\n');

    printReverse_2("abc");
    putchar('\n');

    return 0;
}

Answer 1

有什么理由不喜欢在这类问题中使用递归？在大输入的情况下，递归是否会造成某种不利？

递归为每个函数调用创建一个新的堆栈帧。对于大型输入，它可能会耗尽堆栈空间。如果可能，更喜欢迭代而不是递归。