0
int rec(int k)
{
    static int temp = 0, counter = 0;
    if(!k) return counter;
    if(k%2 == 0){
        counter++;
        temp = rec(k/2);
    }
    if(k%2){
        counter++;
        temp = rec(k-1);
    }
}

This function is supposed to get a number k and check how many operations are needed to get k to 0 only by multiplying by 2 or by adding 1. this function works fine but returns zero instead of the last value in the counter. I tried to debug it, and I saw the counter value increasing, but after getting to the value it is supposed to return, the function goes back to complete all the calls, and returns 0. I fixed it by making counter global and returning nothing, but my questions are:

Is there a way to fix it as it is with the counter inside the function?

Why is this function returning zero at the end?

Sidharth Mudgil
  • 1,293
  • 8
  • 25
noname delete
  • 1
  • 4
  • 2
    What happens if `if(!k)` is *not* true? What do your function return then? Please explain that to your [rubber duck](https://en.wikipedia.org/wiki/Rubber_duck_debugging). – Some programmer dude Dec 06 '22 at 09:08
  • On another note, `if (k % 2 == 0) { ... } if (k % 2 != 0) { ... }` (that's what your conditions essentially are) could be written as `if (k % 2 == 0) { ... } else { ... }` – Some programmer dude Dec 06 '22 at 09:11
  • 1
    What is the purpose of `temp`. You assign to it but you never read it. – Konrad Rudolph Dec 06 '22 at 09:12
  • @Someprogrammerdude, Thank you for the answer, if `if(!k)` is not true, it progresses as it should. this if is there to return only when k is 0. – noname delete Dec 06 '22 at 09:14
  • @KonradRudolph I will use it later in my program after I know this function works. – noname delete Dec 06 '22 at 09:16
  • If you declare a function to return a value, you *must* explicitly have a `return` statement to return a value. Other than the `main` function, there are no implicit returns. – Some programmer dude Dec 06 '22 at 09:22
  • 5
    Instead of wasting your own and everyone else's time trying to find bugs that the compiler has already spotted, you could start listening to what the compiler has to say: [What compiler options are recommended for beginners learning C?](https://software.codidact.com/posts/282565) "warning: variable 'temp' set but not used", "warning: control reaches end of non-void function". Why thank you Mr gcc, you spotted two bugs in less than 1 second! – Lundin Dec 06 '22 at 09:22
  • @Lundin wasting time? If you don't want to answer, just don't answer! you are wasting my and others time by writing this kind of comments. I clearly ask because I couldn't manage to figure it out by myself. – noname delete Dec 06 '22 at 09:36
  • @nonamedelete And the reason why you couldn't, is because you ignored the compiler. And next time you get a similar bug, you won't be able to quickly figure out why either. On and on it goes until you finally enable compiler warnings/errors and pay attention to them. – Lundin Dec 06 '22 at 10:14
  • Only for the pedantic: `rec(INT_MIN)` leads to UB on non-2's complement machines as `INT_MIN` is odd and `INT_MIN -1` is `int` overflow. Not to worry, C2x will fix that. – chux - Reinstate Monica Dec 06 '22 at 10:52
  • *"check how many operations are needed to **get k to 0** only by **multiplying by 2** or by **adding 1**."* I guess you mean the other way around. Also, it seems your function expects only positive values, is there that constraint too? – Bob__ Dec 07 '22 at 09:51
  • @Bob__ This is the way I solved the problem. To go from the end and devide/subtract instead of going from the beginning and multiply/add. – noname delete Dec 07 '22 at 10:36

3 Answers3

1

Here's a nice recursive function that doesn't declare any variables at all, it's purely recursive!

int get_steps_to_zero(int n)
{
    // Deal with negative values
    if (n < 0) n *= -1;
    if (n == 0) {
        // Base case: we have reached zero
        return 0;
    } else if (n % 2 == 0) {
        // Recursive case 1: we can divide by 2
        return 1 + get_steps_to_zero(n / 2);
    } else {
        // Recursive case 2: we can subtract by 1
        return 1 + get_steps_to_zero(n - 1);
    }
}

get_steps_to_zero(457);
> 13
Randomblock1
  • 51
  • 4
  • This is a far better way to do it. And you can call this function more than once, which you can't do with static variables. – pmacfarlane Dec 06 '22 at 10:06
  • I got curious machine code when I checked the result of this function in gcc and posted a separate question here: [Why would gcc -O3 generate multiple ret instructions?](https://stackoverflow.com/q/74700866/584518) – Lundin Dec 06 '22 at 10:25
  • Randomblock1, for fun, try `get_steps_to_zero(-1)` with your code. – chux - Reinstate Monica Dec 06 '22 at 11:03
0

Others have addressed the general recursion issue, yet there remains a ...

Corner case

"this function works fine" --> Not quite.

The algorithm is an infinite loop for rec(-1) as it attempts -1 --> -2 --> -1 --> -2 ...

A better approach would sometimes add 1.

if(k%2) {
  counter++;
  // temp = rec(k-1);
  temp = rec(k + (k < 0 ? 1 : -1));
}

This also well handles non-2's complement issue.

chux - Reinstate Monica
  • 143,097
  • 13
  • 135
  • 256
0

I will try to show a new side to this discussion, Recursion is like a chain, This means that any function can receive a value from its child and return a value to its parent. In your program you are trying to return a value from the last child to the first parent, So your program must have all links in the chain receive and send value in order. But in your code you return a value only in the last call, and all other calls do not return this value back.

Your stop condition is here:

if(!k) return counter;

Only the last call enters this scope, but other calls do not reach any return statement. they get to here:

if(k%2 == 0){
        counter++;
        temp = rec(k/2);
    }
    if(k%2){
        counter++;
        temp = rec(k-1);

here there is no return statement.

your compiler will warning you like this: "warning: control reaches end of non-void function". but your program will compile so it return zero like all non-void functions without return.

So if you want this program to work make it like Randomblock1, or like this:

int rec(int k)
{
    static int counter = 0;
    if(!k){
       return counter; 
    }
    else if(k%2 == 0){
        counter ++;
        counter += rec(k/2);
    }
    else{
        counter++;
        counter += rec(k-1);
    }
    return counter;
}

But this program also do not work well, what is the reason? The reason is because you used by static variable. It's a little hard to explain, but you can't use this recursion with a static variable, so add a patch to this line:

static int counter = 0;

like this

int counter = 0;

I hope what I wrote will be understandable

Yonatan Pozner
  • 1
  • 1