Re 3. Parameterised and Functional Recursion | Strivers A2Z DSA Course

Summary

This 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

00:00

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

05:02

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

10:05

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

15:06

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

Keywords

💡Code Studio

Code Studio is mentioned as the sponsor of the video, offering a platform for practice interview problems. It contains over 2000 problems with solutions in various programming languages such as C, Java, and Python. It is related to the video's theme as it provides resources for interview preparation, which is the main focus of the video content.

💡Recursion

Recursion is a key concept in the video, referring to a function that calls itself to solve smaller instances of the same problem. It is central to the video's theme of solving problems like the summation of the first n numbers and factorial of n using a recursive approach. The script provides examples of how to implement recursion in programming.

💡Summation

Summation in the video refers to the process of adding a sequence of numbers together to find the total sum. It is used to illustrate a problem that can be solved using recursion, where the script explains how to calculate the sum of the first n numbers both through parameterized and functional recursion.

💡Parameterized Recursion

Parameterized Recursion is a method of implementing recursion where parameters are carried through each recursive call. In the script, it is exemplified by a function that calculates the sum of the first n numbers by carrying the sum and the current number through each recursive call until the base case is reached.

💡Functional Recursion

Functional Recursion is a style of recursion where the function itself returns the answer rather than printing it. The script explains how to implement this by creating a function that calculates the sum of the first n numbers, where the function returns the result instead of printing it, which is useful for further calculations or in dynamic programming.

💡Base Case

The Base Case in recursion is the condition that stops the recursion from continuing infinitely. In the video, the base case is used to define when the recursive function should stop calling itself, such as when n is less than one for summation or n equals zero for factorial calculation.

💡Factorial

Factorial, denoted as n!, is the product of all positive integers up to n. It is introduced in the video as an example of a problem that can be solved using recursion. The script explains how to calculate the factorial of n using a recursive function, emphasizing the importance of the base case to avoid incorrect results.

💡Time Complexity

Time Complexity in the context of the video refers to the amount of time an algorithm takes to run, often expressed in terms of the size of the input. The script mentions that the time complexity of the recursive solutions for summation and factorial is O(n), as the function makes n recursive calls.

💡Space Complexity

Space Complexity is the amount of memory an algorithm uses in relation to the size of the input. The script discusses that the space complexity of the recursive approach is O(n) due to the stack space used by the recursive calls, where each call awaits the result of the next.

💡Dynamic Programming

Dynamic Programming is a technique used in algorithms to improve efficiency by storing the results of expensive function calls and reusing them when the same inputs occur again. Although not the main focus, the script briefly mentions dynamic programming in the context of wanting the recursive function to return a value for further use, rather than just printing it.

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

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

print

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]