CODEWITHSUNDEEP
crecursiontree
Aldo
Aldo

Reputation: 95

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.

Upvotes: 0

Views: 48

Answers (1)

4386427
4386427

Reputation: 44329

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.

Upvotes: 1

Related Questions