CODEWITHSUNDEEP
crecursion
noname delete
noname delete

Reputation: 1

why is this recursive function doesn't return 'counter' value?

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?

Upvotes: 0

Views: 133

Answers (3)

Randomblock1
Randomblock1

Reputation: 53

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

Upvotes: 1

Yonatan Pozner
Yonatan Pozner

Reputation: 1

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

Upvotes: 0

chux
chux

Reputation: 153348

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.

Upvotes: 0

Related Questions