Re 3. Parameterised and Functional Recursion | Strivers A2Z DSA Course
Summary
TLDRThis video script introduces viewers to the concept of recursion through a problem-solving approach, focusing on summing the first 'n' numbers. The presenter explains two methods: parameterized recursion and functional recursion, using a simple example to demonstrate the process. They also touch on time and space complexity, and the importance of understanding recursive patterns for solving interview problems. The video is sponsored by Code Studio, offering resources for interview preparation, including problem solutions in various programming languages.
Takeaways
- 😀 The video is sponsored by Code Studio, a platform offering over 2000 interview problems and solutions in various programming languages.
- 📚 Code Studio provides guided paths for various programming topics including Python, DBMS, OOP, OS, computer networks, system design, and web development.
- 🏢 The platform also features top company interview questions, such as Amazon coding questions, and over 600 interview experiences from companies like Amazon, Microsoft, Adobe, and Google.
- 🔍 The speaker introduces a recursion problem: finding the sum of the first n numbers, and emphasizes the importance of understanding recursion for strong problem-solving skills.
- 📈 The video demonstrates two methods for solving the summation problem: parameterized recursion and functional recursion.
- 📝 Parameterized recursion involves passing additional parameters to the recursive function to carry state, while functional recursion relies on the function itself to return the answer.
- 🔑 The base case for the summation problem is when n is less than one, at which point the function should return the accumulated sum.
- 🔄 The recursive process involves calling the function with decremented values of n and accumulating the sum until the base case is reached.
- 💡 The speaker explains the importance of learning recursion patterns for different scenarios, such as when to use parameters or returns effectively.
- 📉 The video also touches on the time and space complexity of recursion, highlighting that the time complexity is O(n) and the space complexity is O(n) due to the call stack.
- 🎓 The speaker concludes by encouraging viewers to practice recursion to master it and to like and subscribe for more educational content.
Q & A
What is the main topic of the video?
-The main topic of the video is teaching recursion through the example of summing the first n numbers using both parameterized and functional ways.
What is Code Studio and why is it mentioned in the video?
-Code Studio is a platform that offers over 2000 interview problems and solutions in various programming languages, guided paths for different subjects, and interview experiences from top companies. It is mentioned as the sponsor of the video.
How many ways does the video discuss to solve the summation of the first n numbers?
-The video discusses two ways to solve the summation problem: the parameterized way and the functional way.
What is the base case for the parameterized recursion method in summing the first n numbers?
-The base case for the parameterized recursion method is when 'i' is less than one, at which point the summation is printed.
How does the functional recursion method differ from the parameterized method?
-The functional recursion method does not carry additional parameters like the sum; instead, it returns the answer directly without printing it within the function.
What is the base case for the functional recursion method when summing the first n numbers?
-The base case for the functional recursion method is when 'n' equals zero, at which point the function returns zero.
What is the time complexity of the recursive methods discussed in the video?
-The time complexity of the recursive methods discussed is O(n), as there is one function call for each number up to n.
What is the space complexity of the recursive methods due to the function call stack?
-The space complexity is O(n) due to the function call stack, as there will be n functions awaiting to be completed in the stack.
How does the video explain the transition from the parameterized way to the functional way in recursion?
-The video explains that in the parameterized way, parameters are carried through each function call, whereas in the functional way, the function itself returns the answer, which is useful when the function needs to give back something instead of printing it.
What is an example of another recursive problem presented in the video?
-The video presents the factorial of n as another example of a recursive problem, where the base case would be returning 1 when n equals 0.
Why is returning 0 as the base case incorrect for the factorial problem?
-Returning 0 as the base case for the factorial problem is incorrect because it would result in all factorials being zero, as any number multiplied by zero is zero.
Outlines
📚 Introduction to Code Studio Sponsorship and Recursion Problem
The video begins by acknowledging the sponsorship of Code Studio, a platform offering over 2000 interview problems in various programming languages. It provides guided paths for different programming topics and top company interview questions. The speaker then introduces the main topic of the video: solving the summation of the first 'n' numbers using recursion. The goal is to strengthen the viewer's understanding of recursion through this interesting problem. The explanation is set to cover two approaches: a parameterized way and a functional way, with the latter being particularly useful for dynamic programming and returning values instead of printing them.
🔍 Deep Dive into Parameterized Recursion for Summation
This paragraph delves into the parameterized approach to recursion, where the function carries additional parameters to build the solution. The speaker explains how to implement a recursive function to calculate the sum of the first 'n' numbers, starting from 'n' and moving towards 1. The base case is when 'i' is less than one, at which point the sum is printed. The recursive case involves calling the function with 'i-1' and adding the current 'i' to the sum. The explanation includes a step-by-step breakdown of the recursive calls and how the function builds up to the final sum, using an example where 'n' equals 3.
📘 Transition to Functional Recursion and Problem-Solving Patterns
The speaker transitions to the functional approach to recursion, emphasizing the importance of understanding patterns in recursive problem-solving. The functional approach is particularly useful when a function needs to return a value rather than print it, as in dynamic programming scenarios. The paragraph explains the concept of a functional recursive function, where the function itself returns the answer. The base case is when 'n' equals zero, and the recursive case involves returning 'n' plus the recursive call to 'n-1'. The speaker illustrates this with the summation problem and then extends the discussion to the factorial problem, which involves a similar recursive pattern but with multiplication instead of addition.
🤔 Addressing Base Case Issues and Time/Space Complexity in Recursion
The final paragraph addresses a common mistake in recursive base cases, using the factorial problem as an example. It explains how an incorrect base case can lead to an erroneous result, such as returning zero instead of one in a multiplication scenario. The speaker corrects the base case and emphasizes the importance of setting it properly to avoid incorrect outcomes. Additionally, the paragraph touches on the time and space complexity of recursive solutions, noting that the time complexity is O(n) due to the number of function calls, and the space complexity is also O(n) due to the stack space used by the recursive calls awaiting completion.
Mindmap
Keywords
💡Code Studio
💡Recursion
💡Summation
💡Parameterized Recursion
💡Functional Recursion
💡Base Case
💡Factorial
💡Time Complexity
💡Space Complexity
💡Dynamic Programming
Highlights
Introduction of the sponsor, Code Studio, which offers over 2000 interview problems and solutions in multiple programming languages.
Code Studio provides guided paths for various programming topics including Python, DBMS, OOP, OS, computer networks, system design, and web development.
Availability of top company interview questions, such as Amazon, tagged for easy access to coding questions and solutions in C, Java, and Python.
Access to over 600 interview experiences from major companies like Amazon, Microsoft, Adobe, and Google on Code Studio.
The video focuses on solving the summation of the first n numbers using recursion, a technique to strengthen understanding of recursive programming.
Explanation of the parameterized way of recursion, where a function carries variables and performs calculations.
Demonstration of the functional way of recursion, where the function itself returns the answer without printing it.
The base case for the summation problem is when n is less than one, which stops the recursion.
Recursive function example where the sum is calculated by adding the current number to the sum of the previous number.
Illustration of the recursion process with a step-by-step breakdown of function calls and returns.
The importance of understanding recursion patterns for problem-solving in various programming scenarios.
Transition to the factorial problem as an example of another recursive problem, highlighting the change from addition to multiplication.
Clarification of the base case for factorial, which should return 1 instead of 0 to avoid incorrect multiplication results.
Discussion on the time complexity of the recursive solutions, which is O(n) due to the number of function calls.
Explanation of the space complexity of recursion, which involves the stack space used by the awaiting function calls.
Encouragement for viewers to like the video and subscribe to the channel for more content on programming and interviews.
Conclusion of the video with a summary of the key points covered and a reminder of the importance of recursion in programming.
Transcripts
so before starting this video i'd love
to thank the sponsor of this video which
is code studio now if you are willing to
practice uh interview problems topic
wise this is the place where you should
look for because core studio has over
2000 plus problems and has all the
problem solution in c plus java as well
as python if you're looking for a guided
path then you can find for python for
dbms for object oriented programming
operating system computer networks
system design web development any other
thing that you're looking for you'll
find guided paths for every other thing
over here also also if you're looking
for any top company questions let's say
if you have an interview at amazon if
you're looking for amazon questions you
can get all the top amazon coding
questions via tag and all the solutions
in c plus java as well as python also if
you have an interview schedule you can
read their interview experiences where
there are 600 plus interview experiences
from companies like amazon microsoft
adobe google etc so what are you waiting
for code studio has a lot of free
resources for interview preparation the
link will be in the description make
sure you check it out
hey everyone welcome back to the channel
i hope you guys are doing extremely well
today we will be uh solving a very very
interesting problem in recursion which
is the summation of
the first n numbers
now this can be done using
a very simple for loop but i want you to
do this using recursion because that
will create your base of recursion very
very strong i'm going to teach you a
couple of ways the first way being the
parameter wise ways
where i'll be showing you how to do this
using parameter the next one will be
functional way where the function itself
returns
the answer okay so to start off with uh
i hope you have understood the question
sum of first n numbers assume n is given
as 3 then the summation will be
definitely 6 because
1 plus 2 plus 3 is equal to 6 the sum of
the first three numbers is what the
question states
so to start off with
let's uh learn the parameterized way
now when i say a parameterized wave what
does that mean
that means assume i write a function is
assume i write a function and i say i
and i carry a variable sum
okay and that's the recursive function
that i'm writing
and i say that okay i'm gonna think this
as a loop so in the previous lecture we
saw that we started from one we went on
to two we went down to three so we're
gonna do this uh till we don't reach n
or probably we can do it the opposite
way from n to uh
one so let's assume we do it from n to
one so we can say if at any moment i is
lesser than one yes if at any moment i
is less than one
i can definitely print yes i can
definitely say let's uh print the
summation
okay
and then try our return make sense
and apart from this what i'm going to
say is okay f of
i minus 1
sum
plus i is what i'm going to pass
so this is what my recursive statement
will be and the main will be very simple
again the main will be uh taking an n as
the input
and then we can just call f of
n comma initial summation as
0.
now this is what i have taken now for an
example let's assume this is the output
screen
and let's assume n is given as
3
so what i'm calling for the first time
is
i'm saying i to be
3
sum to be
0
right that is what i'm saying
i to be 3 and sum to be 0
this line is not executed
this line is executed and it thereby
calls another function
in the same link the same function is
called in the memory and it passes i
minus 1 which is 2 because i was 3 so it
tends down to 3 minus 1 which is 2 and
sum plus i
sum was 0 if you see sum was 0 so 0 plus
3 will become 3 so it goes as
3 again
is the if line executed
no the if line is not executed so the
functional line will be executed and
that's i minus 1 which means
something and then sum was 3
plus
i this time is 2.
now this time this function again calls
a function which says function i minus 1
so i was 2 it becomes
1 and the summation 3 plus 2 becomes 5
is the if statement executed no because
the if statement if you carefully
observe
it's
i lesser than one and that's not the
case so it's not executed correct
thereby
it goes again and calls the same
function with i minus 1
comma
sum plus
i
this time i minus 1 i was 1
so this time the functional call is made
to f of i minus 1 1 minus 1 becomes 0
then summation summation was 5
plus i i was 1 so it calls it as 6. what
is the if statement if statement stated
i lesser than 1 i less
than 1 is that the case yes so what it
does is
print the summation summation was 6 so
on the output screen the 6 is printed
and it says
return so thereby this functional line
is no more executed and it directly
returns from here
so if it returns
this function is done
and now it returns
thereby saying this function is done so
this guy
again returns
thereby this function is done thereby
this guy returns so we did a
parameterized function where we can say
that our recursive tree was
3 comma 0 where this being the i and sum
we went on to f of 2 comma added this 3
we went on to f of 1 comma added this 2
we went on to f comma 0 added this one
so whenever we ended up at 0 we just
printed this because we were
adding the i adding the i every time to
the parameter
and that is what we printed this could
have been done in the other way where
you could have done i plus one as well
but i'm just teaching you the parameter
way in how can you actually carry the
parameters yes because over here we
increase the parameters and at the end
of the day at the end of the day we came
here and print this particular parameter
which is six so this is how the
recursion tree will be at the end it
came back came back came back and went
back right this is how you can do it
using parameterized okay
now if you've understood the
parameterized it's time to understand
the functional
how do you generally
write the function because functional
means uh
you don't want the parameter to do the
work you want you write a recursive
function where you say that hey listen
this is my value of n take n as 3 and
give me the summation as 6. so if i'm
asking you to write such a function
that's when you cannot use parameterized
because you want the function to return
the answer you don't want it to print
you want it to return why
uh
there will be a lot of cases when you
learn dynamic programming that you want
the function to give you back something
instead of printing right so basically
uh to understand the concept before
writing the recursive code let's uh so
these are all patterns that i'm teaching
it's not that i'm just writing the codes
these are patterns i'm teaching you to
learn these patterns if parameters are
there then you have to do it in such a
way if there's return then you have to
do it in such a way to learn these
patterns once you're very confident
about these patterns you can solve any
problem in recursion that is my word
okay to go with functional let's
understand when i say functional what
does that mean now if n is given as a 3
for a reason if n is given as 3
can i say this can i say this
i can say i'll do a 3 i'll do
f of 2
where i know where i know
f of n means
summation of
first n numbers okay i know this so if i
write
3 plus f of 2 makes sense
then when i'm calling for f of 2 can i
say okay
that can be written as 2 plus f of 1
and when i'm at f of 1 can i write this
as
1 plus f of 0
and everyone knows that f of 0 is
nothing but 0 so i can think it in such
a way that okay
whenever there is an f of n
i know n will be there
i know n will be there which is 3
because if i'm saying f of 3 i know the
summation will contain 3 but i need the
summation of the rest of the
rest of the two numbers
so this is the idea that i am going to
follow so what i'll say is okay
let them give me the n
if at any moment n is equal to equal to
zero i'm going to return a zero because
if f is if n is zero i know the
summation of the first 0 numbers is 0
or else
i'm going to return simply
n plus f of n minus 1 okay
i'm going to simply return n plus f of n
minus
1
done
now question
might arise
how will this work let's understand
let's write the main function again so
if i write main
and i say n is given as 3 and i call f
of 3 or f of n rather
and i write
print this f of
n
so what is being done
this f of n
goes and calls this so let's call this
with what value
with the value 3 f of 3 is called is
this line executed
no
n means
3
plus
f of n minus 1 is called remember this
there's a line
in completed line 3 plus something
incompleted that incompleted will be
called in recursion till it does not
comes i'm waiting three plus three plus
something something i'm waiting got that
so
f of two now goes
it states if n is equal to equal to zero
it says no
so i'm like okay return
two plus f of one
this time
two plus
this line
waits
for f of one to be done so i go and call
f of one
if n is equal to equal to 0 again i say
no remember this you could have written
n equal to equal to 1 that's your choice
you can write it i'm just teaching you
patterns that's it return 0 doesn't
works
return
one plus
f of zero
again this line awaits i am awaiting let
him come back
so let's go
f of zero
when you go for f of zero let's
understand what happens
if n equal to equal to 0
returns a 0
this guy comes in with a value 0 returns
a 0 this time i'm returning something
i'm giving back something so it's
returning a zero i hope that makes sense
so whenever
this function is called this function is
called it came back with zero came back
with zero so can i say
now instead of writing this f of 0 i can
actually write this 0 because this
function yielded you a value 0 so
thereby 1 plus 0 is 1
hence return this guy returns a 1
1 0 returns are one so can i say now
instead of writing f of one
can i write one because one has been
returned
thereby two plus one can i say this guy
returns a three indeed i can say that f
of n minus one goes away and i can write
three so thereby three plus three is six
thereby this guy returns six and you say
so output is six
this is how yes this is how you can
write a
functional stuff when the problem is
broken down into smaller parts yes
the problem gets broken down into
smaller smaller parts and once it is
broken down it easily gives you the
output
so coming across to the code the quotes
very very simple you say int sum you can
call int n
right and you can simply write if n is
equal to equal to 0
please
return a 0
else return an n plus sum of
n minus 1 and over here probably i i can
just keep n equal to a 3 you can take
this take this as input as well c out
sum of n so if i just write it you'll
see this this perfectly works
i saw it perfectly it's a very simple
one okay so i hope you've understood how
to get the sum of first n numbers
now if i give you a very simple
task task is
factorial of
n
what is factorial of n
whenever i give you n equal to 3
it is 6 whenever i give you n equal to 4
it's 24 basically 1 into 2 into 3 this
time it's 1 into 2 into 3 into 4 correct
multiplication instead of addition
multiplication instead of addition so
how will you do this
i think that's very simple this time
very simple
uh
if i write the code
so i'll leave the parameterized you can
do it yourself i'll try to write the
recursive code okay now you know one
thing for sure in the recursive code
this will become a factorial
correct
and this will become into because 5 into
4 into 3
and this will become n minus 1 but we
need to understand will the base case
change
will it be n equal to equal to zero the
step let's see if i write this and if i
run this what happens let's understand
if i just give it a run
see uh okay sorry let's give it a run so
if i
let's change it factorial okay now let's
give it a run so if i give it a run you
see the output being zero so you see the
output being zero why
due to this base case let's understand
how why did this base gave uh
why did this base case give you 0 so if
i write f of n
and i write the base cases n equal to
equal to 0 and i say return
0 and i'm saying return
n
into
factorial of n minus 1 if this is the
code
and i am writing the main function as
n is given as 3
and i'm saying print
f of n
so basically this guy goes and calls
this with three
not executed
three into
f of
two not executed
if line is not executed so return
2 into f of 2 minus 1 which is 1
so this is gone f of 1
again you're writing n equal to equal to
0 not executed
return 1 into
f of
0
f of 0 is going
and this time the if is executed
and you return a 0 and you return a 0
which is absolutely wrong because the
moment you return on 0 this guy returns
a 0 and if i just strike it off instead
of f of 0 you end up writing a 0 which
means 1 into 0 is 0 you get a 0 thereby
this is straight up 0 2 into 0 is 0
0
this gets 0 3 into 0 is 0 you get a 3.
so what should you have returned yes you
should have written ideally 1
or or or
you should have done this
this is also correct or even if you keep
this this is also correct you should
return one because in case of
multiplications if you're returning 0
the overall product gets multiplied to 0
thereby giving you a wrong answer so
this is what i wanted to
explain you again uh what about the time
complexity you're basically uh doing one
call two call three call till n calls
so i can say big of n
is the time and the space complexity is
an auxiliary space stack space because
this awaits then this awaits so there
will be go of n
uh n functions will be awaiting to be
completed so stack space will be taken
so in stack uh this is what the time and
space complexity will be y big of n as
the time complexity first time this
function is called next this time and
these functions are all unique functions
you don't take a lot of time inside
these functions thereby the number of
function calls will be equal to the
number of time complex is equal to the
time complexity so guys i hope you have
understood the entire lecture so just in
case you did please please please make
sure you like this video and if you're
new to the channel please do consider
subscribing please please do consider
subscribing and yeah with this let's
wrap up this video and meet in the next
precaution video bye-bye
[Music]
関連動画をさらに表示
Re 2. Problems on Recursion | Strivers A2Z DSA Course
Penjelasan Algoritma Rekursif | Algoritma Faktorial dan Pangkat | Algoritma Pertemuan 57
Penjelasan Algoritma Rekursif
Rekursi - Berpikir Komputasional
Menerapkan Konsep Rekursi - Berpikir Komputasional - Rekursi
Dynamic Programming isn't too hard. You just don't know what it is.
5.0 / 5 (0 votes)