CODEWITHSUNDEEP
crecursionstatic
Ayesha Gupta
Ayesha Gupta

Reputation: 145

Can't decipher the output

#include<stdio.h>
int f(int n)
{
    static int a;
    if(n)
        a=n%10+f(n/10);
    return a;
}

int main()
{
    printf("%d",f(12345));
}

The output is 15. My doubt is how the stack memory is being used.

Upvotes: 1

Views: 61

Answers (4)

user803422
user803422

Reputation: 2814

The detailed stack usage is compiler dependent. But we can say roughly that for each call of function f, the "int n" is pushed onto the stack, thus occupying the size of an int. If you call your function recursively N times, then the stack usage reaches N*sizeof(int) bytes. You also probably need to add some bytes for the return value as well.

Upvotes: 0

doctorlove
doctorlove

Reputation: 19242

Let's pretend to be the computer:

  • f(12345)
    • make int a, set to 0 (as static)
    • a = 12345%10 + f(1234)
    • note program counter, so we remember where to come back to
      • f(1234)
      • a = 1234%10 + f(123)
      • note program counter, so we remember where to come back to
        • f(123)
        • a = 123%10 + f(12)
        • note program counter, so we remember where to come back to
          • f(12)
          • a = 12%10 + f(1)
          • note program counter, so we remember where to come back to
            • f(1)
            • a = 1%10 + f(0)
            • note program counter, so we remember where to come back to
              • f(0)
              • return a, i.e. 0 (since we haven't changed it yet)
            • return a = 1%10 + 0 = 1
          • return a = 12%10 + 1 = 3
        • return a = 123%10 + 3 = 6
      • return a = 1234%10 + 6 = 10
    • return a = 12345%10 + 10 = 15
Job done.

Upvotes: 2

Thanushan
Thanushan

Reputation: 532

On every recursive call to f() I denote n and with additional ' so n = 12345, a = 5 n' = 1234, a' = 4 n'' = 123, a'' = 3 n''' = 12, a''' = 2 n'''' = 1, a'''' = 1 n''''' = 0, a''''' = 0 (because a is static)

the answer is a + a' + a'' + .... = 15

Note: the a doesn't need to be static. int a = 0; will do.

Upvotes: 0

Ivan Smirnov
Ivan Smirnov

Reputation: 4435

You'll get the same result with following function implementation:

int f(int n) {
  if (n)
    return n%10 + f(n/10);
  return 0;
}

In your case behavior will be the same, and that's why. Firstly, when you initialize static int variable, it default value is 0 (unlike to just int declaration inside the function body). Secondly, the only value of n when your function just takes a value and does not assign it is 0, because when the line a=n%10 + f(n/10) evaluated, the recursive f() call happens before assignment to a, and its value remains unchanged before f(0) call.

Upvotes: 1

Related Questions