Java Recursion

Summary

This 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

00:00

🔁 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.

05:01

📊 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.

10:02

🔍 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.

Keywords

💡Recursion

Recursion refers to a method in programming where the function calls itself in order to solve a problem by breaking it down into simpler sub-problems. In the video, recursion is the central theme, with the presenter explaining how it works and demonstrating its use in calculating triangular numbers, factorials, and as a fundamental part of the merge sort algorithm. The script provides a clear example of a recursive method named 'get try number' that calculates the nth triangular number.

💡Triangular Numbers

Triangular numbers are a sequence of numbers where each number represents a triangle with dots, with the nth triangular number representing a triangle with n rows of dots, each row containing n dots. The script describes how to calculate these numbers using both iterative and recursive methods, with the recursive method being a key demonstration of recursion's utility.

💡Factorials

A factorial, denoted by an exclamation mark (e.g., 5!), is the product of all positive integers less than or equal to a given number. In the video, the presenter discusses how to calculate factorials using recursion, showing that the factorial of a number n is the product of n and the factorial of (n-1), with the base case being the factorial of 1 which is 1.

💡Merge Sort

Merge sort is a divide-and-conquer algorithm used for sorting arrays. The script explains that merge sort works by dividing the array into smaller parts, sorting those parts, and then merging them back together in the correct order. The presenter demonstrates the algorithm's process through a visual example, showing how it systematically organizes the array elements using recursion.

💡Base Case

In the context of recursion, the base case is the condition under which the recursive method stops calling itself and returns a value directly. The script illustrates this with examples where the base case is when the input number equals one, at which point the method does not call itself but returns a value, preventing infinite recursion.

💡Recursive Method

A recursive method is a function that includes a call to itself within its own body. The script provides an example of a recursive method named 'get triangular number', which calculates the nth triangular number by making recursive calls with decrementing values until it reaches the base case.

💡Divide and Conquer

Divide and conquer is a problem-solving strategy where a problem is divided into smaller sub-problems, each of which is solved independently, and the solutions are then combined to solve the original problem. The merge sort algorithm, as described in the script, is a classic example of this approach, where the array is repeatedly divided and then the sorted sub-arrays are merged.

💡Sorting Algorithm

A sorting algorithm is a set of instructions that converts a list of items into order. The script discusses different sorting algorithms, such as merge sort, and their applications, particularly focusing on how recursion can be used within these algorithms to achieve efficient sorting.

💡Recursive Call

A recursive call is when a function calls itself within its own execution. The script demonstrates this concept through the 'get factorial' method, where each call to the method results in another call with a decremented value until the base case is reached.

💡Iterative Method

An iterative method is a way of solving problems using loops that repeat a block of code until a certain condition is met. The script contrasts this with recursion by showing how triangular numbers can also be calculated iteratively without the use of recursion, using a loop to sum the numbers from 1 to n.

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