Aldo - 8 months ago 31
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* 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){

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

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.