Using return in recursion

Question

public static int Mystery(int a,int b)
{
    if (b == 0)
        return 0;
    if (b % 2 == 0) 
    { 
        return Mystery(a + a, b / 2); 
    }
    else
    {
        return Mystery(a + a, b / 2) + a;
    }
}

Hello guys can you please tell me what's the difference between using a return Mystery(a +a ...etc) and calling it simply by using Mystery(a + a)? What I have been thinking till now is that when I use return something it actually creates a way back for the recursion to come back and using recursion without return (ex.Mystery( a + a etc..)) goes only in depth without actually leaving any path to go back. Thanks!

The function is supposed to return an int, if you don't return an int it's a compile error... — Kevin DiTraglia, May 02 '14 at 15:22
If you just have a recursive function call, when the call returns it will continue execution at the next line. When you use `return` with a function call, you often *add* something to *accumulate* a result and return that immediately. — crashmstr, May 02 '14 at 15:22
Well I could juts write return 0 in the end ?! Why should I write return on the recursive call,this is what my question is,it is not about the function that I posted itself. — Hristo Hristov, May 02 '14 at 15:23
you would return if you want the accumulation of all the recursive calls. otherwise why have a recursive call unless it is going to manipulate a class level variable. — Delta, May 02 '14 at 15:24
@Bart Thank you that was what I was trying to get it && crashmstr thanks guys! — Hristo Hristov, May 02 '14 at 15:24

score 1 · Accepted Answer · edited May 23 '17 at 10:32

If you don’t return the value from the recursive call, there is no way for you to accumulate the results from all calls. E.g., you are doing Mystery(…) + a, so if Mystery didn’t return a value there, you would be adding a to nothing (and not return that either).

Of course you could also do the recursive call first, save that value and return it later:

int value = Mystery(a + a, b / 2);
// …
return value + a;

The point is that each recursive call needs to return a value which is processed by the parent call, so that you actually utilize the calls.

And finally, you usually would want to have the recursive call on a return because there are languages that can remove tail recursion. C# doesn’t do that though.

Using return in recursion

1 Answers1