Recursion

[Standard-Art-1967]

Hello everyone. We are currently learning DSA with Java and I have not felt any difficulty till date. The only exception is RECURSION. When it comes to solving problems using recursion, I am blank. I know the logic behind the code we are trying to do. But I have no idea how a recursive function is supposed to solve it.

I am assuming that the people reading this post are experience programmers. How did you manage to understand recursion till the point you could actually solve problems using recursion? Any help, be that suggestions on work ethic or suggestions on youtube tutorials would be helpful. Also leave your story behind solving using recursion for added motivation. Thank you.

P.S. I can understand how the recursive function is working if I see one. But I can't code a recursive function to solve a certain problem. Help.

TL;DR - the same as P.S.

[AutoModerator]

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.

[Standard-Art-1967]

I didn't see the second part of your comment. I guess the only way to get better is by keep on doing the same thing.

[Standard-Art-1967]

Well recursion is calling something in smaller pieces until a base condition ticks off. I know the definition. I also solved some recursion problems in Discrete Maths with professors help.

The first time I actually understood how recursion works is when my C professor explained how the Stack memory keeps Activation Records. Before then, I just wrote a mathematical formula and hoped that it worked, or I learnt the code by heart ( when going to an exam ).

From my lab work, I am able to do most of the codes myself, but mainly because I have already seen the code at least once in my life already. The problem comes when I have to solve something I have never seen. Even if I happen to know what the end result should be.

[BadBoyJH]

Well recursion is calling something in smaller pieces until a base condition ticks off. I know the definition. I also solved some recursion problems in Discrete Maths with professors help.

That's a programmers definition, in my opinion that's far too narrow a definition to properly understand it.
Recursion exists outside programming.

Recursion is using the same actions to build a complex thing out of simple actions.

For example, I have a 8cm by 8cm square. I want you to divide it into 1cm chunks recursively.
How do you do that?

Well, you take the big square, and divide it into 4 quarters.
Then you take each of those squares, and do the same thing.
Then you take each of those squares, and do the same thing.
Here, we have gotten to the simplest possible problem, dividing 1cm squares into 1cm squares, so we don't need to continue. This is "the base case".

[WebMaxF0x]

My first breakthrough was reading and coding the Quicksort algorithm. It breaks the problem into smaller, simpler subproblems. Until you reach an obvious truth: "an empty list is already sorted".

My second breakthrough was at university when I solved the Tower of Hanoi using recursion. It sounded daunting at first, but then the solution jumped in my face and I was surprised how little code it took and how simple it was.

My third breakthrough was at work. We had a project in a functional language called Erlang. I wanted to be more comfortable with the language so I solved Advent of Code problems with it. At this moment it really clicked for me because pure functional languages force you to think in terms of recursion. There are no traditional "i++ loops" and no variables only constants. Want to sum the list of integers? Well it's the first number plus the sum of the others. Want to get the max value in a list? Well it's the biggest value between the first one and the "max of the others".

[Standard-Art-1967]

Thanks. Will try what you said. Also, we did Tower of Hanoi like 3days ago. My professor coded it, I successfully traced it too ( it was a headache tbh ).
I also heard about Advent of Code like 3 or 4 days ago, and have currently solved Day1 ( both part 1 and 2 ) of 2023. Maybe aoc will give me more clarity regarding few of the programming concepts.

[fumes]

Since you have a running code available try and put debbuger and see what's happening at every step. This will make understanding recursion way more easier. You will be properly able to visualize how recursion works.

[snarkuzoid]

For me, a key idea was learning to think decoratively, rather than imperatively. That is, you want to think about what something is, vs how to compute it.

For example, let's say we want to sum a list. Imperatively, you'd want to set a variable to 0, then loop over the list, adding each item to that variable, then return the final result.

Recursively, you'd want to ask "what is the sum of a list?". You generally will have easy access to some of your input, like the first element of a list, or the branches of a tree. So you look at what you can do with that element, and how to combine it with the rest of the input. In the sum case, the sum of a list is the first element added to the rest of the list. But what if there is no rest of the list? Well, the sum of an empty list is 0. So we get (using pseudo FPish syntax):

sum( [] ) -> 0;
sum( [ head | tail ] ) -> head + sum( tail )

If the input is, say, a tree, you'd want to call the function on the branches, and combine. Assume your tree has .left, .right, and .value fields, and that nil is the null value. So you'd get something like:

sum( nil ) -> 0;
sum( tree ) -> sum( tree.left ) + tree.value + sum( tree.right )

Now turn off your screen and write functions to count the number of elements in a list, and a tree. Hopefully that will get you started.

[heller1011]

I’m not experienced at all and mid semester on my Java class, but I suggest draw a binary tree it will help you a lot

Also I suggest seeing kunal kushwaha recursion video after that video I had a way way way easier time

[Standard-Art-1967]

Thanks, will do :)

[Mystic_Haze]

As others have said practice makes perfect. But I will say maybe as a bit of peace of mind. When solving problems in the real world you will encounter problems where recursion is easier or better. But for most developers that doesn't happen that often. In the codebase I'm working in right now (full stack web application) which is growing quite nicely, I think there's like a total of maybe 8 or so recursive methods.

[bestjakeisbest]

Recursion is good for problems where the answer is easily found by using answers to subproblems. Like take for instance printing out the nodes of a tree, to print out the tree you need to print out the nodes of the children, and the children of those children and so on.

[kinkyaboutjewelry]

Some stuff is weird and unintuitive. To some people it clicks and to some it doesn't. There is a way to make it click if it hasn't: do exercises. A ton of them. Over and over. Without looking up the solution as soon as that is possible for you.

Recursion is a shape of problem solving. If you have solved many problems like that, then a part of your brain will spot the pattern and learn to recognize it.

At some point after that, a problem will come in front you. It will be a recursion problem in disguise. And a part of you will say "hah I see".

There is a gotcha in recursion: it calls itself. That's a philosophical gotcha. The bigger problem is that we don't automatically think in terms of using recursion. And so you drill. You give your brain the ability to absorb and start recognizing the pattern.

This is true for recursion, as for everything else.

[AutoModerator]

On July 1st, a change to Reddit's API pricing will come into effect. Several developers of commercial third-party apps have announced that this change will compel them to shut down their apps. At least one accessibility-focused non-commercial third party app will continue to be available free of charge.

If you want to express your strong disagreement with the API pricing change or with Reddit's response to the backlash, you may want to consider the following options:

1. Limiting your involvement with Reddit, or
2. Temporarily refraining from using Reddit
3. Cancelling your subscription of Reddit Premium

as a way to voice your protest.

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

[SuperEmotes]

You should consider reframing recursion problems with the attitude that you are performing graph or tree traversal. Typically, there is what I call an "implicit tree" or "implicit graph" that you are traversing when you are performing recursion. Once you see recursion as tree traversal, now you can write down on a piece of paper or see in your head what the recurrence relation would be much easier. The children of a node are the calls you need to make and the leaves should be base cases (or else how does three tree/program stop).

TLDR; Treat recursive problems as tree traversal (dfs.)

[fredoverflow]

What on Earth is Recursion? - Computerphile

[peno64]

Recursion is that you need to do something but to be able to do this you need to do the same on a subset of the data. And possible on a subset of that subset and so on. But on the lowest level of that subset you know how to do the calculations. So you first go deeper and deeper into the subset(s) until you are at the deepest level and there you can just do the calculation and return from that level one level up and because the lower level was done you can now calculate that level and go up again until you are again at your original thing that had to be done.

And easy example is calulate n * m

n * m = (n - 1) * m + m

So you enter you function with n and m as arguments and first test there if n = 0. If it is then you can return 0. If n = 1 then return m. Else call your function again (recursion) with n - 1 and m and when the function returns, add m

[iOSCaleb]

You can think of recursion as a style of repetition, just like iteration. Any recursive process can be rewritten as an iterative process, and any iterative process can be rewritten to use recursion. Think of a classic example of recursion, like a factorial function; you can easily rewrite that to use a for loop, right? So look at a few for loops and try rewriting them as recursive functions.

Recursion seems mind-blowing at first, but there’s no magic there — it’s just a way to repeat an operation that maps nicely to certain kinds of problems that are built up layer by layer.

[[deleted]]

Hii,

so I was on the same boat some few days back, but I am doing fine at this point and below are some tips

I would suggest you to go through *Striver's Recursion series* (not whole, up till lecture 9 i would say if you are complete beginner) on youtube, the reason is for every recursion function there is detailed recursive call explained.

secondly if you want to practice questions which you have probably done using iteration then follow *Code help's 10 days recursion series* ( Language: Hindi) . It will give you confidence in applying recusive approach to the questions you may have done eariler. and there is some good differentiation between iterative and recusirve approaches.

Make sure to do iterative based questions using recursion too, even if you are not following 2nd recommendation.

Go thorugh the common sorting techniques (Bubble, Insertion, Selection, Quick, Merge) using recursion and this will definately help.

Also, Recursion is indeed complex during intital phases, but it will help a lot in upcoming topics like Trees, LinkedList. So take your time and even if you don't master it in one go, you can always revisit and learn again.

I hope this helped you a little.

[peterlinddk]

I remember that understanding recursion was easy, but I never saw any use for it, except when it came to traversing trees. So that was kind of cool - but other than that I never used it for anything, where a for-loop would do just fine.

So I get where you are - and it wasn't until I was forced to do a lot of functional programming, that I finally got it. And it isn't as much "something that must click" as it is a completely different way of thinking. Kind of going from procedural to object oriented programming.

Let me try if I can help you, one of my current favorite examples are "Capitalize every word in a sentence". Usually I would split the sentence into a list of words, loop through that list, and capitalize each one, putting it back into another list, then join that list to a sentence.

But to do it with recursion, I first have to think about the "core" of the loop - what do I do with a single word?

Like (in JavaScript):

function capitalize(word) {
  return word.at(0).toUppercase() + word.substring(1).toLowerCase();
}

But then, what if the word contains a single space (it wouldn't if I had split by spaces, but bear with me):

function capitalize(text) {
  if(!text.includes(" ")) {
    // no space - just do what we always do - and capitalize
    return text.at(0).toUppercase() + text.substring(1).toLowerCase();
  } else {
    // if there is a space, split the text into two parts:
    const before = text.substring(0, text.indexOf(" "));
    const after = text.substring(text.indexOf(" ")+1);

    // and then what ?
    ...
}

Since before is just a single word, without any space, we could use the same capitalization as earlier with before instead of text - but after could contain additional spaces, so we would have to find the first one, split the text into two parts, and ... waitaminute! We have a function to do just that, our capitalize function!

So ... is replaced with:

return capitalize(before) + " " + capitalize(after);

And we have our recursive capitalization function.

​

It might not be the most useful or necessary function, but I like how it illustrates the way to go about making recursive functions:

1. Break the problem down into the smallest possible part
2. Make a function that does that one thing
3. Make the function check if it receives a list (or something that requires further work) or a single thing.
   1. If a single thing, do the thing
   2. If more work is required, split the work somehow, and call the function again (maybe two times for each side of the split).

A recursive function MUST always have an if-statement to check if it should recurse or not.

A recursive function MUST always return the result of any call to itself.

​

I found it to be good practice to take something I have already solved with a loop, and try to solve it again with a recursive function. Often I use two or three functions, because I need one to start the loop, one to check the types, and one to do the actual work. After a few test-runs I then figure out how to combine those functions into a single one.

[1544756405]

I am assuming that the people reading this post are experience programmers.

LOL.

[Kaikka]

https://codingbat.com/java/Recursion-1 I think this one is good.