Aldo Aldo - 1 month ago 6
C Question

How can I reimplement this function as tail-recursion or otherwise use less memory?

I need to recursively do the following calculation.

For any n between 1 and 30 I need to consider all possible combinations of addition or subtraction from 1 to n. So, for example if n = 5:

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


I need to find the number of possible expressions that equal the number itself. So for n = 5, only the following two expressions equal to 5:

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


My approach

I figured out how to create a recursive tree where each level of recursion will add or subtract the 'depth'. So as as result, at the final depth, the nodes will already have the calculated sum - all I have to do is check whether they equal to the initial number.

Recursive Tree Image

This works alright, but at larger numbers n>26 I suffer from huge memory consumption and the program takes too long. A little maths makes it clear why.
So how can I optimise this? I've been trying to turn it into tail-recursion but it's not working out for me... I simply don't understand how to implement that for when I have two recursive calls.

Here is my code:

Tree structure and creation function

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


Function that builds my tree

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


Global scope variables & main:

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


Please help — I've been stuck too long on this.

Answer

I don't think you need a tree for this.

Some simple recursion should do:

#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

TIP: You can improve run time performance a lot by noticing that the last half numbers are the negative of the first half. Use something like:

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

to achieve that.