Original subtitles

So Lucas numbers what is going on, guys, in this video, we are going to make some exercise about

Lucas numbers and.

That's not a mathematical kuris.

That's a programming course.

We are not going to get into all the details and discuss its relation to the Fibonacci's serious.

We are simply going to talk about a sequence Lucas sequence, let's say, here, Lucas sequence.

And basically the sequence is going to have just some set of rules and we will have to like to implement

it using our programming language and using some recursive method.

So first of all, let us just make a quick recap of what a sequence is actually all about.

And basically, we know let me use the wall.

It's just pink.

So we know that sequence is just.

Sequence is just the set of numbers which have some, let's say, some straight words there in some

base conditions.

So, for example, we have like this sequence one, two, three and so on.

We know that we have the first element is one.

And then the next element is just.

The previous element, plus one, we can also have like two, four, six and so on, each element equals

to the previous element plus two, maybe, maybe like two, four and let's say eight and let's say 16,

which is just the power of the sequence of power.

Basically, there may be a lot of different sequences out there.

And what we are going to do is basically we are going to implement a new sequence that is called the

lucas' sequence.

And this sequence looks like this, so lucas' sequence at index end equals two.

Let's see if and equals to zero, then the value will be two.

OK, so that's if and equals to zero and 11 equals to one if an equal to one and ehl and minus one plus

and minus two if and is greater than one then one.

OK, so that's basically the rules for defining our sequence.

And if we will have we will take a look at for example, how it looks like.

So the first element and equals to zero and is the index.

Right.

That's the index.

So we will see that it's two and then we have one because that's the index of one.

And the next value where I am equals to two will be basically the sum of the two previous.

So it will be three and then it will be four.

Right, because two plus one is three three one plus three, four, three plus four is seven and so

on and so forth.

So that's basically the lucas' sequence.

And what we are going to do right now is simply to write a recursive function that will implement it.

OK, so these function is going to get some in OK, which will represent the index and then it will

find the value of this index using some recursive approach.

So let us start.

OK.

So what do you think should be the type of this function?

Well, basically saying we know that here probably we have at the two base cases we have integers then

probably also for the general case, let's call it this way, when we have like to add the two previous

values and these two previous values probably will also be in the jurors, then in this case, the type

of the function is also probably going to be eight.

So let's say and let's call it like lucas' recursive.

And what we are going to receive is just an which is the index.

OK, awesome.

All right.

So what do you think should happen here?

So basically it's very similar.

If you remember the Fibonacci series that we've made where we have to, first of all, to treat these

two base cases.

So let's start with an equal to zero.

So if an equal to zero, then in this case, what do we know to do?

What do you think?

Basically, we know that two should be returned, right, because the Lucas Valukas sequence at Index

zero should return the value of two.

And that's exactly what we are doing.

And if the index equals to come here and give the index.

Yeah.

And if the index equals to one and in this case, we should return one.

OK, that's not something that I decide to do, you know, like on my own, because that's simply of

the rules for this sequence.

That's exactly how it is defined.

OK, so these are the two base cases which we took care of right now and now.

What do you think that is missing?

What do you think that we didn't take care of?

So let's just use here.

That's something we took care of.

That's also something we do care of.

But what about this?

Right.

This will happen only if and is greater than one.

So assuming that the function is receiving an index, which is a positive number, at least zero or

above, then in this case we will return.

Right.

Because it was not an index zero and it was not an index one.

In this case, we will return the Valukas recursive function for and minus one plus the lucas' recursive

four and minus two.

OK, this will satisfy.

Let me just zoom in a little bit, OK.

This will basically satisfy this condition that al at index end equals to L at the end minus one which

is the Lucasville recursive for M minus one plus lucas' recursive for N minus two.

And basically that's it.

OK, we can simply run this program.

So let's say oh now we have like creative low cost value add index, let's use an index equals to percentage

D also and we will get here at index number and the value will be like Lucas' in cursive at index number.

OK, so let's try to build and run it and see what happens.

Where is the build, build and run.

Answer a number.

So let's start with zero.

So lucas' value at index zero equals to two.

OK, awesome.

That's, that's true.

And now let's try it for the index one Loukas value of the index one equals to one.

So let's see if we can find also these seven.

What is its index is zero.

One, two, three, four, index four.

So let's build and run it and let's use here for so lucas' value at index four equals to seven, which

is pretty much exactly what we have anticipated.

So I think the recursive solution is now complete.

And now, if you still have some questions, feel free to ask them regarding these lucas' recursive.

What I want us to do is simply to make a non recursive solution.

OK, so let's make it.

Additional solution without using recursion recursions again, although it's still in the section of

recursions, but I want you to simply take a look at how these function will look like if we were not

using a recursions.

So get yourself ready.

OK, I think I will leave it in this video to take a few moments, stop this video and try to think

about it, how you can solve this exercise.

These lucas' are sequenced without using the recursion method, but basically try to go back to your

previous mindset that you had like without before using recursions when you were using like iterations

and loops while using for loops, while loops and so on.

So try to think how you would implement this solution and don't skip like to the.

The answer is that I'm about to share with you, try to solve it on your own.

That's very important.

That's the time when you may feel like you're getting a hold of all of the differences between the two

approaches, the recursions and the loops.

So it takes some time.

Guys, stop the video.

And once you're done, let me know and you can go further.

So let's start writing our function.

OK, so these function type is also going to be pretty much the same.

So it's going to be and it's a low class and call it.

I don't know, I'm not not recursive, OK?

It's going to end exactly like previously.

And now we will not have any recursive calls.

We will not have any lucas' recursive.

What do we have to do is basically to understand that two main things should happen here.

So what are the two main things we assume, OK, that the previous value we will start from the bottom

up.

OK, we will assume that the previous value, OK, we will create two values, OK, we will create previous

and we will create current and we will create also temp.

Let me show you what I mean.

Exactly.

So let's first of all, start by defining these two values.

OK, so this will be like eight and three years equals two two.

And then we will also create in current equals to one.

OK, so this will be like two and one.

And what we will ask is pretty much the same question.

If M equals if in equals to zero.

Right.

Just like previously, then in this case we will return the previous book, which is basically the value

of two.

Basically you can return to OK, no problem at all.

So if and equals to one many of these case return one.

OK, so these were just basically the two cases that we needed to take care of and we took care of them.

Now we need to like to calculate every time and to remember.

OK, let me show you that every time that we would like to calculate the lucas' value at index and we

have to remember what was the value, add the previous index as well as what was the value at the previous

of the previous.

OK, so we need to remember always the two values.

So this will be the current.

OK, and this will be in this case for hour two for our two base examples, OK, let me second sorry,

this will be let's start with this will be the previous right or not.

So basically, the solution is a little bit of get lost here because I want to like to give you the

whole picture, but I think I'm doing it the wrong way.

So let's start with the solution.

Using the for a loop, I think it will be easier for you.

So let's start with I let's go.

Let's build our way together.

OK, so for Igbos to do right.

Because we already already took care of index zero and of index one.

So four equals to two as long as I is less than or equal to and I plus plus.

OK, and now what we have to do is to simply calculate some given value.

So how should we do it.

Basically, we should also create additional variable, let's call it, I don't know, let's call it

temp, OK?

And we will say that temp will be equal to the previous value plus the current value.

OK, if we will get like four equals two, we will know that previous is two and current is one.

So we simply got two plus one, which is three.

OK, which is three.

So temp now holds the value of three.

And what we have to update is the previous value.

OK, so the previous value because we have to keep track of both of them L N minus one and L and minus

two.

So the previous value is going to be equal to the current one, which is in this case simply one.

Right.

So each should be equal to current.

OK, so also what we have to update, what do you think for the next iteration.

Right.

So we know that previously we had like this was our what was it previous.

This was current.

Right.

Then we calculated this value.

OK, now we have to update it a little bit so we know that the previous is now should be here and the

current should be here.

Right.

And that's basically why we are going to use current equals to term.

OK.

And then on the next iteration, we are going to calculate this value and this will be the sum of the

previous plus the current, which is previous, plus the current, which will give us four, then you

go and so on and so on until you reach this condition of IGIS.

As long as he is less than or equal to and until this condition is true, you execute this loop and

then basically finally you return the value of current, which is basically will be the final value

that you have calculated.

Who so that was not an easy one to explain.

I hope that's clear to you guys.

And basically we talked about two different approaches to solve and basically to create functions to

find the value at index in a given index in a Loukas sequence.

So I hope that's clear with you guys.

Two approaches.

One, the recursive approach.

The other one is the lucas' non recursive approach to functions to solve one of the same things.

One has its own benefits, one has the other benefit.

Basically, one of the benefits using the recursion is simply that the answer here is just five lines

of code right in the body of the function.

It may also be like minimized to even further to be something like this.

Right.

We can also do it like that.

OK, so it will be three lines of code, but basically we can see that using the non recursive here

is much, much more code.

At least four more lines of code, not drastically more but more.

But regarding the recursion, there are also additional problems that are not being treated, at least

not in this course.

I'm not talking in like in depth.

The memory usage that are a recursive calls can make, for example, if the index here is very, very

high.

So you will have like many, many instances in the memory of your computer and this may cause some problems.

But still, that's a cause for mainly beginners.

Okay.

Not any advanced topics are discussed here.

So basically that's something that you also should bear in mind.

Yeah, and this is it, guys.

My name is Vlad.

This is Alphatech, best course programming.

So thank you so much for watching and make sure to let me know if you have any questions until then.

Next time.

We'll see you next videos.

Bye bye.