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

  1. #1
    Registered User
    Join Date
    Sep 2011
    Posts
    71

    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?
    Last edited by y99q; 09-30-2011 at 08:43 PM.

  2. #2
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,229
    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.

  3. #3
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Ireland
    Posts
    8,446
    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...
    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. In over my head
    By Shelnutt2 in forum C Programming
    Replies: 1
    Last Post: 07-08-2008, 06:54 PM
  2. X11 head to i2c bus
    By maes in forum Linux Programming
    Replies: 0
    Last Post: 07-25-2007, 05:28 AM
  3. K&R is doing my head in!
    By Unregistered in forum C Programming
    Replies: 10
    Last Post: 03-06-2002, 10:32 PM
  4. Head Nod...
    By Cheeze-It in forum A Brief History of Cprogramming.com
    Replies: 3
    Last Post: 02-16-2002, 12:58 PM
  5. file pointers + recursion = sore head
    By korbitz in forum C Programming
    Replies: 4
    Last Post: 12-18-2001, 05:55 PM