Aldo - 2 months ago 11

C Question

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

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:

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

}

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.