[HELP] Can't understand recursion
Posted by SprinklesWise9857@reddit | learnprogramming | View on Reddit | 10 comments
I'm currently taking my uni's DSA course and we're currently on recursion. The professor spent no more than 20-30 mins on it and moved on, and our current project that's due soon is all about recursion. I can read recursive code, and I can trace through it, but I can't come up with recursive code on my own if I were to be given/assigned a problem that required recursion. It feels like I have to think "backwards" because of the call stack, and my brain is not used to thinking that way, so I've been unable to do that. I can't even code up a recursive factorial, which is arguably one of the easiest recursion problems. Any advice/help would be greatly appreciated.
It sucks because I spent a really long time during the summer studying and working with pointers because I struggled on those too, and eventually, it finally clicked for me and I fully understand pointers now. It felt like I broke through a barrier, and I wasn't expecting to run into anymore for a while--especially since I self-studied a bit of DSA over the summer as well. But now, I'm struggling majorly on recursion.
Sbsbg@reddit
There is a trick I use when creating recursive functions. You have to trick yourself that you already have a working function. First focus on what the function does and ignore how it does it. Then think on how you can extend what the function does using the same function.
Some examples
Factorial. You have a function f(x) that already calculates factorial. How do I extend it to x+1 using itself. If I take x-1 and call f on that and then multiply by x i extend it.
Reversing a list. You have a function f(x) that takes a list x and reverse it. How do I use this to reverse a slightly larger list. Well if I split the list in one item and a smaller list and use f to reverse the smaller list and finally stick the item in the other end.
Traversing and printing a tree. You have a function f(x) that prints a tree. How do I use it to print a tree node. Print the left branch f(x.left), print the node data and finally print the right branch.
That's it. Then you only have to solve the smallest end solution, add a test to use the end solution or the recursive solution and you are done.
HashDefTrueFalse@reddit
If you know how the stack works and how new stack frames are pushed/popped for each function call/return, you can picture how recursion works. It's basically just a new stack frame being pushed for each new invocation of the same function with different parameter values, until a terminating case stops the new calls. At which point there is a chain of returns as the stack unwinds. Whether the important bit of work/computation happens before or after the recursive call inside the function will determine whether the work is done on the build up of the stack or the unwinding of the stack. Not much more to it.
There's a pretty famous old book called Structure and Interpretation of Computer Programs that builds lots of recursive procedures. It would probably help you. From memory, the bits in chapter 2 on writing procedures that recursively visit and transform lists is quite good.
It might help you to do some simple tree walking. Define a (left, data, right) structure using whatever language+construct you like, and try to write a function that walks it and prints the data at each node. Maybe post it back here if you're struggling so people can help.
RecentlyRezzed@reddit
SICP can be downloaded from the MIT.
grantrules@reddit
How far did you get into DSA? Binary Search Trees are a pretty common pattern in DSA, and they use recursion.. maybe take a look into that? I think it's a more practical application than something like factorials so maybe give that a look?
SprinklesWise9857@reddit (OP)
Outside of the course I'm taking at my uni, I self-studied big O, linked lists, stacks & queues, and finished off with only a bit of binary search trees. I was just about to get into recursion, but I decided against it because by that time, I had already started school. I was only self-studying because I had nothing to do during the summer and I knew I'd thank myself later for it. I'll take a look at recursive BST now that you mention it's more practical, thanks.
ungemutlich@reddit
Mathematical induction is very closely related and might be another angle for understanding it:
https://en.wikipedia.org/wiki/Mathematical_induction
Start by defining the dead simple base cases. If a tree node is null, the height is 0. If the root of a tree has no left or right children, its height is 1.
Then a recursive step moves you towards a base case (like the condition for terminating a loop). The height of a node with children is 1 + the height of the children. The process will continue down the tree until reaching a leaf, and then the whole thing will unwind, adding 1 for each level.
These are the lectures to go with the SICP book mentioned earlier. Everything is done with recursion until well into the course:
https://www.youtube.com/watch?v=-J_xL4IGhJA
No_Indication_1238@reddit
Express each recursive function through a mathematical function. n1 = n0 + 1, n2 = n1 + 1 etc. That made it easy for me. Second thing is, watch the turtle paint branches of a recursive tree. It clicked for me at this point. Each recursive function can be expressed by a loop so a recursion is basically a loop with a break condition (if something, return).
wiriux@reddit
Recursion is indeed hard. This is one of those where shortcuts or “memorization” won’t cut it. You need to understand how things are stored in the activation record and how the tree or records of is being built with each call.
Have you looked into recurrence relations yet or have you not taken analysis of algorithms yet?
You just have to be extra patient with recursion and analyze and understand the baby programs. Once you understand the basics then it gets easier. Work with a debugger or piece of paper so that you can see what is being called and what is the value when stack starts being popped.
I don’t have any advice on this. This is just something you need to seat down with paper and trace it or a debugger if you don’t want to use paper. Regardless, keep going through the fundamentals until it clicks. If you don’t understand your professor there’s ton of resources online where you can learn from.
Accurate_Tension_502@reddit
That’s the problem with incursion. It insists upon itself.
AutoModerator@reddit
To all following commenters: please, do not bring up the old circlejerk jokes/memes about recursion ("Understanding recursion...", "This is recursion...", etc.). We've all heard them n+2 too many times.
I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.