Recursive tree function?

Question

I have an assignment I've been stuck on for too long. I'm supposed to consider all possible expressions from 1 to N like this:

n = 5;

1 % 2 % 3 % 4 % 5 = ?

where % can be addition, subtraction or multiplication ( + , - , * ) What I have to do is consider all possible combinations of these operations and count how many resulting expressions are equal to n itself.

So, for example, for n=4 the answer is 1, because there is only one expression that equals n.

1 + 2 - 3 + 4 = 4

There is also a couple more caveats to this - multiplication binds stronger than the other two operations. So for example

1 + 2 + 3 * 4 * 5 + 6 

needs to be parsed as

1 + 2 + (3 * 4 * 5) + 6

Additionally, multiplication can only be used a maximum of 5 times in a row (not in total), so anything under n=20 will be able to fit in integers. To tackle this problem I wrote this recursive tree, but at higher values such as n=15 my output becomes incorrect.

[N ] - [Expected result] [My program's result]
[5 ] - [              3] [                  3] 
[6 ] - [              1] [                  1]
[9 ] - [             27] [                 27]
[15] - [           3932] [               3911]
[16] - [           9803] [               9327]
[17] - [          23209] [              22942]

I've been trying to diagnose this for almost a week and can't get it working properly... I tried to make the code as readable as possible and commented where necessary. Just to explain what the code does - it builds a tree where the (+,- and *) are branches each iteration. Each node is the sum of the expression up to that point, so when we reach depth = n, all of the ending nodes are all possible expression sums - all we have to do is check if they equal to n. Illustrated below:

#include <stdio.h>

int n;
int result = 0;

void tree(int depth, int sum, int mul, int last) {
    //DEPTH = recursion from 1 to n
    //SUM = the sum of the expression
    //MUL = counter to track how many consecutive multiplications have been done
    //LAST = previous number added to sum

    //if n nodes reached
    if (depth == n) {
        if (sum == n) {
            //count result
            result++;
        }
        return;  
    }
    //build tree
    depth++;
    if (mul % 5 != 0) { //if multiplication hasn't been used 5x in a row
        tree(depth, (sum - last) + (last * depth), mul + 1, last * depth);
    } else {
        //else dont build a multiplication branch, but reset the counter
        mul = 1;
    }
    //build addition and subtraction trees
    tree(depth, sum + depth, mul, depth);
    tree(depth, sum - depth, mul, depth * -1);
}

int main(int argc, char **argv) {
    scanf("%i", &n);
    tree(1, 1, 1, 1);
    printf("%i\n", result);
    return 0;
}

UPDATE 1: MUL COUNTER CORRECTED

#include <stdio.h>

int n;
int result = 0;

void tree(int depth, int sum, int mul, int last) {
    //DEPTH = recursion from 1 to n
    //SUM = the sum of the expression
    //MUL = counter to track how many consecutive multiplications have been done
    //LAST = previous number added to sum

    //if n nodes reached
    if (depth == n) {
        if (sum == n) {
            //count result
            result++;
        }
        return;  
    }
    //build tree
    depth++;
    if (mul < 5) { //if multiplication hasn't been used 5x in a row
        tree(depth, (sum - last) + (last * depth), mul + 1, last * depth);
    } else {
        //else dont build a multiplication branch, but reset the counter
        mul = 0;
    }
    //build addition and subtraction trees
    tree(depth, sum + depth, mul, depth);
    tree(depth, sum - depth, mul, depth * -1);
}

int main(int argc, char **argv) {
    scanf("%i", &n);
    tree(1, 1, 0, 1);
    printf("%i\n", result);
    return 0;
}

Changes: Corrected the counter and starting values in accordance to answers (thank you!), but the program still produces incorrect results at high values, updated data:

[N ] - [Expected result] [My program's result]
[5 ] - [              3] [                  3] 
[6 ] - [              1] [                  1]
[9 ] - [             27] [                 27]
[15] - [           3932] [               3924]
[16] - [           9803] [               9781]
[17] - [          23209] [              23121]

The results are closer!!

Answer 1

I'm not sure this solves all problems but it is a bug.

This code:

if (mul % 5 != 0) { //if multiplication hasn't been used 5x in a row
    tree(depth, (sum - last) + (last * depth), mul + 1, last * depth);
} else {
    //else dont build a multiplication branch, but reset the counter
    mul = 1;
}

is wrong.

First of all you start by mul being 1. So it will take the true branch for the following values: 1, 2, 3, 4

So you only get 4 multiplication in total.

Try this instead:

if (mul % 6 != 0) { //if multiplication hasn't been used 5x in a row
          ^
          Notice...

    tree(depth, (sum - last) + (last * depth), mul + 1, last * depth);
}

Or better - don't use % - just use <

if (mul < 5) { //if multiplication hasn't been used 5x in a row
          ^
          Notice...

    tree(depth, (sum - last) + (last * depth), mul + 1, last * depth);
}

and start using mul equal 0, i.e. tree(1, 1, 0, 1);.

Answer 2

The major problem I see is that you don't reset the mul counter properly. Once you take a + or - branch, you have to reset it to allow 5 consecutive multiplications. A single + or - breaks that string.

So, in addition to the reset from 4386427's answer (use the zero-based one; I expect you'll find it less confusing), you'll need

tree(depth, sum + depth, 0, depth);
tree(depth, sum - depth, 0, depth * -1);

These recognize that the mult sequence counter is currently 0.

Answer 3

There are problems in your algorithm:

• the mul counter should start at 0.

• you should test for the constraint with if (mul < 5) instead of if (mul % 5 != 0)

• you should always pass 0 when you recurse for a different operator.

Note also that it is recommended to avoid global variables, especially with such short and meaningless names as n and result. It is better to use a state structure to which you pass a pointer.

Here is an improved version that can take the argument from the command line and prints the solutions:

#include <stdio.h>
#include <stdlib.h>

struct state {
    int n;
    int result;
    char ops[20];
};

void print_exp(struct state *sp, int depth, int sum) {
    for (int i = 1; i < sp->n; i++) {
        printf("%d %c ", i, sp->ops[i]);
    }
    printf("%d = %d\n", sp->n, sum);
}

void tree(struct state *sp, int depth,int sum, int mul, int last, char op) {
    // DEPTH = recursion from 1 to n
    // SUM = the sum of the expression
    // MUL = counter to track how many consecutive multiplications have been done
    // LAST = previous number added to sum

    //if n nodes reached
    sp->ops[depth - 1] = op;
    if (depth == sp->n) {
        if (sum == sp->n) {
            //count result
            sp->result++;
            print_exp(sp, depth, sum);
        }
        return;
    }
    depth++;
    if (mul < 5) { //if multiplication hasn't been used 5x in a row
        // recurse with a multiplication
        tree(sp, depth, (sum - last) + (last * depth), mul + 1, last * depth, '*');
    }
    // recurse with addition and subtraction operators
    tree(sp, depth, sum + depth, 0, depth, '+');
    tree(sp, depth, sum - depth, 0, -depth, '-');
}

int main(int argc, char **argv) {
    struct state s = { 0, 0, "" };

    if (argc > 1)
        s.n = strtol(argv[1], NULL, 0);
    else
        scanf("%i", &s.n);
    tree(&s, 1, 1, 0, 1, '\0');
    printf("%i\n", s.result);
    return 0;
}