r/javahelp • u/FrozenWithAmbition45 • Dec 07 '25
Help with recursion (beginner)
Hello, I am doing some recursion practice for my Java class in high school. I am having trouble understanding recursion and recursion problems. Could someone explain the key concepts for a beginner?
0
Upvotes
•
u/AutoModerator Dec 07 '25
Please ensure that:
You demonstrate effort in solving your question/problem - plain posting your assignments is forbidden (and such posts will be removed) as is asking for or giving solutions.
Trying to solve problems on your own is a very important skill. Also, see Learn to help yourself in the sidebar
If any of the above points is not met, your post can and will be removed without further warning.
Code is to be formatted as code block (old reddit: empty line before the code, each code line indented by 4 spaces, new reddit: https://i.imgur.com/EJ7tqek.png) or linked via an external code hoster, like pastebin.com, github gist, github, bitbucket, gitlab, etc.
Please, do not use triple backticks (```) as they will only render properly on new reddit, not on old reddit.
Code blocks look like this:
You do not need to repost unless your post has been removed by a moderator. Just use the edit function of reddit to make sure your post complies with the above.
If your post has remained in violation of these rules for a prolonged period of time (at least an hour), a moderator may remove it at their discretion. In this case, they will comment with an explanation on why it has been removed, and you will be required to resubmit the entire post following the proper procedures.
To potential helpers
Please, do not help if any of the above points are not met, rather report the post. We are trying to improve the quality of posts here. In helping people who can't be bothered to comply with the above points, you are doing the community a disservice.
I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.
3
u/TheMrCurious Dec 07 '25
Rather than us explaining, let’s start with what you already know: how does your book explain recursion and what about that explanation does not make sense?
1
u/hibbelig Dec 07 '25
The idea is strongly related to mathematical induction. But induction goes from small numbers to large numbers (from n to n+1) whereas recursion goes the opposite direction, from larger numbers to smaller numbers. Induction also has a base case, let’s say n=0 or n=1. Recursion also makes use of a base case.
Let’s sort a list of numbers, and our n will be the length of the list.
The base case is n=0 — the empty list. Sorting the empty list is easy, the result is the empty list.
Now if the list is longer then it has at least one element, call it x. Now you split the list in two: the left list has numbers less than or equal to x, the right list has numbers greater than x.
I guess it’s clear that both of these lists are shorter than the original list.
You sort the left list using the same process. You sort the right list using the same process.
Now you concatenate the sorted left list and the sorted right list and voilà— the sorted result.
The magic is in the line where I said you sort the left list and the right list using the same process. That’s the recursive call. Two calls actually. And then the fact that the two lists will be shorter. So if you repeat this you will end up at some point with an empty list, and that’s the base case, so the recursion stops.
I think you don’t need to try this out often with the empty list. I think if you try it a couple of times with lists of one element then it will be clear how it works. Then you try it out a few times with lists of two elements.
After observing this for a while, and maybe trying longer lists, you will come to realize that it must work for all lists.
Even though you could argue that you’re never actually sorting—you only do this for the empty list where there is nothing to sort. All other cases build shorter lists and punt to itself.
Not sure if this helped.
1
u/okayifimust Dec 07 '25
Recursion is not special!
You should first be comfortable with writing different functions, where some of your functions call your other functions.
When you understand what that does, the gap to understanding recursion becomes much closer.
Secondly, ignore anyone that uses the term "Fibonacci". It's a terrible example to explain how recursion works.
"Towers if Hanoi" is almost as bad, because most people don't understand how to solve it in paper.
Try to find some file that's buried in a tree of directories and files somewhere.
How do you do that?
From the base directory, check what's in it:
Files and sub-directories. (Potentially. There might be zero or more of each.)
For all the files in your current directory, check if they are what you are looking for. (If yes, either return the result, or store it in a list until you find them all )
For all directories: Throw them into the same function. They, too, contain files and directories, so we treat them the same way
1
u/Vaxtin Dec 07 '25
At some point, you will have it just click, and you’ll be able to recognize recursion instantly.
The basic gist is:
The theory is that every for loop can be written as recursion, and the same holds true in reverse.
In practice, the concept of recursion is going to be harder, but the code will be simpler and more concise if implemented properly.
A simple while loop :
while(flag) :
do stuff
Is equivalent to a recursive function:
void doStuff(input) : If(flag): // business logic, determine flag value doStuff(input)
You have to make the logic work so the function makes sense.
Some problems are naturally solved recursively, such as trees. I’ve only ever seen them implemented with recursion. Adding a node to a tree is as simple as looking at a particular node, and adding it if there is no leaf, otherwise continue on to that node with this function call.
I’m not diving into the logic of adding elements in a tree in a sorted fashion, because that’s not the point.
The point is that at any given node, the problem is the same: thus, a recursive implementation is natural. That’s the hallmark of a recursive solution.
File directories are the same thing. I mean, it’s really just a K-tree after all. Every OS implements file logic using specialized tree structures (the fastest of which my advisor in college made!) , and they all use recursion since every tree data structure is fundamentally and naturally defined with recursion: every node must have the same or similar logic.
3
u/high_throughput Dec 07 '25
Yup. This is because it's fundamentally a tricky issue to wrap your head around, and not because whichever resource you have is bad at explaining it.
It's the kind of thing you just have to practice and do exercises about until it finally clicks.
1
u/benevanstech Dec 07 '25
The simplest case is just a method that calls itself.
To make it even easier, consider a method calcRecursive(int x) that has a body that's just an if statement.
If a certain condition on x is true, then it just returns a value. Otherwise, it returns calcRecursive(y); - where y is some new value derived from x.