Re 2. Problems on Recursion | Strivers A2Z DSA Course

Summary

This video, sponsored by Code Studio, offers a comprehensive guide to basic recursion problems, ideal for interview preparation. The presenter introduces over 2000 coding problems, solutions in C, Java, and Python, and guided paths for various topics. The tutorial focuses on recursive functions to print a name or numbers in a sequence, both linearly and in reverse, using parameters effectively without global variables. The explanation includes the concept of backtracking and emphasizes understanding recursion flow and complexity, ensuring viewers grasp the foundational concepts of recursion.

Takeaways

• 😀 The video is sponsored by Code Studio, a platform with over 2000 interview problems and solutions in C, Java, and Python.
• 📚 Code Studio offers guided paths for various subjects like Python, DBMS, OOP, OS, computer networks, system design, and web development.
• 🏢 It also provides top company interview questions, such as Amazon's coding questions, and a collection of interview experiences from companies like Amazon, Microsoft, Adobe, and Google.
• 🔗 There are free resources available for interview preparation on Code Studio, with a link provided in the video description.
• 📈 The video focuses on basic recursion problems, building on a previous lecture about recursion.
• 🔑 The first problem discussed is printing a name 'n' times using recursion, emphasizing the importance of base cases and recursive calls.
• 🔄 The concept of changing parameters in recursion is introduced, with an example of printing a name 'n' times without using global variables.
• 🕵️‍♂️ The video explains how recursion works with a step-by-step breakdown of function calls and returns, using the example of printing a name.
• 📉 The time and space complexity of the recursion examples are discussed, highlighting that both are O(n) for the given problems.
• 🔢 Additional recursion problems, such as printing numbers linearly from 1 to n and vice versa, are covered with a focus on understanding the logic behind the recursive calls.
• 🔄 Backtracking is introduced as a recursion technique, demonstrated by printing numbers in increasing order but with the print statement placed after the recursive call.
• 💡 The video challenges viewers to think about recursion in reverse order and to solve problems by starting from the end, encouraging active learning and participation.

Q & A

What is the main topic of the video?

The main topic of the video is solving basic recursion problems in programming.

Who is the sponsor of the video?

The sponsor of the video is Code Studio, a platform for practicing interview problems.

What kind of problems does Code Studio offer solutions for?

Code Studio offers solutions for over 2000 problems in various topics including C, Java, Python, DBMS, OOP, OS, computer networks, system design, web development, and more.

How can viewers find top company interview questions on Code Studio?

Viewers can find top company interview questions via tags, such as 'Amazon', and get all the top coding questions along with their solutions in C, Java, and Python.

What additional resource does Code Studio provide for interview preparation?

Code Studio provides over 600 interview experiences from companies like Amazon, Microsoft, Adobe, and Google.

What is the first recursion problem discussed in the video?

The first recursion problem discussed is to print a name 'n' times using recursion.

What is the base case for the 'print name n times' recursion problem?

The base case for the 'print name n times' problem is when 'i' exceeds 'n', at which point the function returns and stops the recursion.

How does the video explain the concept of changing parameters in recursion?

The video explains changing parameters by demonstrating how to modify the function call to 'f(i + 1, n)' after printing the name, to continue the recursion until the base case is met.

What is the time complexity of the 'print name n times' recursion problem?

The time complexity of the 'print name n times' recursion problem is O(n), as the function is called 'n' times.

What is the space complexity of the 'print name n times' recursion problem?

The space complexity of the 'print name n times' recursion problem is also O(n), due to the stack space used by each recursive call waiting to be completed.

How does the video introduce the concept of backtracking in recursion?

The video introduces backtracking by not allowing the use of 'i + 1' and instead using 'i - 1' to print numbers from 'n' to '1', demonstrating how the print statement can be executed after the recursive call.

What is the challenge posed by the video for the viewers at the end?

The challenge posed by the video is to print numbers from 'n' to '1' using recursion without using 'i - 1, n' as the recursive call, and to share the solution in the comment section.

Outlines

00:00

🎥 Introduction and Sponsor Acknowledgement

The script starts with the host expressing gratitude to the sponsor, Code Studio, which offers a platform for practicing interview problems in various programming languages like C++, Java, and Python. The host highlights the platform's extensive library of over 2000 problems and guided paths for different programming topics, including Python, DBMS, OOP, OS, computer networks, system design, and web development. Additionally, the host mentions the availability of top company interview questions and shared experiences from interviews at companies like Amazon, Microsoft, Adobe, and Google. The host then invites viewers to check out the free resources for interview preparation provided by Code Studio, with a link in the video description. The video's main content is introduced as a continuation of a recursion playlist, focusing on basic recursion problems, and the host encourages viewers to watch the previous video for foundational knowledge before proceeding.

05:04

📚 Recursion Problem: Print Name N Times

The host delves into the first recursion problem, which involves printing a name N times using a recursive function. The explanation begins with a base case scenario where the function stops if the printed count exceeds N. The function is defined with parameters 'i' and 'n', starting from 1 and going up to 'n'. The host illustrates the recursive process with an example where 'n' is set to 3, demonstrating how the function calls itself with incremented 'i' values until it reaches the base case. The explanation includes a step-by-step breakdown of the function calls and prints, leading to the final output. The host also discusses the time and space complexity of the problem, concluding that both are O(N) due to the number of function calls and the stack space used during recursion.

10:07

🔢 Recursive Sequence Printing: 1 to N and N to 1

The host moves on to the next set of problems, which involve printing numbers linearly from 1 to N and then in reverse from N to 1 using recursion. The explanation for printing from 1 to N follows a similar recursive pattern as the previous problem, with the base case being when 'i' exceeds 'n'. The host then challenges the viewers to adapt the approach to print from N to 1, starting with 'i' equal to 'n' and decreasing it with each recursive call. The host provides a detailed explanation of how the function should be structured to achieve this, emphasizing the change in the recursive call from 'i + 1' to 'i - 1'. The examples given help clarify how the reverse order is achieved through recursion.

15:08

🔄 Backtracking in Recursion: Printing in Reverse Order

The host introduces the concept of backtracking in recursion, a technique used when the problem requires printing or processing in a reverse order without using the typical increment or decrement approach. The host presents a scenario where the print statement is placed after the recursive call, ensuring that the last call is executed first. This is demonstrated with an example where the function starts with 'i' equal to 'n' and decreases 'i' with each call, but the print statement is executed after the recursive call returns. The host walks through the execution flow, explaining how this approach allows for printing in increasing order even when starting from the highest value and recursively calling with decreasing values. The explanation includes a visual representation of the recursion tree, illustrating the order of function calls and prints.

20:11

🌟 Conclusion and Future Discussion

In the concluding part of the script, the host summarizes the problems discussed in the video, which include printing a name N times, printing numbers linearly from 1 to N and in reverse, and using backtracking to print in reverse order. The host encourages viewers to attempt a related problem as an exercise, hinting at a challenge to print from N to 1 without using the straightforward decrement approach. The host then invites viewers to like the video, subscribe to the channel if they are new, and check out the Striver SSD sheet linked in the description. The video wraps up with a reminder to stay tuned for the next video, which will cover more interesting recursion problems.

Keywords

💡Code Studio

Code Studio is mentioned as the sponsor of the video and a platform for practicing interview problems. It is defined as a resource with over 2000 problems and solutions in various programming languages such as C, Java, and Python. It is related to the video's theme as it provides guided paths for different programming topics and interview preparation, which is the main focus of the video content.

💡Recursion

Recursion is a fundamental concept in programming and the central theme of the video. It is defined as a process where a function calls itself as a subroutine. In the video, recursion is used to solve basic problems like printing a name or numbers in a sequence using a function that calls itself with modified parameters.

💡Base Case

The base case in recursion is a condition that stops the recursive calls and is crucial for avoiding infinite loops. In the video, the base case is used to determine when to stop the recursive function calls, such as when the counter variable exceeds a certain value, ensuring the function terminates after printing a name a specified number of times.

💡Recursive Function Call

A recursive function call is when a function calls itself within its own definition. In the script, the recursive function call is demonstrated with examples such as printing a name 'n' times or printing numbers from 1 to 'n'. The function call 'f(i+1, n)' or 'f(i-1, n)' is used to illustrate the recursion process.

💡Backtracking

Backtracking is a form of recursion where the function call is made first, followed by the execution of the print statement. It is introduced in the video as a technique to print numbers in a sequence starting from 'n' and decreasing to 1. The script uses the term to describe a different approach to recursion where the print statement is placed after the recursive call.

💡Time Complexity

Time complexity in the context of the video refers to the measure of how long an algorithm takes in terms of the amount of input. It is mentioned when discussing the efficiency of recursive solutions, with the video stating that the time complexity for the demonstrated recursive algorithms is O(n), indicating a linear relationship with the input size 'n'.

💡Space Complexity

Space complexity is the measure of the amount of memory an algorithm uses in relation to the input size. In the video, space complexity is also discussed as O(n) for the recursive algorithms, reflecting the stack space used by each recursive call until the base case is reached.

💡Interview Preparation

Interview preparation is a key theme in the video, as the script discusses using Code Studio for practicing coding problems that are often encountered in technical interviews. The term is used to highlight the practical application of the discussed recursion concepts in real-world scenarios such as job interviews at top companies.

💡Top Company Questions

Top company questions refer to the specific coding and technical questions that candidates might encounter during interviews with leading tech companies. The video mentions that Code Studio provides access to such questions, particularly for companies like Amazon, tagged and solved in multiple programming languages.

💡Guided Paths

Guided paths in the video refer to structured learning routes provided by Code Studio for various programming topics. These paths are designed to help users systematically prepare for technical interviews, covering areas such as Python, DBMS, object-oriented programming, operating systems, and more.

Highlights

Introduction of Code Studio as the sponsor of the video, offering over 2000 interview problems and solutions in C, Java, and Python.

Guided paths available for various programming topics including Python, DBMS, OOP, OS, computer networks, system design, and web development.

Access to top company interview questions and solutions, specifically mentioning Amazon coding questions.

Feature of reading interview experiences from companies like Amazon, Microsoft, Adobe, and Google.

Emphasis on the importance of watching the previous video on recursion before starting this lecture.

Explanation of solving basic recursion problems, starting with printing a name 'n' times using recursion.

Demonstration of a change of parameters in recursion by using integers 'i' and 'n' without global variables.

Illustration of the recursion process with a step-by-step example of printing a name 'n' times.

Introduction of time complexity and space complexity concepts in the context of recursion.

Solving the problem of printing numbers linearly from 1 to 'n' using recursion.

Approach to print numbers in reverse order from 'n' to 1 using recursion with a base case of 'i' less than 1.

Introduction of backtracking in recursion with an example of printing numbers from 'n' to 1 without using 'i + 1'.

Explanation of how to print numbers from 1 to 'n' by starting from 'n' and using backtracking.

Challenge to the audience to solve a recursion problem without using 'i + 1' and to share their solutions in the comments.

Visualization of the recursion process as a tree to understand the flow of function calls and returns.

Conclusion of the video with an invitation to like, subscribe, and check out the provided resources for further learning.

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

so today will be the lecture two of

recursion playlist which is basic

recursion problems now in the previous

video we did learn about recursion in

depth what is like so please make sure

you watch out the previous video

and after that only you start this video

so in this video we are going to solve

uh some problems the first one being a

print name five times i'm assuming you

can do that

print uh

linearly from one to n using recursion

definitely

print linearly from n to one then print

linearly from one to n but in

some backtracking over here i'll teach

you how can you do stuffs

uh using backtrack kind of backtrack

and print from end to one again using

back cracking okay so

i'm assuming you can do the first three

but still i'll recommend you to watch

the entire video because

the concepts gets more clear the more

you watch the videos so let's uh take

the first problem and do it that is uh

print name

n times let's keep it n times okay so

the generic way is definitely uh

to run a for loop and print the name n

times but i want you to print your name

n times using recursion yes that's

that's a catch here using recursion

so how can you do this

you know there will definitely be a main

which will uh be calling print

okay so i'm saying n times so what you

can do is you can take the n from the

user

yes you can take the n from the user

so

input as n in java it will be integer

dot parsi and n

and then you can say a function

with

uh probably 0 and n so over here i'm

gonna teach you

something which is very important uh one

and then so this is the first time and

i'm saying till new printed okay okay

i'm gonna teach you something

change of parameters which is very

important so i'm writing a void f okay

no global variables this time i'm taking

an integer i

and i'm taking an integer n

okay

over here i know the base cases

if i start from yes if i start from 1

i have to go till n that's for sure

like i have to print it n times so i

know the base case is definitely going

to be till i haven't printed n times

so if at any moment i

exceeds n

i am going to say return because

i'm going to just print it n times

that's very simple

uh coming from the previous class it's

very very simple this is what we call it

as the base case

remember

so base case is decided on the problem

statement so this is the base case

okay

what after that

after that i will be like okay let's

print it so you will simply say print

let's assume my name is raj so i'll

print raj

and then i'll call f

i've printed it once i did came up as

one so the next time i will call it as

i plus one comma n okay

so let's understand how does the flow

works so that you get a better

perspective

so initially uh you will be taking

integer n

assume n is given as 3 assuming n is

given as 3 and again i'll put the output

screen over here

assuming n is given as 3

so n becomes 3

function says 1 and n

so this guy calls this particular guy

with i's value as 1 n's value as 3 so

the function call yes the first function

call that you make is of

f of 1 comma 3 that's the first function

call you made

is the base case true no because

1 is not greater than three

one is not greater than three no

thereby you say print raj so raj gets

printed okay next you're saying function

of i plus one so this guy calls a

function with i plus 1 i was

1 over here i gets incremented by 1 and

calls the function by

2 and n is still 3 and over here you

write the same line of code i greater

than n

because it's the same function which is

being called so in memory it's the same

one

print raj

and

then f of i plus one comma n

okay

this time let's understand if this base

case is executed i is 2

n is 3 so this will not be executed

print raj

again you print raj

right remember this function of 1 of 3

called this f 2 3 so in recursion tree

it will be f of 2 comma 3

this is how you create the recursion

tree now f of 2 3 this is printed

and now this portion so this guy goes

and again calls f of i plus 1 so 3 comma

3 and again you write the same lines is

i greater than n

then you say return

definitely uh this is false so thereby

you again go and say

print raj

and is f of

i plus 1 comma n

so this is false so this gets executed

so raj is again printed

f of i plus 1 so this time f like f of 2

3 called f of 3 3

so i can just

draw that f of 2 3 called f of 3 3.

now f of 3 3

calls

i plus 1 which is f of 4 comma 3

and this moment i can say if i greater

than n then return becomes true

why because because

i is4

n is 3 and this guy comes out to be true

thereby you are returning so the moment

you're returning these lines will be of

no use anymore these lines will be of no

use anymore so you return now this is

done now remember f of 3 3 called f of 4

3 so you can do it in the recursion tree

as well f of 3 3 called f of 4 3 okay

so

this is done

this is over so i can say this function

is over thereby you can return

this is done so this function is over

there by this is over you can return

thereby this is over you can definitely

return back to where it was called

and now the function

the program terminates so this is how

easily the recursion did work and we did

it in the parameters and not using any

global variables so i was able to print

my name n number of times is i was able

to print my name n number of times and

at f of 4 3 i returned so this got

completed this return so this got

completed this return so during the

course this guy printed one raj this guy

printed one raj this guy printed one raj

and this guy hit the base condition and

returned so this is how you can easily

uh do the first problem which is print

the name

n times using recursion

right i hope you have understood this

so

if i talk about the time complexity uh

space complexity it's very very simple

i can say the time complexity uh to be

big o of n

because inside the functions yes inside

the functions uh these lines

are like we go off one like they don't

take any time so apparently uh you're

calling one function

that guy calls one more function that

guy calls one more function so you're

calling n functions if you carefully

observe

one two three four so you're calling n

functions like here about n functions so

i can say the time complexity to be big

o of n yes i can say the time complexity

to be b co of n

and what is the stack space so in space

complexity we generally assume the stack

space now this guy would have been in

the stack

when you called

f of 1 comma 3 would have been in the

stack then f of 2 comma 3 would have

been in the stack then f of 3 comma

three would have been in the stack so

they were they were waiting in the stack

till this base case returned they were

waiting to be completed so thereby i can

say the space complexity is also big o

of n now this space complexity is

hypothetical like you're not using an

array internal the computer's internal

memory uses the stack space so thereby

making the time complexity and the space

complexity to be big o of n and b go

often i hope that makes sense

so guys we have done the first problem

which is print the name ten times or

five times okay now let's do the next

problem which is print linearly

from one

to n

so basically if n is given as four i

want you to print one two three four yes

this is what i want as the output

okay so how will you do this again very

much similar to the previous problem if

i write down the function it's going to

be i comma n and it's going to be i

greater than n

and you are saying return

and this time the print statement will

be executing i

and then you can call f of i plus 1 and

is a similar one just in place of the

name you can print i

right so that in the main yes so that in

the main

when you call the function like you can

take the input of n

you can take the input of n and then

when you call the function with one

comma n

first time

prince

i which is

one next time goes

i plus one so two similarly you can just

go on printing till whatever your n is

so it was quite similar to the previous

one where i'm easily able to print

one

to n correct now it's a time to uh think

it in the reverse order and do the next

problem which is

print

in the opposite fashion print in

uh terms of

n to one

so

like if i give you n equal to 4 you're

going to print me 4 3 2 1. now can you

do this can you do this i think you can

yes you can uh it's very simple

as of now the code that we wrote started

from i equal to 1 and then you did i

plus 1 then you did again i plus 1 and

you kept on calling so if i'm if i have

to print from 4 i can understand that

the first

i has to be 4

and the last has to be a one

after one

before one you don't print so i can say

i'll just write the function

in the opposite order it's going to be

same i comma n

but this time it's going to be if i

becomes

lesser than 1 then i don't need to print

and i can print the i

and this time i can call it i minus 1

comma n

and during the start yes i repeat during

the start of main

i can take the input of n definitely

i can take the input of n

and i can say f of n comma n to be

called yes i can say f of n comma n to

be called so that if if assume n is

given as 4

the first time or assume the n is given

as 3 to have a better understanding

the first time you call it three comma

three and this goes

calls it like

three comma three correct

this line doesn't executes

print three so the output screen will

definitely have something like three and

then you call it as f of two comma three

and again then you will call it as f of

one comma three and again at the end

you'll call it f of zero comma three and

this 0 comma 3 will be executed and

you'll come back you'll come back and

you'll come back so automatically you

print 3 2 1

as simple as that so it's the main stuff

is you just change it over here where do

you say i'm going to do a i minus 1

this is the main step where you change

that you say i'm going to do a i minus 1

correct so again we have also done the

next problem which is print in terms of

n

is

to

one

so three problems have been done

now

these were very basic i want to do i

want you to change it and think it in

the reverse order

what if i

want to print from 1 to 1 but i don't

want to do i plus 1 instead i say that

the recursion call starts from n comma

and usually like uh to give a better

brief

let me just explain i am saying print

from 1 to n

print from 1 to n

but i am not going to allow you

to use

plus 1 like generally from 1 to n was

meaning f of i plus 1 comma n was the

function call was the recursive function

call that you are making i'm not

allowing you to do that i'm not allowing

you to do plus one so how will you do

this

so over here i'm going to teach you

something as backtracking okay so let's

understand backtracking

since i'm not allowing you to use plus

you have to use minus so what i'll do is

i comma n okay as usual this time it'll

be like if i at any time goes lesser

than one

uh you return

f of i minus one comma n

and right after that i'm writing print

of

i okay

so over here i'm writing the main

function

over here i'm writing the main function

and

what i'm writing is okay mean

let's take the input of n

and let's call f of n comma n

so basically what i did was i said that

you cannot use this plus thereby

you can use minus one

why because i wanted to i wanted you i

wanted me to teach you

what if i write the print line after the

recursion call what happens let's

understand so again let's uh quickly

give the output screen

and uh assume n is given as three so the

first call is 3 comma 3 thereby the

first call goes as

3 comma

3 the first call goes as 3 comma 3 now

let's understand this does this line

execute i lesser than 1 no because

i is 3 and it doesn't executes

perfect

next

i am saying f of i minus 1

so this function call will go remember

this

the print line will not be executed

the function call will go perfect let's

call the function call and i'm saying i

minus 1 that's 2 comma 3

and again let's write if i is lesser

than 1 then return

let's say f of i minus 1 comma n

and then let's write the print of i

and then this okay so let's see if the

first line executes again no because i

is 2

this time again you call the function

with i minus 1 which is 2 minus 1 1 1

comma 3

and this time you write if i is lesser

than 1

you return

and you say f of i minus 1 comma n

print off i

okay

let's see what happens this time

f of one comma three

i is one doesn't executes

f of i minus one

goes and calls this with f of i minus

one means zero comma three

if

i lesser than one return i'm not writing

the remaining couple of lines

i is zero so this line this time is

indeed true

is indeed true and if this line

is

true what happens

you basically say return executes so you

return

so this function line has been executed

correct now the print comes over here

because after this

the line of execution comes over here

and it says print i

what's the value of i

one so the output will be one

next

the execution line comes over here which

means the function has been executed

correct

go back

went back

this line has been executed

thereby the function line comes to the

next

this print is i what's the value of i do

print it

next the line of execution goes here

which means this function has been

executed go back

this line this has been executed you go

to the next print i i's value is 3

thereby this line has been executed

go here

hence go back

so

even by

starting from 3

even by starting from 3

i was able to output

in the linearly increasing order so it's

not necessary that you have to start

from

1 in order to print from one two three

you can start from the back and you can

do the task after the function call so

basically

by doing this what you did was you made

it mandatory that

this line this print line is executed at

the first

because you kept it after the function

call you kept it after the function call

so

unless until this function call is over

this line would have never been executed

so you made sure the last guy has been

executed first

why how did you make sure that the last

guy because this was the last guy has

been executed first how was this

function completed first by making sure

the print line is after the function

call because this will only be executed

if the base case is true thereby this

gets executed this then then this gets

executed then this that's the opposite

way you made it by writing after the

function

got it so this is how you print from

one is to n now i will be asking you to

do the other one so this is what i've

done but by backtrack

this has been done i want you to do the

other way

i want you to print from end to end

basically if i give you as n equal to

3

i want you to print 3 to 1 but i don't

want you to use

this i minus 1 comma n i don't want to

do i don't want you to use this okay so

i'm not solve this i want you people to

answer in the comment section about this

let's see if you have understood the

entire concept you should be able to do

it

yes you should be able to do it so

remember uh

if i write this as a recursion tree it's

very simple you started with f of three

comma three then you went to f of two

comma three then you went to f of one

comma three then you went to f of uh

zero comma three which indirectly stated

a mover

then the print line executed of one

then you said

after this the print of two was executed

and right at so this the print of three

was executed so this is how the

recursion tree will look like for this

particular stuff

so i hope guys you have understood all

the problems and you have understood the

recursion in depth for the basic kind of

problems of one 1d recursion so just in

case you did please please please make

sure you like this video and if you're

new to this channel please do consider

subscribing and yeah if you haven't

checked out our striver ssd sheet the

link is in the description please make

sure to check it out with this let's

wrap up this video and meet in the next

one where i'll be discussing some other

interesting problems bye

don't ever forget your golden