Using return in recursion [closed]

StackOverflow https://stackoverflow.com/questions/23431548

  •  14-07-2023
  •  | 
  •  

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!

Was it helpful?

Solution

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.

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top