Menu
Jump to content

What's with the ads?

Archived

This topic is now archived and is closed to further replies.

daijobu

Computer Science peeps: I hate recursion. I do I do I do

Recommended Posts

I've got a huge mind block when it comes to recursion.  I like to trace my programs, but I just get stuck and confused.  I trace the results of a recursively called function, and I forget where I came from.  If that makes any sense.  

 

What am I missing?  I want to see the light!  Help me see the light.  

 

And anyone who says, "To understand recursion you must understand recursion."  is asking for it.  

 

 

Share this post


Link to post
Share on other sites

I'm not sure I can help but am willing to try. :)  Are you having trouble understanding recursion in general or figuring out how to code a recursive function and verify it's doing what you'd expect? If it's the latter then what I typically do when I'm trying to verify complicated code is actual walk through it on paper with sample values. It's similar to tracing but I find it easier to keep track and think through everything for some reason. Sometimes I talk out loud as I'm doing that too - lol. 

 

For a recursive function it might be helpful if you try walking through it on paper to indent each time you go through the function and then once you've hit the "end" (where there are no more recursive calls) unindent back out. 

 

I just did some searching to see if there were any good examples online and this is helpful: https://www.cs.umd.edu/class/fall2002/cmsc214/Tutorial/trace-recursion.html

 

Also, in case it makes you feel better, I've never used recursion outside of school. There are only certain types of problems where it's necessary, helpful, or more efficient. In my experience those don't come up often.

 

Good luck!

Share this post


Link to post
Share on other sites

Yes, recursive functions are a pain to trace. Is it an option for you to print the current value of the node in your method? I find it easier to look at the printed values to see where the program walked, than to trace call-by-call.

Share this post


Link to post
Share on other sites

I haven't done as much coding since I switched from CS to math several years ago, but I used to use a combination of using well-chosen sample values, as a previous poster mentioned, to see if I could determine whether each block of code was doing what I wanted it to do, and commenting out all but one block at a time to test each block independently. Once I knew each block worked independently, I could start un-commenting one more block at a time, and testing to see whether each block worked with what had already been tested.

Share this post


Link to post
Share on other sites

I love working things out visually, and find that many people who are struggling with complex code, method calls or call stacks are simply having trouble detangling the sequence in their heads. So work the sequence out physically. I like using either a whiteboard or wood blocks. Each function/method should have its own unique shape and/or colour. As mentioned above, walk through it with simple values. Or even walk through it with your real inputs. Unrolling your recursive calls into a sequence of sequential (hehe) calls to the same method ("oh look! three red squares one after the other") and seeing the inputs and outputs change can help give feel to what's going on.

 

Recursion is a beautiful shorthand. But it is pretty specialised and rare. In the real world, not a lot of people work with recursion with any regularity.

Share this post


Link to post
Share on other sites

Mmmm.  Recursion is one of the things I liked most in programming.  To me there's just something cool about creating something that spawns off another and another until the work is done.  

 

My graduate work was in theoretical computer science and my dissertation topic involved a lot of recursive functions and data structures.

 

It does depend on what sort of programming you're doing, but certain areas of programming do use it quite a bit.  These days I teach primarily applications and a little web design, so no recursion in my college classes.

 

Here's a YouTube that might help: https://www.youtube.com/watch?v=72hal4Cp_2I.

 

 

Share this post


Link to post
Share on other sites

To trace a recursive loop, if that is what you are asking, just initialize a local variable and increment it every time the loop runs. Put your break point on that local variable and then, you can walk through every recursion.

 

e.g. pseudocode ... (hope this helps)

 

function recursive_worker()

{

#ifdebug

  static int zcounter = 0;

#endif    

  result  = do_something();

   if(result != NULL or MYANSWER)

  {

     recursive_worker();

     #ifdebug

        zcounter++;

        print_debug("running recursive function for the %s time", zcounter)

     #endif

  } 

  else

return

}

Share this post


Link to post
Share on other sites

I'm not sure I can help but am willing to try. :)  Are you having trouble understanding recursion in general or figuring out how to code a recursive function and verify it's doing what you'd expect? If it's the latter then what I typically do when I'm trying to verify complicated code is actual walk through it on paper with sample values. It's similar to tracing but I find it easier to keep track and think through everything for some reason. Sometimes I talk out loud as I'm doing that too - lol. 

 

For a recursive function it might be helpful if you try walking through it on paper to indent each time you go through the function and then once you've hit the "end" (where there are no more recursive calls) unindent back out. 

 

I just did some searching to see if there were any good examples online and this is helpful: https://www.cs.umd.edu/class/fall2002/cmsc214/Tutorial/trace-recursion.html

 

Also, in case it makes you feel better, I've never used recursion outside of school. There are only certain types of problems where it's necessary, helpful, or more efficient. In my experience those don't come up often.

 

Good luck!

 

Yes, tracing is difficult for me.  And while I can seem to set up the base case, I have trouble figuring out what to do when I return something from a recursive call.  

 

But I've printed out that link you provided and will read it tonight,  Thanks!

Share this post


Link to post
Share on other sites

I love working things out visually, and find that many people who are struggling with complex code, method calls or call stacks are simply having trouble detangling the sequence in their heads. So work the sequence out physically. I like using either a whiteboard or wood blocks. 

 

I think this is what I need, more visual references.  I will try tracing on paper, then when I'm returning something I forget where it gets returned to!  And then I need to do something with that return value and continue with the program.  I'm to try to throw in a little more patience into my approach.

 

Thank you everyone for your help! 

Share this post


Link to post
Share on other sites

This is my favorite part of programming, although I admit when I was first learning how to use it my husband had to help me follow what was happening. I wish I'd taken a picture of the diagram he drew on the whiteboard, because it made the whole thing make sense.

Share this post


Link to post
Share on other sites

 

 

I just did some searching to see if there were any good examples online and this is helpful: https://www.cs.umd.edu/class/fall2002/cmsc214/Tutorial/trace-recursion.html

 

 

Good luck!

 

This I think is just what I needed.  Something to keep track of my return values and put them into the proper level of recursion.  I needed an algorithm to check my algorithm!

Share this post


Link to post
Share on other sites

×
×
  • Create New...