使用C语言算法按顺序打印数字

Question

给出了示例模式，

input :    16
output:    16 11 6 1 -4 1 6 11 16

如果输入为10，则程序应该打印出以下输出。

10 5 0 5 10

注意：上述序列按5递减/递增。

挑战在于不声明任何变量或循环，仅使用递归。

我尝试使用以下代码。

void sequence(int input, int base){

    input = input - (input > 0?5:-5); //main execution
    printf("input:%d\n",input);
    if(input == base)return;
    sequence(input,base);
}

//例如，输入和基本(initial Value)为16。上述方法会递归地执行自身，直到输入=基数。

我可以打印出这个序列（用粗体表示）

16 11 6 1 -4 1 6 11 16

如何完成这个序列。在上述方法中，在主执行行中，我需要检查条件input = input - (input < 0?5:-5);来打印剩余的序列。但我不确定如何在没有任何变量或循环的情况下做到这一点。是否有可用的算法或任何其他更好的解决方案。

- iPhone Guy

---

需要左递归或右递归吗？如果不需要，只需在测试停止递归后再次输出即可...顺便说一句，您永远不需要base参数...达到递归的顶部帧就足够了。 - user2371524

@FelixPalmen：参数没有声明？（顺便说一句，楼主很可能混淆了声明和定义；我认为只声明变量并没有问题，因为在定义之前你无法使用它...） - too honest for this site

@Olaf 函数声明不是变量声明。是的，声明一个没有定义的变量不会影响代码的函数性，但这只是无用的--在这里真的很苛刻，抱歉 ;) - user2371524

@FelixPalmen：我在哪里说了这个？但是，实际上，参数也是一个本地变量（其类型/位置在外部已知），而且它也有声明/定义（允许在调用者中使用它们名称的语言使其更加可见）。我没有谈论函数本身。 - too honest for this site

@Olaf, 不是的，它是函数声明/定义的一部分。在[tag:c]中作为变量只是一个技术细节，在这里完全与明显是关于学习/教授函数式编程的问题无关。请友好地停止发表那些只会让人分心的“超级聪明”的评论，谢谢。 - user2371524

Answer 1

以下是一些示例代码，如果不需要严格的左递归或右递归，则可以匹配我的注释：

void sequence(int n)
{
    printf("%d ", n);
    if (n > 0)
    {
        sequence(n-5);
        printf("%d ", n);
    }
}

进一步说明：

1）这似乎是关于函数式编程的，其中一个关键概念是您永远不能分配变量……看看它在这里是如何避免的。（严格说来，由于printf的副作用，它不是函数式的）

2）它不是严格的左递归或右递归（意味着递归发生在评估的中间），因此无法轻松地转换为迭代。

- user2371524

---

@kkk，对于-16，您最喜欢的输出是什么？ - Wolf

-16 -11 -6 -1 4 -1 -6 -11 -16 - asio_guy

@kkk 只从 OP 中给出的示例中，这是一种可能的，但在我看来奇怪的假设。 - user2371524

@kkk：与原始代码相比，这将具有相反的方向（先增加，然后减少）。我期望它会打印“-16 -16”。第二个printf应该在if之外，但这将打印两次内部，因此可能需要特殊处理。 - too honest for this site

@Olaf，不应该这样，看看这些例子，最小的数字总是只打印一次。 - user2371524

Answer 2

似乎递归应该在达到0或以下时停止。因此，请在您的递归函数中尝试使用这个条件（缩减为只有一个参数）：

void sequence(input) {
    // print input
    if (input > 0) {
        // recursive call
        sequence(input);
    }
    // print input again (sometimes...)
}

更新：让我们谈谈对称性

为了对称起见，也可以使用Felix's solution的反向版本。

void sequence(int n)
{
    if (n > 0) {
        printf("%d ", n);
        sequence(n-5);
    }
    printf("%d ", n);
}

两者都具有一种不适合回文结构的不对称性，并且还存在另一个问题：尾随空格的瑕疵。因此，让我们向您介绍一个明显的解决方案，可以处理这些微小的缺陷：

void sequence(int n)
{
    if (n > 0) {
        printf("%d ", n); sequence(n-5); printf(" %d", n);
    } else {
        printf("%d", n);
    }
}

- Wolf

---

基础就是初始值。它是16。 - iPhone Guy

这将打印中间（最小）值两次；第二个打印语句应该放在if体内。 - M Oehm

@MOehm 是的，我知道，这就是为什么我在第二条评论中加入了“(有时候...)”的原因;-) - Wolf

@Wolf 如果空格很重要，最后一个不错。当然它仍然不是L或R递归 ;) - user2371524

Answer 3

使用两个不同的函数来实现计数：一个是递增，另一个是递减。

void down(int input, int base) {
    printf("input:%d\n",input);
    if(input > 0) down(input - 5, base);
    else up(input + 5, base);
}

void up(int input, int base) {
    printf("input:%d\n",input);
    if(input == base) return;
    up(input + 5, base);
}

通过调用down开始计算。

演示实况

- alain

---

当你从递归函数返回时，你又开始上升了。 - M Oehm

不，查看实时演示。 - alain

当然可以。你递归的深度是你需要的两倍。也许我的评论有歧义，它并不是指你的解决方案，虽然它可行但过于冗长，而是指所谓的解决方案，在递归后再添加另一个打印语句。 - M Oehm

是的，没错。但是这个答案表明一个变量可以被另一个递归路径调用替换，有时候这是很有用的。（这就是为什么我认为这个答案增加了价值。） - alain

Answer 4

#include <stdio.h>

using namespace std;

void printSequence(int input) {
    printf("%d ", input);
    if (input <= 0)
        return;
    printSequence(input - 5);
    printf("%d ", input);
}

int main ()
{
    int input = 0;
    scanf("%d", &input);

    printSequence(input);

    return 0;
}

- smyatkin_max

Answer 5

你的递归代码的基本情况似乎有误。我认为你的代码会以现在的方式进入无限递归。你可以使用一个标志来实现你的序列：

void sequence(int input, int base){
    static int flag = 0;
    //input = input - (input > 0?5:-5); //main execution, wrong
    printf("input:%d\n",input);
    input -= (flag == 0)?5:-5;          //use flag for base case of sequence
    if(input <= 0)
        flag = 1;
    if(input == base){
        printf("input:%d\n",input);
        return;
    }
    sequence(input,base);
}

- vish4071

---

变量不应该被使用（在问题中提到），而且使用标志也不是一个好习惯 :) - iPhone Guy

啊，是的。根据OP的条件，我使用了一个错误的标志，但是为什么你说使用标志是不好的习惯？ - vish4071

我是指与上面的原帖相关。 - iPhone Guy