My recursive function only calculates half of even numbers-CodePudding

#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?

CodePudding user response：

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.

CodePudding user response：

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( "=/2 = %d\n", vals[i], half1( vals[i] ) );

    return 0;
}

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

CodePudding user response：

nice puzzle, I'll give you my answer in python because I don't remember C

def half(x):
   def inner(x, y):
      if is_zero(y) or not is_positive(y):
         return x
      else:
         return inner(pred(x), pred(pred(y)))
   return inner(x, x)