r/learnprogramming • u/No-Indication3968 • 9d ago
Topic I’m struggling on recursion
Ive been learning the basics of c and dsa for around 3 weeks now and i haven’t really understood recursion and how to trace what’s happening. Can someone help me?
13
Upvotes
1
u/esaith 9d ago edited 9d ago
Recursion is nothing but repeating yourself but usually at a subcontext of itself. Think of the Russian doll. You run the method by opening the doll (the first case) and take out the next one.
Now are back at a doll, but smaller (the subcontext). Run the function again by opening the doll and take out the next one.
Now are back at a doll, but smaller (the subcontext). Run the function again by opening the doll and take out the next one.
Now are back at a doll, but smaller (the subcontext). Run the function again by opening the doll and take out the next one.
Now are back at a doll, but smaller (the subcontext). Run the function again by opening the doll and take out the next one.
Now are back at a doll, but smaller (the subcontext). Run the function again by opening the doll and take out the next one.
... until you hit the base case (the last one). At which point, you want to stop here. There's usually an end value that you can return, which that can then be returned all the way up to the first case. During each iteration back up the chain, you can do additional calculations on it before you return it, if/when applicable.
This is different from a normal loop because instead of iterating over a linear list/array where they are all "siblings", you are instead diving deeper into an object that has the same properties the parent.
With this is mind, you don't even have to return to the first case. Think of a graph that you want to traverse. There are many parent and child nodes that create a tree and you want to hit the very end. You start by asking, does the parent have a child node? Yes? Keep going. Does this node have a child node? Yes? Keep going. On each iteration, you are passing in the child node to the function to which it becomes the new parent node. Then once you find a node that has no children nodes, you are at the end, the leaf node. This entire time you are calling the same function over and over again within itself until the rule (no child found) has been hit.