c - 如何将此函数重新实现为尾递归或以其他方式使用更少的内存？

Question

我需要递归地进行以下计算。

对于 1 到 30 之间的任何 n，我需要考虑从 1 到 n 的所有可能的加法或减法组合。因此，例如如果 n = 5:

1 ± 2 ± 3 ± 4 ± 5 ± 6 = ?;

我需要找到与数字本身相等的可能表达式的数量。因此，对于 n = 5，只有以下两个表达式等于 5:

5 = 1 + 2 + 3 + 4 − 5
5 = 1 − 2 − 3 + 4 + 5

我的方法

我想出了如何创建一个递归树，其中每个递归级别都会添加或减去“深度”。因此，在最终深度，节点将已经计算出总和 - 我所要做的就是检查它们是否等于初始数量。

Recursive Tree Image

这工作正常，但是当数字 n>26 时，我会遭受巨大的内存消耗，并且程序花费的时间太长。稍微数学一下就可以清楚为什么。那么我该如何优化呢？我一直在尝试将其变成尾递归，但它对我来说不起作用......我根本不明白当我有两个递归调用时如何实现它。

这是我的代码:

树结构及创建函数

typedef struct nodes {
    unsigned int value;
    struct node* pos;
    struct node* neg;
} node;


node* addNode(int data){

    node* newNode = (node*)malloc(sizeof(node));
    newNode->value = data;
    newNode->pos = NULL;
    newNode->neg = NULL;

    return newNode;
}

构建我的树的函数

node* buildTree(int depth, int data){

    node* nNode = addNode(1);

    if(depth==n+1){
        if(data == n) {
            result++;
        }
        return nNode;
    }

    else{
        nNode->pos = buildTree(depth+1,data+depth);
        nNode->neg = buildTree(depth+1,data-depth);
        return nNode;
    }
}

全局范围变量和主变量:

int result = 0;
int n;

int main(int argc, char **argv)
{
    scanf("%i",&n);
    buildTree(2,1); //build tree starting with recursion depth = 2, first node value = 1.
    printf("%i\n",result);

    return 0;
}

请帮忙——我在这件事上坚持了太久。

Answer 1

我认为你不需要一棵树来做这个。

一些简单的递归应该做:

#include <stdio.h>

void f(int current_sum, int current_depth, int target_depth)
{
    if (current_depth > target_depth)
    {
            // Here you have the final result for this path
        printf("%d\n", current_sum);
        return;
    }
    f(current_sum+current_depth, current_depth+1, target_depth);
    f(current_sum-current_depth, current_depth+1, target_depth);
}

int main(void) {
    f(0, 1, 3);   // I use n=3
    return 0;
}

Output:

6
0
2
-4
4
-2
0
-6

提示:通过注意后半部分的数字是前半部分的负数，您可以大大提高运行时性能。使用类似的东西:

    f(current_sum+current_depth, current_depth+1, target_depth);
    if (current_depth != 1)
    {
        f(current_sum-current_depth, current_depth+1, target_depth);
    }

实现这一目标。