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

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 supposed to get a number k and check how many operations needed to get k to zero only by multiplying by 2 or by adding 1. this function works fine, but returns zero instead of the last value in counter. I tried to debug it, I saw the counter value increasing, but after getting to the value it supposed to return, the function goes backwards to complete all the calls, and returning 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 counter inside the function?

Why is this function returning zero at the end?

CodePudding user response：

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)
{
    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

CodePudding user response：

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.

CodePudding user response：

This should work

int rec(int k)
{
    static int temp = 0, counter = 0;

    if (k == 0)
        return 0;

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

function call

int main()
{
    printf("%d", rec(10));
    return 0;
}

output