Java Recursion
Summary
TLDRThis tutorial delves into the concept of recursion, explaining it as a method that calls itself, simplifying the problem with each call until it reaches a base case. The video demonstrates calculating triangular numbers and factorials using recursion, illustrating the process with visual examples and code snippets. Additionally, it provides a detailed walkthrough of the merge sort algorithm, showcasing its efficiency and organization through an animated execution, all aimed at helping viewers grasp these fundamental programming concepts.
Takeaways
- 🔁 Recursion is a method where the function calls itself, simplifying the problem with each call until it reaches a base case where it no longer calls itself.
- 📊 The script explains how to find triangular numbers using recursion, which involves summing numbers from 1 to n, where n is the position in the sequence.
- 📚 The base case for the triangular number example is when the input number equals 1, at which point the method stops calling itself and returns 1.
- 📈 Triangular numbers are demonstrated visually as numbers arranged in triangles, with the nth triangular number being the sum of the first n natural numbers.
- 🤔 The tutorial also covers a non-recursive method for calculating triangular numbers, which is a simple iterative process summing numbers from 1 to n.
- 📝 The script provides a step-by-step explanation of how to implement a recursive method to calculate triangular numbers, including printing intermediate results for clarity.
- 🎲 Factorials are introduced as another example of a calculation that can be performed using recursion, with the base case being factorial of 1 equals 1.
- 👉 The merge sort algorithm is explained, which uses recursion to sort arrays efficiently by dividing the array into smaller parts, sorting them, and then merging them back together.
- 📉 The merge sort process is visualized through the script, showing how it compares and swaps elements to sort the array incrementally.
- 💻 The tutorial includes code examples and comments to aid understanding of recursive methods, triangular numbers, factorials, and the merge sort algorithm.
- 🔍 The script encourages viewers to look at the provided code, which is heavily commented, to understand the inner workings of the merge sort algorithm.
Q & A
What is the main topic of this tutorial?
-The main topic of this tutorial is recursion, including its definition, how it works, and its applications in calculating triangular numbers, factorials, and in the merge sort algorithm.
What is a recursive method?
-A recursive method is a method that calls itself, simplifying the problem with each call until it reaches a base case where it no longer calls itself.
What are triangular numbers and how are they related to recursion?
-Triangular numbers are numbers that can be represented in a triangle pattern. They are related to recursion because the script demonstrates how to calculate them using a recursive method.
How is the nth triangular number calculated using recursion?
-The nth triangular number is calculated using a recursive method that adds the sequence of numbers from 1 to n, with each recursive call reducing the number by one until it reaches the base case of 1.
What is the base case in a recursive method?
-The base case in a recursive method is the condition that stops the recursion, typically when the problem is simplified enough that it no longer requires further recursive calls.
Can you explain the non-recursive approach to calculating triangular numbers?
-The non-recursive approach to calculating triangular numbers involves summing the sequence of numbers from 1 up to the desired number, without using method calls to itself.
What is a factorial and how is it calculated using recursion?
-A factorial is the product of an integer and all the integers below it. It is calculated using recursion by multiplying the number by the factorial of the number minus one, until the base case of 1 is reached.
What is the merge sort algorithm and how does it use recursion?
-The merge sort algorithm is a sorting technique that divides the array into smaller parts, sorts them, and then merges them back together in the correct order. It uses recursion to repeatedly divide the array until each part is a single element or empty, and then merge them back in sorted order.
How does the merge sort algorithm sort an array?
-The merge sort algorithm sorts an array by first dividing it into halves, sorting each half, and then merging the sorted halves back together. This process is done recursively until the entire array is sorted.
What is the significance of the merge sort algorithm in computer science?
-The merge sort algorithm is significant in computer science because it is an efficient, stable, and comparison-based sorting algorithm with a time complexity of O(n log n), making it suitable for large datasets.
Outlines
🔁 Introduction to Recursion and Triangular Numbers
The video script introduces the concept of recursion, a method that calls itself to solve a problem by breaking it down into simpler instances. It uses the example of calculating the nth triangular number to illustrate recursion. The script explains that a recursive method will eventually reach a base case where it stops calling itself. The process of calculating triangular numbers recursively is demonstrated, showing how each method call simplifies the problem until reaching the base case. The script also provides a visual representation of triangular numbers and contrasts the recursive method with an iterative approach that doesn't use recursion.
📊 Recursive Calculation of Triangular and Factorial Numbers
This section of the script delves deeper into the recursive calculation of triangular numbers, providing a step-by-step breakdown of the process and the base case for the recursion. It then transitions into explaining how to calculate factorials using recursion, with a similar structure of a base case and recursive calls. The script includes code snippets and explanations to demonstrate the recursive process for both triangular numbers and factorials, highlighting the method's efficiency in breaking down complex problems into manageable parts.
🔍 Understanding the Merge Sort Algorithm Through Recursion
The final paragraph of the script shifts focus to the merge sort algorithm, which utilizes recursion to sort arrays efficiently. The script provides a high-level overview of how merge sort works, explaining the process of dividing the array into smaller parts, sorting them, and then merging them back together. The explanation includes a visual demonstration of the sorting process, showing how the algorithm compares and orders elements within the array. The script emphasizes the importance of understanding the underlying mechanics of merge sort, even if one typically uses pre-written code for such tasks.
Mindmap
Keywords
💡Recursion
💡Triangular Numbers
💡Factorials
💡Merge Sort
💡Base Case
💡Recursive Method
💡Divide and Conquer
💡Sorting Algorithm
💡Recursive Call
💡Iterative Method
Highlights
Introduction to recursion, explaining it as a method that calls itself until a simpler problem is reached.
Demonstration of a recursive method to find the nth triangular number.
Explanation of triangular numbers and their visual representation as triangles.
Comparison between recursive and iterative methods for calculating triangular numbers.
Illustration of the base case in recursion as a condition to stop the method from calling itself.
Recursive method implementation for calculating triangular numbers with detailed tracing.
Introduction to factorials and their calculation using recursion.
Recursive method for calculating factorials, including base case and recursive case.
Visualization of the merge sort algorithm using recursion to sort an array.
Detailed explanation of how merge sort works step by step.
Commentary on the efficiency and organization of the merge sort algorithm.
Demonstration of the merge sort algorithm in action, sorting an array.
Explanation of the sorting process within merge sort, including shifting and comparing elements.
Final sorting of the array using merge sort, showcasing the algorithm's effectiveness.
Invitation for viewers to leave questions or comments for further discussion.
Teaser for the next tutorial covering more sorting algorithms.
Transcripts
whoa Internet and welcome to part 6 of
my job algorithms tutorial today I'm
going to talk about recursion what it is
how it works and on top of that we're
going to take a look at what our
triangular numbers water factorials and
how to use recursion in the merge sort
all of the tutorials in my java
algorithms tutorial series is available
and i'll link in the upper right-hand
corner if you want to look at something
else i have a lot to do so let's get
into it so what exactly is recursive
method it's just a method that calls
itself and with each method call the
problem is going to become simpler and
simpler and the only condition with a
recursive method is that it will
eventually lead to a point where the
method no longer calls itself so let's
see exactly what that looks like
over here on the right-hand side of the
screen you will see a recursive method
and it is named get try number and if
you pass in a value like 6 into this guy
well obviously 6 is not equal to 1 so we
skip over this condition we get down
here where num is going to be equal to 6
of course and then we have a call to the
method itself and it is going to pass in
8 5 whenever that happens again you have
a situation where you do not know what
this is but you know what this is equal
to and that is again going to be 5 and
you're going to pass in 4 then you get a
situation where you have 4 plus whatever
the result of this calculation and then
you have 3 plus whatever 3 minus 1 equal
to 2 and the 2 goes back into the method
again and then as we approach the end
you see that 2 plus get try number and
we are passing a one end and whenever
you look at this guy up here you can see
that we are getting to the end and the
number 1 is passed in just as you can
see here it goes up here then we can now
calculate the previous method 2 plus 1
is going to be equal to 3 now we'll that
we have a result for that we can pass
that up here now that we have a result
for this guy we can pass the 6 up here
now that we have a result for that we
can pass the 10 up here and now that we
have a result for this we can pass the
15 up there and that is how recursion
would work if you're trying to find the
nth triangular number if you don't know
what a triangular number is
don't worry I'm going to cover that in a
second so let's look at recursion using
a totally different layout if that
didn't solidify it in your mind right
here I have three methods and they are
all inside of boxes because this is our
recursion works so let's say a 3 is
passed into my recursive method again we
get to a situation where we do not know
what the value is after this calculation
is done hence all of these methods are
going to be calling down to these guys
until we get to the part right here
where 1 minus 1 is going to be equal to
0 and this is going to return a value of
1 as it did right there now that we have
returned value we can now take this one
and pass it up here and that's exactly
what we did and now we know that 2 plus
1 is going to be equal to 3 just as you
see right there and now we can return a
3 up here and whenever we do that 3 plus
3 is going to be equal to 6 and all of
our method calls or done so there's two
different ways to look at recursion now
let's look at it using code so here is
our code and all the code here both that
I show you as well as the code that I
don't show is available in a link in the
description under the video so what I'm
going to do here first off is to show
you what triangular numbers are and I'm
just going to come in here and go
recursion tool and then I'm going to
calculate and print out triangular
numbers so let's say I want to do it up
to the sixth triangular number I'll save
that and execute now you know what a
triangular number is the first one
doesn't look much like a triangle but
you can see that the second one most
definitely does and all that we're doing
here is going one two and three and
finding the triangular number then once
again we are finding the third
triangular number by going one two three
four five six and again there is the
third triangular number and you can see
that there is going to be a equal number
of rows to ultimate columns that's why
it looks like a triangle and that's why
it is called triangular numbers so now
before I show you how to create
triangular numbers or calculate
triangular numbers using recursion I'm
going to show you how to do it not using
recursion because
is even though triangular numbers and
recursion or normally talk together
it ultimately doesn't make sense to use
recursion when calculating triangular
numbers but don't worry about it
and you can forget that I just said that
just focus on the recursion part this is
how you would calculate triangular
numbers if you didn't want to use
recursion pretty simple so I can just go
angular number is equal to zero and how
you actually calculate a triangular
number is let's say you wanted to find
the third triangular number you would
just go three plus two plus one and get
six
that is the third triangular number and
that's how they're calculated so now
knowing that what we're going to do is
go while number is greater than zero
we're going to calculate our triangular
numbers by decrementing backwards from
r3 so triangular number is going to be
equal to triangular number plus number
and then we are going to decrement
backwards from that and then after this
we're gonna go return triangular number
and if we jump back up into main and see
how easy it is to print that out
we're gonna go recursion tool throw that
in there and get triangular number and
we can throw a six inside of there and
let's just block this out so it's not
confusing and go in here and put TN just
to give a little bit of information and
execute and there you can see triangular
number is going to be equal to 21 21 is
the sixth triangular number so now let's
take a look at how to calculate or find
triangular numbers using recursion I'm
actually going to put a couple things
inside of this so that we're going to be
able to easily see what's going on as
recursion is occurring so we're going to
go pass in our number just like we did
before and just to reiterate every
recursive method is going to have a
condition that leads to the method no
longer making another call on itself and
that condition is known as the base case
so in this situation it's going to be
number equal to one and the other
example I show you is going to be very
very similar but because I want to show
you exactly what is going on here which
method is going to be entered inside of
this I'm going to put number right there
and here I'm going to put the value that
is going to be returned and then of
course
going to return that value and then
we're going to get into this situation
where a 1 was not entered in that
situation we're going to calculate a
result which is going to be number plus
and this is going to be the method call
back to itself right like that and of
course we're going to pass whatever the
number is minus 1 into that guy to get
the result then so then I can just print
some information here on the screen so
you can see what's going on I'm going to
come in here and type in result so
result will get printed out on the
screen and I'm going to get rid of this
because I'm going to put some additional
information inside of here and that
additional information is going to be
the actual method that is going to be
executed and here I'm just going to go
get TN just to be simple plus you'll see
what this looks like in a second and
then of course we're going to return our
result and then if we bounce up here
let's copy this first and get to this
guy right here Chaney I can actually
just change that to R and execute it
you're going to see exactly what goes on
when these triangular numbers are
executed again we're going to enter
method 6 enter method 5 4 3 2 1 1 is
going to get a return value which is
going to be equal to 1 2 plus 1 is going
to be equal to 3 and 3 plus 3 is going
to be equal to 6 and 4 plus 6 is going
to be equal to 10 and 5 plus 10 is going
to be equal to 15 and 6 plus 15 is
finally going to be equal to 21 and we
know now what the sixth triangular
number is using recursion and you can
see exactly right there exactly how it's
calculated so now let's take a look at
how to calculate factorials in much the
same way so I'm going to scroll down
inside of here and of course the
factorial of 3 is going to be calculated
3 times 2 times 1 that is or a factorial
which of course is going to be equal to
6 so now we have to actually come in
here and calculate that and of course
I'm going to use recursion so I'm going
to go public int get factorial it's
going to receive a number and of course
I'm going to put a little note inside of
here so you can see exactly how the
method is going to be entered and so
forth and so on and then we're going to
put our base case inside of here
equal to one again we're going to be
doing a very very similar thing return
one and then of course we're going to
have one return and then of course we're
going to go else calculate the result
which is going to be number times get
back toriel call to itself it's going to
pass in number minus one system out
returns and this is going to be the
result of the calculation and then let's
jump up here and actually copy this so I
don't have to actually type all that out
again because like I said very very
similar and change this to print paste
that in there and here it's going to be
factorial then the difference is going
to be this is going to be a
multiplication sign and then of course
after we're done messing around with
that we can actually calculate and
return our result
now get factorial jump abeer factorial
throw this inside of there I'll save and
execute and there you can see exactly
how factorials are calculated just
exactly the same method six method of
five method for method three method to
method one method one is going to return
1 2 times 1 is going to be equal to 2
and 3 times 2 is going to be equal to 6
and 3 times 4 is going to be equal to 24
and so on and so on and so on so there
are two more examples of how to use
recursion to make calculations and do
all kinds of funky stuff now rather than
type out a whole bunch of information
about the merge sort I'm going to
instead show you precisely how it works
now the merge sort is going to sort in a
very very neat and organized way very
very fast as well and of course it's
going to use recursion to do so now I
could have went through here and typed
out all of this code but instead I just
went in and heavily commented it and
decided to focus all of my time in this
part of the tutorial to actually showing
you the merge sort work because most of
the time you're just going to simply
copy and paste and execute a merge sort
you're not going to try to memorize it
but it is important understand how it
works so let's execute this guy ok so
you can see here this is the start of
our array and these are the indexes and
then these are the values that are going
to be stored inside of them well let's
just look at exactly what is going on as
we are going down through this we're
going to hit apart where we are going to
judge the differences between index 0
and 1 and as you can see
here we're checking to see if 10 is less
than 8 of course it's not so what we're
going to do with the merge sort is we're
going to store the value of 8 in a
temporary variable we are then going to
take the value that is stored in the 0
index which is 10 and instead store it
in the 1 index
why because we are then going to copy 8
which was stored in temp into the zero
index and as we come down here you can
see that is precisely what happened they
switched places and as we continue
onwards you can see that it's then going
to judge the differences between what is
in index 2 and 3 see it's slowly going
through this array and sorting it bit by
bit
so it's going to say is 4 less than 80
of course hence we have nothing left to
do so now we have the first two indexes
sorted and the second grouping of index
is sorted so now what we need to do is
sort all four of these and that's
exactly how them the merge sort works so
if we move onwards we're going to be
checking if 8 is less than 4 since that
comes back false what are we going to do
we're going to store four in a temporary
variable and because we already know
that 8 is less than the value that is in
stored inside of index 1 we can move 4
down to here and that is precisely what
we do just by shifting these indexes
along until we get to the part right
down here and you can also see I have a
whole bunch of information on the screen
in addition to what I'm actually talking
about to help you along if you wanted to
do this on your own you can see that the
flora gets shifted there and the 8 and
10 get moved up next we're going to
check if this index is less than this
index which it isn't and then finally we
are going to check if 10 is less than 80
which of course it is and you can see
once we get to this part that the first
part the first 4 rather than the first 2
are all going to be in proper order then
what the merge sort does is focuses on
this second part and sorts it as you're
going to see we're going through here
we're going to be moving the 1 into this
position which is exactly what happens
there and then we're going to be moving
the 3 into the 13 position which is
actually what we are going to do right
here and then of course finally we're
going to sort this second part to move
the 11 where the 13 is and that's what
we did right there once again these two
are in order and these two are in order
so now we have to get all of those in
perfect order all four of them and we're
going to move onwards and take all of
these array parts and move them in order
by shifting just as we did previously
until the whole entire array is sorted
and in perfect order
so that is a run-through quickly of how
the merge sort works once again I have
all the code and it's heavily heavily
commented for the merge sort if you want
to take a look at it and I thought it
would be interesting to look at it as it
was being executed like this rather than
just going line by line by line of code
please leave any questions or comments
below up next I'm going to cover some
more sorting algorithms otherwise till
next time
浏览更多相关视频
Penjelasan Algoritma Rekursif | Algoritma Faktorial dan Pangkat | Algoritma Pertemuan 57
Penjelasan Algoritma Rekursif
Recursion in C
Re 3. Parameterised and Functional Recursion | Strivers A2Z DSA Course
Dynamic Programming isn't too hard. You just don't know what it is.
Rekursi - Berpikir Komputasional
5.0 / 5 (0 votes)