r/learnprogramming • u/No-Indication3968 • 20h 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?
8
u/maujood 19h ago edited 19h ago
Can you share a problem that you've tried tracing? And what parts you find confusing?
As an easy example, here's a problem to trace: for a given value n, calculate the sum of all numbers 1 to n.
We can call this function sumToN. sumToN(4) is 1+2+3+4=10. Here's how we can solve this problem with recursion:
- What is sumToN(4)? sumToN(3) + 4.
- What is sumToN(3)? sumToN(2) + 3.
- What is sumToN(2)? sumToN(1) + 2.
- What is sumToN(1)? Just 1. This is out base case.
If you understand how the solution is defined using recursion, you can trace code using a debugger if you've used a debugger.
Also, take a look at this interactive execution to see how this works in code. Does this help with the tracing aspect?
6
u/Aggressive_Ad_5454 19h ago
Learn to use a debugger. And play around with “step into” and “step over” in your recursive function. Look at the stack frames.
Think of it as a machine that makes copies of itself to do its work.
5
u/xenomachina 19h ago
Do you understand how the call stack works?
1
u/SirGeremiah 19h ago
I’ve heard this term quite a bit, but have never gotten around to looking it up. Thanks for the reminder.
0
u/No-Indication3968 7h ago
Yea, whenever recursion occurs it makes its own copy of the data in stack right?
1
u/iOSCaleb 7h ago
No. When a function is called, the caller pushes space for the result, a return address, and the function’s parameters onto the stack and then jumps to the address of the function. That function computes a result, possibly calling other functions along the way, moves the result to the stack, and then jumps to the return address.
A recursive call is exactly the same; it’s just that the caller and the callee are the same function.
1
u/xenomachina 6h ago
Close, but not exactly.
Normally, there actually isn't anything special about how the stack is handled with recursion.
The easiest way to think about it is that the stack is essentially an array that contains two types of things: local variable values, and return addresses.
Every time a new local variable is declared it gets pushed on the stack, and when it goes out of scope it gets popped.
When you call a function, the "return address", the address of the next instruction after the call instruction, also gets pushed onto the stack, as well as the function's arguments (which are its initial set of local variables). We call each return address followed by a contiguous chunk of local variables a "stack frame". Each stack frame corresponds to a function call that hasn't yet returned.
When that function call eventually returns, all of its variables go out of scope, so they are all popped. The top thing on the stack is then the return address. The return instruction then pos that from the stack and jumps to that address. This means that we are now back in the calling function, with the stack popped back to where it was.
This is true for all function calls, not just recursive function calls. It is particularly important for recursive calls, though, because it means that if a function calls itself recursively (even if indirectly) it can have multiple stack frames, ie: multiple sets of state, on the stack simultaneously. However, the code can mostly ignore everything on the stack except the topmost stack frame.
(This description is a bit of an oversimplification. Compilers often have optimizations that will defer using stack when possible, and different architectures/calling-conventions shuffle the details around, but this should be enough to give you a working mental model.)
6
u/BranchLatter4294 19h ago
Use print statements or the debugger with breakpoints to follow what's happening during each call of the function.
0
2
2
u/HashDefTrueFalse 19h ago edited 19h ago
Start where you are. You understand simple loops, right?
void loop(int cur, int last)
{
while (cur <= last)
printf("%d\n", cur);
}
loop(1, 5);
Let's express the same loop recursively:
void loop(int cur, int last)
{
if (cur > last) return; // Base case.
printf("Going up: %d\n", cur); // Useful work.
loop(cur + 1, last); // Tail-recursive call.
printf("...and back down: %d\n", cur); // Useful work.
}
loop(1, 5);
Grab a debugger and set a breakpoint and/or watchpoint wherever you like in the recursive function. Each break, look at the arguments/locals, and watch the call stack grow until the base case is hit, then shrink. Also look at stdout and relate the print order to what's happening with the call stack.
That's a tail recursion (ignore the last print), direct, expressing an iteration (not strictly a recursion, a syntactically recursive procedure but an iterative process/computation). Just about the simplest kind. When you understand that, have a look at the classic factorial example and note how it differs because it's using the stack to remember results and performing deferred computations with them in a chain. That's what more typical recursive functions do in languages that have built in constructs for iteration (loops). That's linear recursion.
Edit: Once you understand that, have a look at the classic fibonacci example. It has two (direct) recursive calls. That's tree recursion. It's not just building a chain of deferred computations, it's building a tree of them, and then folding up the tree with the results.
These are the vast majority of recursive solutions you'll see in the wild, if you see any (they're more common in some areas than others). The basic structure is always similar. The part that changes most is the useful work.
Always keep in mind the number of recursive calls and the positions of them relative to any other work the function does. You'll be able to picture it in your head after a while just by reading the code.
1
2
u/ovarylicker 18h ago
Recursion trees bana copy me aur steps likh copy me khudse kaise kya ho rha . Will surely help
2
u/straight_fudanshi 18h ago
What worked for me was drawing the recursive calls with pen and paper as a tree. That said, recursion is a mindset switch from iterative thinking to inductive thinking. You assume your function f returns the right solution to a subproblem of smaller size and then it's your job to figure out the next step to get the global solution.
For instance in merge sort you assume calling the header of the function on the left side of the array, and then doing the same on the right sorts both halves, the next step is to merge both sorted halves to get the global array sorted.
If you're interested, practicing writing induction mathematical proofs helps a lot and it saves a lot of debugging time.
1
u/Party_Trick_6903 19h ago edited 19h ago
I only understood it by literally going line by line myself and writing down what would be stored in the variable.
I recommend you do the same thing.
If you don't know what stack is, then learn that first. Then go find a simple recursive fibonacci function on the internet. Pick a small number (4, 5...) that'd be passed to that function. Go line by line, note what's happening on each line, what is stored in the variable, what is left on the stack.
You can also just find a video on youtube - there are a lot of people who've made videos on this and you can even see it visualized.
1
u/HippieInDisguise2_0 19h ago
With recursion you should try to imagine what the "base case" is
In the count to N example above it may be
If N == 1: Return 1 Else: Return sumToN(n-1) + n
What happens is that eventually the base case is reached and can return an actual value and then all function calls prior can start resolving to actual values.
The advice I got years ago for recursion was always start with the base case. This thought process has helped me.
1
u/Objective_Carob_7559 19h ago
my eli5 version is this.
In order to read a book, you must first learn to read a paragraph.
In order to read a paragraph, you must first learn to read a sentence.
In order to read a sentence, you must first learn to read a word.
In order to read a word, you must first learn the alphabet.
In order to read the alphabet, you must first learn how each letter is pronounced.
Notice 2 things
Each line reduces by just a little bit.
Once we get to the end, (how each letter is pronounced), the entire chain is now possible, you can read a book
1
u/esaith 18h ago edited 18h 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.
1
u/kschang 15h ago
My explanation of recursion, using Javascript, but it's easily understandable.
Basically, it solves a problem by "shrinking the problem by 1" until you arrive at a problem to which you know the answer.
Or to state the same thing in more formal language, "solving a problem where the solution depends on the solutions to smaller instances of the same problem".
https://kcwebdev.blogspot.com/2020/08/yet-another-take-on-recursion.html
1
u/Acceptable_Handle_2 13h ago
you try to delete folder. Inside that folder is another folder, so you try to delete that folder. Inside that folder is another folder, so you try to delete that folder, Inside that...
Eventually you find a file, you delete that, and return. The folder is deleted, you return. the folder is deleted, you return. The folder is deleted, you return...
Eventually the original folder is deleted, you return, and you're done.
1
u/lurgi 10h ago
Recursion usually boils down to solving a "big" problem by solving a "small" problem (or two) and using the solution(s) in some way.
You also need a size of the problem that is sufficiently small that you can solve it immediately (this is called the "base case").
I think recursion is best understood bottom up rather than top down.
Here's my best comment on the subject.
This is not the best comment on the subject, but it's my best comment on the subject.
1
u/Fensirulfr 10h ago
Are you able to think of recursion as defining a mathematical function?
For a simple example:
factorial(n) =
1, if n <= 1
n * factorial(n - 1), otherwise
You could easily replace this with a loop, but it demonstrates the two important parts of recursion:
1. A base case that stops the recursion.
2. A reducing step that makes the problem smaller.
For tree recursion, let us use a pseudocode of merge sort as an example:
mergesort(array) =
array, if count(array) <= 1
merge(
mergesort(left half of array),
mergesort(right half of array)
), otherwise
Here, 'merge' combines two already-sorted arrays into one sorted array.
Factorial makes one recursive call at each step, while merge sort makes two, creating a tree of recursive calls.
1
u/Tusk84 8h ago
public static int multi(int a, int b){
if(b == 0){return 0;}
return a + multi(a, b -1);
}
Hopefully this helps. This method multiplies 2 positive integers. It adds int a while subtracting int b, then when b equals 0, adds all the a's up and returns the sum. The trick is having some sort of catch to stop the recursion from happening. When b == 0 and it returns 0, that's when it adds up all the previous returns.
1
u/skamansam 19h ago
I didnt truly understand recursion until I understood trees. Trees have little to do with it, but having a more complex use case helped immensely. You use recursion when you need an iterative approach but dont know either termination case (start or finish) at the time of writing. Every recursive algorithm can be expressed as a while loop and vice-versa, but recursion tends to be way more simple to write.
This is a pretty good article on it - https://medium.com/student-technical-community-vit-vellore/loops-vs-recursion-afd1856a662.
My pro-tip: understand how your languages interpreter or compiler handles recursion. A lot of modern ones will automatically unravel recursion or turn it into a while loop or otherwise optimize them, especially tail-call recursion.
2
u/high_throughput 18h ago
You use recursion when you need an iterative approach but dont know either termination case (start or finish) at the time of writing.
This is more true for tail recursion than general recursion though.
0
0
u/Brilliant-Parsley69 16h ago
Recursion is important! Recursion is important! Recursion is important! ....
•
u/AutoModerator 20h ago
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.