RECURSION | Together Java | Page 1

lethal widget May 19, 2026, 2:57 PM

#

hello can someone help me understand how recursion works with two recursive steps

still sunBOT May 19, 2026, 2:57 PM

#

<@&987246399047479336> please have a look, thanks.

#

Here is an AI assisted attempt to answer your question 🤖. Maybe it helps! In any case, a human is on the way 👍. To continue talking to the AI, you can use </chatgpt:1108714622413963314>.

#

TJ-Bot

Hello can someone help me understand how recursion works with two recursive steps

Recursion with two recursive steps means your function calls itself more than once within the same invocation. Unlike simple recursion where a function calls itself once (e.g., factorial), here you have multiple calls that branch the execution.

For example, in a function like the Fibonacci sequence:

int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

This function calls itself twice: fib(n-1) and fib(n-2). Each call creates a new branch of execution that further calls the function, growing the call tree exponentially.

Key points:

The recursion tree expands faster since you have multiple calls per frame.
Base case(s) stop the infinite recursion.
Each recursive call works independently, but their results often combine to form the answer.
Understanding this helps grasp the calls' growth and potential performance issues (like overlapping subproblems).

If you draw the call tree, you’ll see how a single input expands into many function calls, each handling a smaller subproblem.

Useful links:

cosmic matrix May 19, 2026, 2:58 PM

#

do you mean tree recursion?

lethal widget May 19, 2026, 2:58 PM

#

for example in merge sort

#

like it calls itself for the left and and the right side

cosmic matrix May 19, 2026, 2:59 PM

#

yes, so this is called tree recursion, because it creates a recursion tree of recursive calls

lethal widget May 19, 2026, 3:00 PM

#

so after the first recursive step and recursion it goes to the second one

#

and so on

hallow hinge May 19, 2026, 3:01 PM

#

Yes but it will first exhaust all the "left" side recursive calls, then come up from the bottom doing the right side call.

cosmic matrix May 19, 2026, 3:01 PM

#

i think it helps looking at that tree

#

this is for fibonacci

lethal widget May 19, 2026, 3:01 PM

#

hallow hinge Yes but it will first exhaust all the "left" side recursive calls, then come up ...

so the left recursion will be called until the base case is met?

lethal widget May 19, 2026, 3:01 PM

#

cosmic matrix i think it helps looking at that tree

i understand the fibonacci somehow i just cant seem to grasp the idea around the merge sort

cosmic matrix May 19, 2026, 3:01 PM

#

but for merge sort, take the algorithm and draw a tree of the recursive calls on a sheet of paper

#

it is the same principle

hallow hinge May 19, 2026, 3:03 PM

#

The fibonacci example here is a good example for when you need to retain intermediary results. Look at the image Spectre posted, see how many times fib(1) or fib(0) is called. Waste.

cosmic matrix May 19, 2026, 3:05 PM

#

yeah the trivial recursive fibonacci implementation is very bad, (well every recurisive fib is inferior to the trivial iterative) but i think it is a nice example for showing tree recursion because it is so easy

#

here is one for mergesort, but i think going through that algorithm and drawing the tree on a sheet of paper, help for understanding it

lethal widget May 19, 2026, 3:08 PM

#

yeah i understand the divide and conquer but i just cant see how that translates to code

#

like when the recursive steps are one under the other

#

when the first recursion ends is the first recursive step activated again or does it go to the second one

cosmic matrix May 19, 2026, 3:10 PM

#

yes it goes down to the atomar layer of the left most branch first

#

there no further recursion happens becuse it just returns, then the right one gets called, then the recusion layer is finished and we are back in the layer above, there the left call is finished because we just reurnt from that and the right one gets called

#

#1506309939059228845 message

here like surely joe said

lethal widget May 19, 2026, 3:13 PM

#

so it loops on the left recursion until the base case is met?

#

and then the right is called?

cosmic matrix May 19, 2026, 3:13 PM

#

i really recomend taking the algorithm and pen and paper and drawing the tree

#

step by step

#

then you will see

hallow hinge May 19, 2026, 3:14 PM

#

lethal widget so it loops on the left recursion until the base case is met?

Yes, inside the mergeSort method is two calls to itself then a call to some outside merge method that joins them in the correct order.

lethal widget May 19, 2026, 3:15 PM

#

i will give it a try with pen and paper

#

idk why i am so stuck on this

cosmic matrix May 19, 2026, 3:16 PM

#

i think for recursion it takes until it makes click but then you understand it

lethal widget May 19, 2026, 3:22 PM

#

does the merge happen seperatly for the left and right side?

hallow hinge May 19, 2026, 3:29 PM

#

public static void mergeSort(int[] a, int startIdx, int endIdx){
   //You have some range over a[] when you enter this function

   mergeSort(a, startIdx, midpoint);
   mergeSort(a, midpoint, endIdx);
   // now you merge, you have access to the original range
   merge(a, start,mid,end);// something like this;
}```

#

The point of recursion is that it holds temporary variables like start, mid,end, in its stack frame. The alternative in non-recursive is you keep track of those variables in some sort of Stack variable instead.

olive crown May 19, 2026, 3:31 PM

#

do u have trouble understanding this?

void foo(int x) {
  if (x != 0) bar(x - 1);
  System.out.println(x);
}

void bar(int x) {
  if (x != 0) baz(x - 1);
  System.out.println(x);
}

void baz(int x) {
  if (x != 0) System.out.println("end");
  System.out.println(x);
}

what does calling foo(2) print?

#

there is no recursion here.

#

if u understand that u also understand recursion. demystify it, java has no idea what recursion is. it just executes method after method

lethal widget May 19, 2026, 3:33 PM

#

olive crown do u have trouble understanding this? ```java void foo(int x) { if (x != 0) ba...

"end"? and 2

#

i think

hallow hinge May 19, 2026, 3:34 PM

#

cosmic matrix here is one for mergesort, but i think going through that algorithm and drawing ...

Look at this picture again. The outer most mergesort is working on the top row, and then the merge part is working on the bottom row. The second mergesort layer is 38, 27, 43, 3 on the top and 3, 27, 38, 43 on the bottom.

olive crown May 19, 2026, 3:34 PM

#

lethal widget "end"? and 2

no. take pen and paper and execute it step by step like "a dumb java robot"

#

thats how java works after all. its a dumb robot running line by line

#

dont overcomplicate it. dont guess. run it by hand line by line

lethal widget May 19, 2026, 3:51 PM

#

yeah i cant understand how this shit works thanks for your help and time tho

olive crown May 19, 2026, 4:06 PM

#

lethal widget yeah i cant understand how this shit works thanks for your help and time tho

do u understand this?

void foo(int x) {
  System.out.println(x);
  bar(x - 1);
  System.out.println(x);
}

void bar(int x) {
  System.out.println("bar" + x);
}

what does it print for foo(2)?

#

we are stepping back until the point where its becoming clear

lethal widget May 19, 2026, 4:07 PM

#

2 then bar 2

#

bar 1

olive crown May 19, 2026, 4:07 PM

#

there are 3 prints. not two

lethal widget May 19, 2026, 4:08 PM

#

why would it print the second one tho

#

never mind

#

that doesnt make sens

olive crown May 19, 2026, 4:08 PM

#

why would it end before

lethal widget May 19, 2026, 4:08 PM

#

yeah ok i get that

olive crown May 19, 2026, 4:08 PM

#

so whats the output?

lethal widget May 19, 2026, 4:08 PM

#

2 bar1 2

olive crown May 19, 2026, 4:09 PM

#

yup. so next:

#

what about this?

void foo(int x) {
  if (x > 0) bar(x - 1);
  System.out.println("foo" + x);
}

void bar(int x) {
  System.out.println("bar" + x);
}

what does it print for foo(2)?

lethal widget May 19, 2026, 4:10 PM

#

bar1 foo2

olive crown May 19, 2026, 4:11 PM

#

great.

#

so back to this:

#

void foo(int x) {
  if (x != 0) bar(x - 1);
  System.out.println(x);
}

void bar(int x) {
  if (x != 0) baz(x - 1);
  System.out.println(x);
}

void baz(int x) {
  if (x != 0) System.out.println("end");
  System.out.println(x);
}

what does calling foo(2) print?

#

its exactly the same. just a third method

lethal widget May 19, 2026, 4:12 PM

#

0 1 2

olive crown May 19, 2026, 4:12 PM

#

nice

#

so now we look at this:

#

void foo(int x) {
  if (x != 0) foo(x - 1);
  System.out.println(x);
}

what does calling foo(2) print?

#

as a reminder: java has no idea what recursion is. it works the same way as if it would be any other method

lethal widget May 19, 2026, 4:15 PM

#

0?

#

no

#

2 1 0?

#

no 0

#

0 final asnwer

olive crown May 19, 2026, 4:18 PM

#

unfortunately not correct

#

its the exact same code as the one right before

#

with foo bar baz

#

its absolutely identical

#

so i guess ur still overcomplicating it

#

instead of seeing that there is no magic involved

#

🙂

lethal widget May 19, 2026, 4:19 PM

#

2!=0 true so it call itself again and goes back to the if no?

olive crown May 19, 2026, 4:19 PM

#

foo(2) starts. if check, enters the if

#

so it calls foo(1) next

#

what does java do when it calls another method?

#

it pauses the current method

#

continues with the other method first

#

and once that is done it eventually comes back and resumes where it paused

#

so foo(2) is paused

#

foo(1) starts

#

enters if. foo(0). so foo(1) pauses

#

foo(0) starts

#

if check. not enter. print(0)

#

foo(0) is done

#

java resumes its caller, foo(1) where it paused

#

print(1)

#

foo(1) is done

#

java resumes its caller foo(2) where it paused

lethal widget May 19, 2026, 4:21 PM

#

wait it prints and then calls the method?

olive crown May 19, 2026, 4:21 PM

#

print(2)

olive crown May 19, 2026, 4:21 PM

#

lethal widget wait it prints and then calls the method?

no.

#

go back to the old code

#

foo(2) calls bar(1)

#

foo(2) is paused. bar(1) starts

#

bar(1) calls baz(0). bar(1) is paused

#

baz(0) prints 0 and is done

#

java resumes bar(1). print 1

#

bar(1) is done. java resumes foo(2). print 2

#

done

#

its exactly the same

#

if u understand the previous code u also understand this

#

if not, ur overcomplicating

#

u have to understand and visualize how java moves through the code

#

line by line. when a method calls another method it will pause the original method and do the other method first

#

if foo calls bar, java needs to pause foo and do bar first

#

once bar is done it comes back and resumes foo

lethal widget May 19, 2026, 4:24 PM

#

and it will go back to the other methods the waay it came?

olive crown May 19, 2026, 4:25 PM

#

lethal widget and it will go back to the other methods the waay it came?

u know how to this works already. look at this

void foo() {
  System.out.println("hello");
  String name = askForName();
  System.out.println(name);
}

#

foo calls askForName. foo is paused in the middle of its execution

#

askForName needs to happen now

#

once its done java will continue foo

#

with the last line

#

where it paused

#

its all there and u know it already

lethal widget May 19, 2026, 4:27 PM

#

ok so when there are two recursion steps

#

when the first one is done

olive crown May 19, 2026, 4:28 PM

#

dont rush ahead yet

lethal widget May 19, 2026, 4:28 PM

#

ok ok

olive crown May 19, 2026, 4:28 PM

#

u cant visualize this yet

lethal widget May 19, 2026, 4:29 PM

#

olive crown ```java void foo(int x) { if (x != 0) foo(x - 1); System.out.println(x); } `...

1 0?

olive crown May 19, 2026, 4:30 PM

#

nope. lets step back. walk me through every line. tell me what java executes

#

we start with foo(2)

#

what happens?

lethal widget May 19, 2026, 4:30 PM

#

x!=0 true so it calls foo(1)

olive crown May 19, 2026, 4:30 PM

#

yes. so foo(2) is paused

#

foo(1) starts. what next

lethal widget May 19, 2026, 4:31 PM

#

1!=0 true agian

olive crown May 19, 2026, 4:31 PM

#

right. so?

lethal widget May 19, 2026, 4:31 PM

#

foo(1) pauses again

#

and f(0) called

olive crown May 19, 2026, 4:31 PM

#

yes

lethal widget May 19, 2026, 4:31 PM

#

0!=0 false so the base case is met

olive crown May 19, 2026, 4:32 PM

#

yeah. java has no idea what a base case it. it runs line by line. whats the next line it runs

lethal widget May 19, 2026, 4:32 PM

#

so it doesnt recurse again

#

the print

#

so 0

olive crown May 19, 2026, 4:32 PM

#

so we get print 0. what happens next?

#

foo(0) is done now

lethal widget May 19, 2026, 4:33 PM

#

prints foo(1) and foo(2)

#

and foo(0)

olive crown May 19, 2026, 4:33 PM

#

ur rushing a bit

#

what happens next when foo(0) is done

lethal widget May 19, 2026, 4:33 PM

#

nothing?

#

checks for -1?

olive crown May 19, 2026, 4:34 PM

#

no

#

look at this again

void foo() {
  System.out.println("hello");
  String name = askForName();
  System.out.println(name);
}

#

what happens when askForName() is done?

lethal widget May 19, 2026, 4:34 PM

#

the name is printed

olive crown May 19, 2026, 4:35 PM

#

so. java resumes the paused foo() method. resumes it at the point where it called askForName and was paused

#

the caller gets resumed

lethal widget May 19, 2026, 4:35 PM

#

arent there two paused foo methods>?

#

the foo(2) and foo(1)

olive crown May 19, 2026, 4:36 PM

#

yes. so what happens when foo(0) is done?

lethal widget May 19, 2026, 4:36 PM

#

resumes those paused ones

olive crown May 19, 2026, 4:36 PM

#

which one

lethal widget May 19, 2026, 4:36 PM

#

in order?

olive crown May 19, 2026, 4:36 PM

#

who called foo(0)?

lethal widget May 19, 2026, 4:36 PM

#

foo(1)

#

and foo(2) called foo(1)

olive crown May 19, 2026, 4:37 PM

#

we were essentially here:

void foo(1) {
  if (1 != 0) foo(0);
  System.out.println(1);
}

lethal widget May 19, 2026, 4:37 PM

#

0 1 2

olive crown May 19, 2026, 4:37 PM

#

see where it says foo(0)

lethal widget May 19, 2026, 4:37 PM

#

i think i get it

olive crown May 19, 2026, 4:37 PM

#

thats where it paused foo(1)

#

so now that foo(0) came back, java resumes exactly there:

#

#

exactly the same way as with askForName()

#

no magic involved

lethal widget May 19, 2026, 4:39 PM

#

so when a method calls itself it has to go back to who called it

#

and it starts from where it wss called

olive crown May 19, 2026, 4:39 PM

#

ur making this sound as if its special. its for any method

lethal widget May 19, 2026, 4:39 PM

#

yeah lol

olive crown May 19, 2026, 4:39 PM

#

method A calls method B, A is paused. when B is done we go back to A

lethal widget May 19, 2026, 4:39 PM

#

so recursion is fake

olive crown May 19, 2026, 4:39 PM

#

yes

lethal widget May 19, 2026, 4:39 PM

#

its not like a real thing

olive crown May 19, 2026, 4:39 PM

#

java doesnt care the slightest

lethal widget May 19, 2026, 4:40 PM

#

ok this is starting to make sense

olive crown May 19, 2026, 4:40 PM

#

with that having clicked u now just have to play this "dumb robot running line by line" game

lethal widget May 19, 2026, 4:40 PM

#

so its the same with two recursive steps

olive crown May 19, 2026, 4:40 PM

#

yeah

#

do that line by line game a few times and ull get a feeling for it

lethal widget May 19, 2026, 4:42 PM

#

so in merge sort

#

when it recurses its self for the left after its done it goes to the next line which is the recursion to itself for the righ

olive crown May 19, 2026, 4:53 PM

#

yes

cosmic matrix May 19, 2026, 4:53 PM

#

https://visualgo.net/en/sorting

here is a visualisation which also shows the code. but my recommendations stays to try it line by line with pen and paper first, you are the java code executor, draw the tree. or look at this and then try to do it by yourself.

Sorting (Bubble, Selection, Insertion, Merge, Quick, Counting, Radi...

Sorting is a very classic problem of reordering items (that can be compared, e.g., integers, floating-point numbers, strings, etc) of an array (or a list) in a certain order (increasing, non-decreasing (increasing or flat), decreasing, non-increasing (decreasing or flat), lexicographical, etc).There are many different sorting algorithms, each ha...

lethal widget May 19, 2026, 5:02 PM

#

olive crown yes

but after doesnt it have to recurse back to itself to the left?

#

wait it does

#

from following the lines

#RECURSION