MIPS Tutorial 33 Introduction to Recursion Video Lecture | MIPS Assembly Programming Simplified - Electronics and Communication Engineering (ECE)

hi guys this is AM L again and welcome
back to another tutorial about MIPS
assembly programming and well today I'm
going to talk to you about a very
important topic and the topic is
recursion um I apologize because I
wasn't able to post any any videos
lately
I've been very busy taking this
algorithm algorithm course but now I
want to show you this whenever you have
a program in execution it is it is
called a process and a process has these
sections of memory one text section data
the heap and the stack section the text
section is for the code because remember
that the code is going to be stored in
binary it's going to be stored in your
random access memory and this is a
concept called the store program counter
data is for all the global variables so
whenever you declare variable it's going
to be stored in the data section the
heap is for the dynamic for dynamic
memory location so if you let's say that
you're using C++ or if you're using any
other programming language and you want
to allocate memory dynamically then you
use the heap so you you as a programmer
in C++ then you have to delete the
anything that is in dynamic dynamically
allocated memory and the stack the stack
is the most important section for this
video because without a stack we
wouldn't be able to do recursion so
please understand this right here if you
understand this picture here you will be
able to understand recursion a lot
easier a lot better so I want to tell
you what recursion is all about so this
is what recursion is about recursion
is when a function calls itself and this
is like the most popular definition of
recursion if you're watching any other
tutorials about recursion that's what
people are gonna tell you when a
function calls itself so I want to show
you right here the factorial function
recursion is very popular in mathematics
and also in computer in computer science
and factorial function right here in
mathematics can be defined recursively
so this is a function and these are the
condition so if N equals 0 then the
function is going to give you one but if
n if the number is greater than or equal
to 1 the function is going to give you
the number multiplied by the function
itself evaluated 1 minus the number so
don't worry I know that maybe this
doesn't make a lot of sense to you now
but let me show you what what factorial
is so right here you can see that let's
say that you say 8 factorial so
factorial is a mathematical concept and
the simple factorial is exclamation sign
but this is actually let's say 4
factorial so 4 exclamation sign is 4
factorial so what this equals is 4 times
3 times 2 times 1 or if I say 3
factorial is equal to 3 times 2 times 1
so and if I do the arithmetic 4 times 3
is 12 times 2 is 24 times 1 is 24
so 4 factorial is equal to 24 and 3
factorial is equal to 3 times 2 6 times
1 6 so now you know what factorial means
and mathematicians they have defined
zero factorial it is defined to be 1
don't ask me why but this is just the
way mathematicians define zero factorial
you should ask a mathematician if you
want to know why zero factorial is
defined to be one but now that you know
what factorial is I'm going to go back
to the recursive definition of factorial
so you can see that the factorial of any
number is equal to 1 if the number is
zero or it is equal to the number
multiplied by the factorial of the
previous number if the number is greater
than or equal to 1 so don't worry if it
doesn't make sense it will make sense
don't worry now so I know that these are
these tutorials they are about MIPS
programming but recursion is kind of a
topic that needs a lot of explanation in
order to understand very well so that's
why I'm trying to explain it from a high
level and then I'm gonna go maybe in my
next video I'm gonna explain recursion
at a lower level using MIPS but now I'm
gonna show pictures and I'm gonna show
you how to actually I do recursion in
C++ so you can have a good foundation so
you can understand my tutorial later but
what I want to say is the following
why is requesting useful well recursion
is very useful
it's like looping like iteration but
sometimes recursion is better than
iteration and sometimes iteration is
better than recursion
so it depends on the problem that you're
trying to solve so if you have ever
taken any algorithm scores or any data
structure course you probably know about
searching and sorting so recursion is
very useful for searching and sorting
because when it comes to algorithms we
can use a divide and conquer technique
and whenever we have recursion we can
divide a problem into smaller problems
of the same type until we reach a final
a final step the base case so right here
when n equals 0
it's gonna be 1 this is the base case
and if n is greater than or equal to 1
then this is gonna this is what this is
what's going to happen so without any
further ado I'm gonna show you in C++
how it works so C++ right here and let's
do sharp include let's dang iostream
greater than using STD : : see out I'm
gonna use also in line so in a Germaine
the main function and return 0 so I want
a function that's gonna calculate the
factorial of any number so integer fine
factorial integer number so this is the
prototype right here and now I'm going
to implement the function find factorial
and it's gonna take a number and I'm
gonna take a look here so if N equals 0
then it's gonna return 1 otherwise it's
gonna return this so it's pretty easy so
if the number is equal to 0 then return
1 so this right here is the
bass case Hales return the number times
find factorial of the number minus one
so what this means is that this is the
base case so whenever the function
reaches the base case this is where the
function is going to stop otherwise the
function is gonna be calling itself over
and over again it's gonna be repeating
itself calling itself and it's gonna be
calling itself and you can think of it
as looping line looping itself calling
itself but um whenever the condition is
met whenever the number is equal to zero
then it's going to stop calling itself
what it's gonna do is that it's going to
return an answer and the answer is gonna
allow this function to give you to
calculate the right value okay
don't worry if you don't understand
because I'm gonna show you exactly how
it works so right here I'm gonna test it
so let's say that I do the following see
out the factorial of 4 is 5 factorial 4
of 4 in line so I save I execute and as
you can see the factorial of 4 is 24
okay so let me show you right now how
this works because I know it's kind of
confusing so right here you see the
picture the stack is the section of code
for your program that contains
all the functions so whenever you
whenever you call a function whenever
you're using a function it's gonna be
stored here in the stack in the stack
frame so it's gonna have a stack frame
so whenever you open your program guess
what's gonna be the stack frame in the
stack already it's gonna be the main
it's gonna be these right here so when
you call your program the the first one
that is going to be there is going to be
in the stack is main so this is gonna be
mine right here and let me give it a
name right here main wait let me change
the color and the size is gonna be 14 so
main function so right here you can see
this is the stack frame for the main
function right here so then when you
call factorial right here fine factorial
5 factorial 4 is gonna be pushed but in
this case let me do of 3 because I don't
wanna make it too too long so fine
factorial of 3 so 5 factorial of 3 is
gonna be in the stack so right here and
the function is gonna be fine factorial
of 3 so then if we go back when you call
the function with the number 3 is the
node if the number equals equals 0 do
this but the number is not equal to 0 is
equal to 3 so it's gonna say 3 times 5
factorial of 2 so 5 factorial of 2 it's
gonna it's gonna go here in the stack as
well so let me put in the stack and
whenever you put something in the stack
it is called push
a value to the stack so now it's gonna
push fine factorial of to find factorial
of 2 so right here you can see fine
factorial of 2 and then it's gonna go
back the number is not 0 so it's gonna
do 2 times 4 factorial of 1 so factorial
of 1 is gonna come here as well so
factorial of 1 find factorial of 1 okay
so now it comes here number is not 1 is
1 so it's not equal to 0 so it's gonna
say 1 times 5 factorial of zero so right
here the stack it's gonna say find
factorial of zero and because now
finally the number is 0 it's gonna come
here so if number equals equals 0
yes it's equal to 0 return 1 so now it
never it's not gonna it's not going to
call itself anymore it's gonna it's
gonna return it's gonna go back
so what it's gonna do is the following
it's gonna pop all of that all of it
it's gonna it's gonna say okay I know
what factorial of zero is it's 1 so now
I can return 1 yeah I can return 1 so
it's gonna pop it and then it's gonna
say now I know what 5 factorial of 1 is
it's just 1 times 1 because the other
function return 1
so I can pop it and then it's gonna say
oh five factorial - now I know what that
is is two times one because the other
function returned one to me so two times
one is two and then it says five
factorial three oh now I know what that
is it's three times 2 because the
factorial of 2
I gave me back 2 so 3 times 2 is 6 and
now we're back in the main function
right here and we continue working in
the main function and we print it out so
finally the main function is going to
get fat it's gonna get back the value 6
so we're gonna do it again with 3 and
you're gonna see that the factorial of 3
is 6
let me change the number here factorial
of 3 is 6 so there you go this is a very
important concept so this is just
preparing you guys so you can understand
my next tutorial in which I'm gonna be
talking about this same thing the same
program and recursion and divide and
conquer
but using MIPS I wanted to give you this
introduction because in this way you
will be able to understand better what
I'm talking about so I'm gonna do it
again so this is what happened so you
have 3 times factorial 4 fine factorial
of 2 but fine factorial of 2 doesn't
know what the value is so it's going to
say 2 times fine factorial of 1 and then
fine factor of 1 doesn't know yet
so it's gonna say 1 times find factorial
of zero and then he's gonna say Oh
I know factorial of zero is 1 now I can
return now I can go back and then he
goes back with a value of 1 so he gave
back 1 so now 2 times 1 is 2 so this one
says oh I know 2 times 1 is 2 so now I
can go back and that one goes back with
2 and now it says Oh fine factorial 2 is
totally gave me back to so it's 3 times
2 which is 6 now I can go back and then
he goes back a man gets the value of 6
and there you go
that is that is the main concept of
recursion a function calling itself and
whenever you call a function remember
that the function is going to go to the
stack section of memory and in this case
the stack is growing downward because
it's like a stack of plates it's just
like puddings one thing on top of
another and then you can only remove it
from the top of the stack and then when
you are putting stuff on the stack it is
called pushing pushing elements to a
stack pushing a function to a stack when
you are when you are taking it off from
the stack it is called popping an
element from the stack when when you are
putting the elements to a stack Crisco
it is called unwinding and when in there
and when the functions are coming back
when they are going back to the color
the whole process is is going backwards
this is called that is called rewinding
so I hope you understand the main
concept remember that recursion is a
very powerful technique I really want to
help you out to understand it and in the
next tutorial I will try to teach you
how to do recursion
at a lower level using MIPS assembly
language so thank you very much for
watching and see you next time okay bye