Recursion and return statements in C

Question

Please explain how the return call from nested recursive function propagates all the way out to main?

I came across the following code segment in a book. The printf output is '6, 12'

In the recursive function sumdig(), a return statement is called in third recursive call.

When sumdig() now returns to the second recursive call, sumdig() should evaluate to an expression, not a return statement (i.e. return sumdig(n)).

But that is not what seems to happen. The return call from the recursive function is being propagated all the way out to main.

Can anyone please explain how the return call from nested recursive function propagates all the way out to main?

The code below would have made sense to me if the recursive call was something like 'return sumdig(n)'.

main()
{

  int a, b;

  a = sumdig( 123 );
  b = sumdig( 123 );

  printf( "%d, %d\n", a, b);

}

sumdig(int n)
{
  static int s = 0;
  int d;

  if(n != 0)
  {
    d = n % 10;
    n = (n - d) / 10;
    s = s + d;

    sumdig(n);

  }
  else
    return(s);
}

Recursive calls for Sumdig

Initial call           :n = 123, s = 0
First recursive call   :n = 12,  s = 3
Second recursive call  :n = 1,   s = 5
Third recursive call   :n = 0,   s = 6   // Return statement happens here

Likewise For Second call...the static variable will increment by 6 again to become 12.

If my question is not clear, please help me improve it.

which complier are you using? Whether any warning during compilation? I am getting output like this 4199344, 4199344 — 999k
– 999k, Commented Aug 22, 2013 at 11:55
Yes, i lifted the code from a book. Sumdig is declared in Old style K&R format. So return is an implicit int. — kutichatan
– kutichatan, Commented Aug 22, 2013 at 11:56

Devolus · Accepted Answer · 2013-08-22 12:20:16Z

4

The return value is undefined, because only the innermost recursive call returns with a defined value s. All previous calls for sumdig() are returning with an undefined value, because there is no return statement when the sumdig returns without fullfilling the if` clause i.e when it returns from a recursive call.

So it might be, that s is propagated back, if the return value in the register stays unchanged, which may, or may not be the case.

To be safe, the recursive call should be:

return sumdig(n);

answered Aug 22, 2013 at 12:20

Devolus

22.2k15 gold badges70 silver badges122 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Neil Hampton · Accepted Answer · 2013-08-22 11:58:59Z

1

This is very old style C. The return value from a function will be the result of the last evaluation in the function (in this case sumdig()).

answered Aug 22, 2013 at 11:58

Neil Hampton

1,88313 silver badges14 bronze badges

8 Comments

kutichatan Over a year ago

noz, I was thinking along those lines. So i put a the statement 'd = 99;' at the end of sumdig() function. But output is still '6, 12'?

Santhosh Pai Over a year ago

@kutichatan : try to run the program with the help of a debugger , you 'll get the complete trace .

Neil Hampton Over a year ago

Odd - perhaps the d=99 has been optimized out?

kutichatan Over a year ago

Just ran through the debugger, with dissassembly view in eclipse. The d=99 statement seems to be executed.

sepp2k Over a year ago

Even in old style C, the return value of a function was not the result of the last expression. If the end of a function is reached without encountering a return statement and you then try to use the return value of that function, the behavior is and always has been undefined. What is old style though is being allowed to not give return types to the functions.

|

sujin · Accepted Answer · 2013-08-22 12:08:38Z

1

Your question itself has the answer. static variable s updated each recursion when if condition false that time only function return to main. So last updated value of s return to main.

answered Aug 22, 2013 at 12:08

sujin

2,8833 gold badges25 silver badges37 bronze badges

1 Comment

Neil Hampton Over a year ago

Not quite because s is only returned from the bottom level call (when n is 0)

Collectives™ on Stack Overflow

Recursion and return statements in C

3 Answers 3

Comments

8 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

8 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related