Can you do Recursion in your head? if so, how do you do it?

• 09-30-2011
y99q
Can you do Recursion in your head? if so, how do you do it?
Code:

```        static void P(int x)         {             if (x > 0)             {                 Console.WriteLine(":" + x);                 P(--x);             }             if (x > 0)             {                 Console.WriteLine("::" + x);                 P(--x);             }             Console.WriteLine(":::" + x);         }         static void Main(string[] args)         {             P(3);             Console.ReadKey();         }```
Above you will see some code I was contemplating today while I was driving on the highway. I was able to predict the first 6 lines of output

Code:

```:3 :2 :1 :::0 :::0 ::1```
but after the 6th line I came up with a bunch of nonsense because I reached a point where I couldn't mentally hold the flow of the algorithm.

If you look at the above code, are you able to mentally correctly come up with the entire output?

If so, how do you do it? Do you picture like a spiral around each recursive call?
• 09-30-2011
cyberfish
Usually recursive code is not that complex. The way to understand recursive code is to think about it recursively. Basically, when you are writing the function, you need to assume that the function is already working properly, so you can use it to solve (usually) sub-problems. Then, make sure your base case will always be reached.

When I trace recursive functions, I do it just like computers. I set up a call stack in my head, with context for each call. If I reach a point I can't do it anymore, I write it down.
• 10-01-2011
Mario F.
A little aside: You could probably have predicted the entire output, were you not driving.

To add to what cyberfish said, a recursive function will usually present itself as a solution to your problem in a more benign environment. That is, you are in full control of the problem invariants and the recursive solution just comes more naturally to you. The reason you couldn't predict the result of your function has no doubt a bit to do with the fact you were engaged in another high-concentration activity. But this difficulty was also raised by the fact there was no actual problem involved. No invariants either, which help limit the complexity of the problems we try to solve and maintain us focused on the important details. You were simply creating a recursive function from the bottom up. Instead we tend to create recursive functions from a bird's eye view down, and apply assertions and let the computer do the trace for us if we need it debugged. There's no actual requirement for a programming to be able to mentally follow a recursive function path beyond what's reasonably expected.

That said... as a pure mental exercise I don't think we can follow recuursive functions for very long if they don't exhibit a pattern at some point. It's not something our brains are very good at. But with training, who knows...