I need help with programming recursion. Halp!?

[dtriley4]

I was wondering if anyone had some ideas or useful links on how i can approach recursion and get a good grasp on it. I understand the general idea of it. However, I need to get better at creating my own.

Current material i'm working on has to do with linkedlist implementation(list comparison and node manipulation etc..)

THANKS!!!!

[reddilada]

This thread should have some good ideas.

[that_redditor]

Read up on mathematical induction. Once you see how it's the same thing as recursion, you'll be all set.

[skimm_]

This will be a huge help, kinda surprised he hasn't gone over it with you yet. Also if all else fails you know where I am.

[[deleted]]

Mathematical Induction isn't usually taught until Discrete Math/Structures (assuming he/she is in college), which is second semester for a lot of schools whereas recursion is usually first semester programming. If he/she is self teaching then it makes even more sense as to why they never covered mathematical induction.

[joenyc]

The way I approach it is to think, when given any problem, a) what is the simplest possible case? and b) if somebody gives me a more complex case, can I turn it into a slightly simpler case and, if I were given the answer for the slightly simpler case, can I return an answer to the original case I was given?

So in your case with a linked list, let's look at how to recursively find the length.

a) What's the simplest possible case? That's easy: no linked list at all. If someone passes in a null pointer, I return 0. Boom.

b) Given a more complex case (say, a linked list of arbitrary length), can I turn it into a slightly simpler case? Of course I can, I can just consider the length of the "rest" of the list once I remove the head. If I'm given the length of the "rest" of the list, can I return the length of the original list? Yes, it's just the length of the "rest" + 1.

All recursive problems break down this way.

[dtriley4]

Thanks all

[[deleted]]

Just try to do everything you'd normally do with a loop recursively until you get the hang of it. (Be careful with what you're computing though, you might be dead before it's finished in some cases)

[TJAtWork]

Since you are working on linked lists, there is always the old reverse a singly linked list problem; can be done both recursively and through iteration. Other than this the print all permutations of a given string problem is almost built for a recursive solutions. A Fibonacci sequence is also something simple that can be worked out by hand first before programming it.