CODEWITHSUNDEEP
crecursion
Alexandre Santos
Alexandre Santos

Reputation: 20

My recursive function only calculates half of even numbers

#include <stdio.h>

int succ(int x) {
  return x+1;
}

int pred(int x) {
  return x-1;
}

int is_zero(int x) {
  return x == 0;
}

int is_pos(int x) {
  return x >= 0;
}

int half(int x, int y) {
    return is_zero(y) ? x: half(pred(x), pred(pred(y)));
}

int half1(int x) {
    return half(x,x);
}

int main() {
    int x;
    scanf("%d", &x);
    int z = half1(x);
    printf("%d\n", z);
    return 0;
}

This is one of the first exercises I received in college and I am having a little difficulty. I can only use the functions succ,pred,is_zero,is_pos to make a recursive function that calculates half of a number and I can't use if or while. I made this code, but it only works for even numbers, for example input=30 output=15 but if input=17 it will not return an output. Any tips?

Upvotes: 0

Views: 135

Answers (2)

Fe2O3
Fe2O3

Reputation: 8344

Nesting AND recursion? Too complicated for my little brain... Trying to double increment one parameter while aiming for a particular target (zero)? Could be tricky to get the conditionals right (as comments and another answer have already indicated.)

Why not simply "meet in the middle"?

#include <stdio.h>

int succ(int x) { return x+1; }
int pred(int x) { return x-1; }
// int is_zero(int x) { return x == 0; }
int is_pos(int x) { return x >= 0; }

int half( int l, int h ) {
    return is_pos( l - h ) ? h : half( succ(l), pred(h) );
}

int half1( int x ) {
    // terms are multiplied by 0 or 1 depending on x being +/-.
    return half( (!is_pos(x))*x, is_pos(x)*x );
}

int main() {
    int vals[] = { 30, 17, -42, 0 };

    for( int i = 0; i < sizeof vals/sizeof vals[0]; i++ )
        printf( "%3d/2 = %d\n", vals[i], half1( vals[i] ) );

    return 0;
}

 30/2 = 15
 17/2 = 8
-42/2 = -21
  0/2 = 0

Upvotes: 0

Chris
Chris

Reputation: 36536

What happens when you try half1(17)?

half1(17)
half(17, 17)
half(pred(17), pred(pred(17)))
half(16, pred(16))
half(16, 15)
half(15, 13)
half(14, 11)
half(13, 9)
half(12, 7)
half(11, 5)
half(10, 3)
half(9, 1)
half(8, -1)
half(7, -3)
...

y in this case will never equal 0, so the recursion never ends.

You want to check if y is negative (not positive) or equal to zero.

int half(int x, int y) {
    return !is_pos(y) || is_zero(y) ? x : half(pred(x), pred(pred(y)));
}

Now, the recursion will end with half(8, -1) and 8 will be returned.

Upvotes: 5

Related Questions