CODEWITHSUNDEEP
cfunctionrecursiondefinition
noor napso
noor napso

Reputation: 113

How does this recursive function return the correct answer?

I wanted to know how this function returns 4 which is the correct answer, when it resets the res variable every time the function calls itself. num = 2367319

int func(int num)
{
    int res = 0;
    if (num > 0)
        res = (num % 10 % 3 == 0 ? 1 : 0) + func(num / 10);

    return res;
}

Upvotes: 2

Views: 109

Answers (4)

TruthSeeker
TruthSeeker

Reputation: 1579

In simple words, when function is called all it's local variables are created on stack(i.e stack pointer incremented by amount of local variables used). Upon function exit stack pointer is decremented by same amount.

Consider below example, function foo() with some bytes of local variables calling a bar() with some other bytes of local variable. (For simplistic purpose I have excluded the function return address from stack)

 /*stack growth in this direction ---->*/


 foo()-------+
             |
    /*foo code execution */
             | 
           bar()----------+
                          |
                  /* bar() Code execution */
                          | 
             +------------+
             |
|------------+

As functions is called stack is expanded and shrinks upon function exit.

In case of recursive function bar() happens to be foo() again and again. But new stack location is allocated for every function call.

And hence in your case res is being set to zero at different stack location even though it appears to be same variable name.

Upvotes: 0

Vlad from Moscow
Vlad from Moscow

Reputation: 310930

For starters the declaration and the implementation of the function is bad.

The function parameter has the type int. So the user can supply a negative number and will await how many digits of the number are divisible by 3. However the function returns 0. A question arises: and what to do with negative numbers? To write one more function?

The second problem is that the function is unable to process integer numbers of types long int and long long int. Again do we need to write separate functions for these signed integer types?

The function uses an redundant variable res.

It can be declared and implemented the following way as it is shown in the demonstrative program below..

#include <stdio.h>

unsigned int func( long long int n )
{
    const long long int Base = 10;

    return n == 0 ? 0 : ( n % Base % 3 == 0 ) + func( n / Base );  
}

int main(void) 
{
    printf( "%d : %u\n", 2367319, func( 2367319 ) );
    printf( "%d : %u\n", -2367319, func( -2367319 ) );

    return 0;
}

The program output is

2367319 : 4
-2367319 : 4

How does the function works?

If the n is equal to 0 then the function returns 0.

    return n == 0 ? 0 : ( n % Base % 3 == 0 ) + func( n / Base );  
           ^^^^^^   ^^

Otherwise if the last digit n % Base (the remainder of division by 10) of the number is divisible by 3 then this expression

    return n == 0 ? 0 : ( n % Base % 3 == 0 ) + func( n / Base );  
                          ^^^^^^^^^^^^^^^^^^

yields 1 (true). Otherwise it yields 0. So the function counts the number of digits divisible by 3 in such a way recutsively.

For example let's consider the number 2367319.

The expression 2367319 % 10 yields the digit 9. 9 % 3 (2367319 % 10 % 3) is equal to 0. So the expression

2367319 % 10 % 3 == 0

yields 1.

Now the function calls itself with the number 2367319 / 10 that is with the number 236731. And the operation with the last digit of this new number is repeated. In this case the expression

236731 % 10 % 3 == 0

evaluates to 0 (false).

And so on. All results of the function calls are accumulated and returned.

In fact you will have

(2367319 % 10 % 3 == 0) + (236731 % 10 % 3 == 0) + (23673 % 10 % 3 == 0) +...+ 0

         1              +         0              +        1              +...+ 0

Upvotes: 0

Code-Apprentice
Code-Apprentice

Reputation: 83527

res isn't "reset". Rather a new local variable named res is created for each recursive call.

I suggest you add some printf() statements in order to see how this function works.

Upvotes: 9

Lajos Arpad
Lajos Arpad

Reputation: 76426

res equals the number of digits divisible with 3. It will always get a proper value, as long as num is still greater than 0.

Upvotes: 0

Related Questions