Recursion in 1 Shot || Beginners Guide

[Cricket-Memories-With-Akshay]

Hello Love Bhiya, errors I find after watching this video are following:

1. 16:20 Tail Recursion
TC: O(n)
SC: O(n) used in recursion stack



2. 17:30 Head Recursion
TC: O(n)
SC: O(n) used in recursion stack



3. 23:20
TC: O(n)
SC: O(n) used in recursion stack



4. 30:00 Before Optimization
TC: O(2^n)
SC: O(n)
used in recursion stack
Can be optimize using DP and can be done with an iterative method.

int fibonacci (int n)
{
int dp[n + 1];

dp[0] = 0;
dp[1] = 1;
for(int i = 2; i < n + 1; i++)
{
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
TC of above code: O(n)
SC of above code: O(n) - dp array



5. 39:40
TC: O(n)
SC: O(n)
used in recursion stack + O(1) for mapping the number to its respective names( like 4 - 'four'). Hence, effective space complexity will be O(n)
where n is length of number



6. 46:50
TC: O(log(n))



7. 54:50
TC: O(n)
SC: O(n)


8. 1:02:00
TC: O(2^n)
SC: O(n)



9. 1:10:00
TC: O(3^n)
SC: O(n)



10. 1:15:00
TC: O(2^n)
SC: O(n)



11. 1:20:00
TC: O(n*n!)
SC: O(n)



Thank You for this video!

[siddharthsingh]

Thanks love babber Bhaiya
16:25 Tail Recursion TC: O(N) and SC: O(N)
17:36 Head Recursion TC: O(N) and SC: O(N)
21:44 TC: O(N) and SC: O(N)
30:02 Before Optimisation TC: O(2^N) and SC: O(N)

Yes, It can be Optimize with Dynamic Programming and can be done with an iterative method.
Code using DP:
int Fibo(int n, int dp[])
{
if(n<= 2) return 1;
//base case
if(dp[n] != -1) return dp[n]; // if already called and stored in dp then return value in Dp


return dp[n] = Fibo(n-1, dp)+Fibo(n-2, dp);
}
After Optimisation using DP, TC: O(N) and SC: O(N)
39:43 T.C: O(number length) and S.C: O(number length)
46:52 TC: Log(n)
54:52 T.C: O(n) and S.C: O(n)
1:02:14 Subset TC: O(2^N) and SC: O(N)
1:11:11 TC: O(3^N) and SC: O(N)
1:15:15 TC: O(2^N) and SC: O(N)
1:26:20 TC: O(N*Log(N)) and SC: O(N)

[abhishekdhok]

//I hope this will helps. Correct me if I am wrong
16:20 => example of head recursion
time complexity : O(n)
space complexity : O(n)

23:31 : factorial program
time complexity : O(n)
space complexity : O(n)

30:09 => fibonacci sequence
time complexity : O(2^n) => yes we can optimize this time complexity using dp as it is so many overlapping subproblems.
space complexity : O(n)

38:06 => printspell
time complexity : O(n)
space complexity : o(2n)

44:32 => fast exponentiation
time complexity : O(logn)
space complexity : 0(logn)

54:48 => sorted or unsorted
time complexity : O(n)
space complexity : O(n)

1:00:34 => power set
time complexity : O(2^n)
space complexity : O(n)

1:10:24 => staircase problem
time complexity : O(3^n) i am not sure
space complexity : o(n)

1:14:51 => print all subsequences
time complexity : O(2^n)
space complexity : O(n)

1:26:31 => print all permutations
time complexity : O(n*n!) => I used google to find this.
space complexity : O(n)

1:29:02 => total ways to reach destination
time complexity : it is also exponential but we can also solve this type of problem using bfs..
space complexity : O(n)

Thank You!!!.

[raghavarora]

16:25 Tail Recursion ( when processing comes before the recursive call )
17:37 Head Recursion (when call comes before processing)
23:33 T.C - O(n) S.C - O(n)
30:04 T.C - O(2^n) S.C - O(n)
We can optimise using iterative method
(Then we can do this in linear time and no stack space required)
39:44 T.C - O(length of number) and S.C - O(length of number )
46:54 Fast Exponentiation TC - Log(n)
54:50 T.C - O(n) S.C - O(n)
1:02:15 Subset question TC - O(2^N) SC - O(N)
1:11:10 Max 3 jump question ( TC - O(3^N) SC- O(N))
1:15:17 Subsequence Question ( TC - O( 2^N ) SC - O(N) )
1:26:20 Permutations (TC - O(N*Log(N)) SC - O(N)
1:31:30 Source To Destination ( TC- O(2^(n^2)) SC -O(n^2). 
Done Bhaiya 🔥🔥.
Thank you for this Awesome Video 🎉❤️

[Lakshmi_Prasanna]

16:19 Tail recursion as the recursive function is the last thing that is executed in the function the statement are
cout<<n;
Print(n-1);
Time complexity:O(n) as the function calls itself for n times
Space complexity: O(n) the depth of stack or the maximum size of the stack is n
17:39 Head recursion as there are statements to be executed after the recursive function call
Print(n-1);
cout<<n;
Time complexity:O(n)
Space complexity:O(n)
23:28 Time complexity of factorial :O(n)
Space complexity:O(n)
30:04 for Fibonacci series Time complexity: O(2^n) As the no of function calls for n th term are 2^n
Space complexity:O(n)
It can be optimised to O(n) using memoization by iterative method
39:41 Time complexity: O(logn) the function calls for log(ceil(n))
Space complexity:O(logn) for number spell problem

[Live-hhli]

Method to find time and space complexity of Recursion:
Time complexity = No of levels of recursion tree * Work done at each level
Smjhte hai
Jese lo print n numbers
Ab isme apn hr level p O(1) ka kam kr rhe hai
Aur isme level hogi n+1
Toh iski time complexity ho gyi O(n)
Thoda complex example lete hai ab
Stair wala problem
Isme agr apn recursion tree dekhe toh apn ek node k lie 3 recursive call kr rhe hai
Mtlb ki hr level p nodes bdhte ja rhe by a factor of 3
Pehle me 1 fir 3 fir un 3 ke 9
Aur levels kitni hai?
At max n
And ek node p O(1) ka work hai
Toh total work
1 + 3 + 9
Toh iski complexity hogi O(3^n)
Agr koi recursion me apn kuch choice kr rhe hai toh uski time complexity hoti hai
O(choice^n)
Jese agr stairs me 1 2 3 ki jagah agr sirf 1 2 hota toh complexity O(2^n) hoti

Ab bat krte hai Space ki:
Toh recursion me space complexity hoti hai depth of deepest recursion tree brach
Smjhte hai isko
Jese ki apn n number print kr rhe the
Toh usme deepest tree ek hi thi
Aur woh n tk ja rhi thi
Isliye space hogi O(n)
Thoda complex example lete hai
Stair wala problem
Agr usme ap hr bar 1 steps lo
Toh recursion tree kafi lmbi bn jaegi
Uski height hogi n joki size of stairs hai.
Isliye O(n) space complexity

How recursion works actually?
Jb apn recursion call krte hai tb
Sbse pehla joh call hota hai woh base case tk chlta rehta hai
Fir woh khatam hota hai
Uske bad dusra call execute hota
Isliye hm space complexity ko height of deepest branch lete hai
Kyoki isse jyada time hoga nhi
And ek tree ka brach khatam hone k bad uska space empty ho jata hai
Jisse dusre recursive calls use krte hai

I think now you can answer all 11 questions which are given by bhaiya

Koi doubt ho toh you can comment

[dipanshugupta]

Question 1: Get Counting
16:55 Tail Recursion TC: O(N) and SC: O(N)
17:36 Head Recursion TC: O(N) and SC: O(N)

Question 2: Factorial
21:44 TC: O(N) and SC: O(N)

Question 3: Fibonacci
30:02 Before optimization TC: O(2^N) and SC: O(N)
Optimized code:
int Fibo(int n, int dp[])
{
//base case
if(n<= 2) return 1;

// if already called and stored in dp then return value in DP
if(dp[n] != -1) return dp[n];
return dp[n] = Fibo(n-1, dp)+Fibo(n-2, dp);
}
TC: O(N) and SC: O(N)

Question 4: Print Spelling
39:35 TC: O(N) and SC: O(N)

Question 5: Exponent
39:55
Before optimization: TC: O(N) and SC: O(1)
After optimization: TC: O(logn) and SC: O(1)

Question 6: Sorted or Unsorted
47:00
TC: O(N) and auxiliary space: O(N)

Question 7: Subsets
56:30
TC: O(N*(2^N)) and SC: O(N)

Question 8: Stair Problem
1:03:00
TC: O(3^N) and SC: O(N)

Question 9: Subsequence
1:11:47
TC: O(2^N) and SC: O(N)

Question 10: Permutation
1:16:00
TC: O(N*N!) and SC: O(N)

Question 11: Source to destination
1:26:10
TC: O(4^(m*n)) and SC: O(n*m)

[shikhershukla]

16:25 (5 4 3 2 1)head recursion as the printing is done before the recursive call
Time complexity - O(n) Space complexity - O(n)
17:25 (1 2 3 4 5)tail recursion as the printing is done after the recursive call
Time complexity - O(n) Space complexity - O(n)
23:40 (factorial) Time complexity - O(n) Space complexity - O(n)
29:50 (fibonacci) Time complexity - O(2^n) Space complexity - O(n)
We can optimize the approach(not using recursion) by storing the previous two numbers in variables and summing them to get the nth term.
39:30 (spelling numbers) Time complexity - O(n) Space complexity - O(n)
46:50 (expenontation) Time complexity - O(log n) Space complexity - O(log n)
54:50 (sorted or unsorted) Time complexity - O(n) Space complexity - O(n)
for unsorted arrays calls will be less than n but this is worst case complexity that is when the array is sorted and it will traverse all n elements
1:02:30 (subset) Time complexity - O(2^n) Space complexity - O(n)
the loop returns 2^n subset for every n input array
1:11:00 (Ways to reach Nth stair by jumps) Time complexity - O(3^n) Space complexity(n)
1:15:20 (subsequence of a string) Time complexity - O(2^n) Space complexity - O(n)
This question can be done using bit masking also
1:26:25 (permutaions of a string) Time Complexity - O(n*n!) Space complexity - O(n)
Thank you so much bhaiya this really helped me a lot

[manjarigoyal]

If u are looking for dsa playlist then u came at right channel. I've watched many videos of different playlists but couldn't find that much beginner friendly videos. He has taught in a very better way.

[bilalahmadmujaddadi]

Whenever i stuck somewhere this man comes up with the solution ❤

[shefalimishra]

16:20
Tail Recursion
Time Complexity: O(n)
Space Complexity: O(n) used in recursion stack

17:30
Head Recursion
Time Complexity: O(n)
Space Complexity: O(n) used in recursion stack

23:20
Time Complexity: O(n)
Space Complexity: O(n) used in recursion stack

30:00
Before Optimization
Time Complexity: O(2^n)
Space Complexity: O(n)
used in recursion stack
Can be optimize using DP and can be done with an iterative method.

int fibonacci (int n)
{
int dp[n + 1];

dp[0] = 0;
dp[1] = 1;
for(int i = 2; i < n + 1; i++)
{
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}

The above code has a space complexity of O(n) and time complexity of above code is O(n)

We can further optimize it to space complexity of O(1) with the following code:
int fibonacci (int n)
{
int a = 0;

int b = 1;
for(int i = 2; i < n + 1; i++)
{
int temp = b;
b = a + b;
a = temp;

}
return b;
}

39:40
Time Complexity: O(n)
Space Complexity: O(n)
used in recursion stack + O(1) for mapping the number to its respective names( like 4 - 'four'). Hence, effective space complexity will be O(n)
where n is length of number i.e. number of digits

46:50
Time Complexity: O(log(n))

54:50
Time Complexity: O(n)
Space Complexity: O(n)


1:02:10
Time Complexity: O(2^n)
Space Complexity: O(n)

1:10:00
Time Complexity: O(3^n)
Space Complexity: O(n)

1:15:00
Time Complexity: O(2^n)
Space Complexity: O(n)

1:20:00
Time Complexity: O(n*n!)
Space Complexity: O(n)

[saifahmedkhan]

16:23 Tail Recursion (bcz, we make a recursive call at the end of func.) Time and Space Complexity = O(n)
17:34 Head Recursion (bcz, we make a recursive call at the starting of func.) Time and Space Complexity = O(n)
23:22 Time and Space Complexity = O(n)
29:56 Yes, we can do with dynamic programming (Time Complexity = O(n^2), Space Complexity = O(n))
39:40 Time and Space complexity = O(n)
46:56 Fast Exponentiation (Time complexity = log(n))
54:51 Time and space complexity = O(n)
1:02:15 Subset (Time complexity =O(2^n) and Space Complexity = O(n))
1:11:09 Max 3 ( Time Complexity = O(3^n) and Space Complexity = O(n))
1:15:19 Sub sequence ( Time Complexity = ( 2^n) and Space Complexity - O(n) )
1:26:22 Time Complexity = O(n*Log(n)) and Space Complexity - O(N)
1:31:33 Time =O(2^(n^2)) Space Complexity =O(n^2)
Homework completed Bhaiya
Thank u @love Babbar bhaiya for this amazing video
Your videos really help a lot.

[piyushsonkar]

16:22 Tail Recursion is used ( when processing comes before the recursive call )
17:33 Head Recursion is used (when call comes before processing)
23:27 T.C - O(n) S.C - O(n)
30:09 T.C - O(2^n) S.C - O(n)
We can optimize it using iterative method
i.e. we can do this in linear time and hence we do not need any space


39:39 T.C - O(length of number) and S.C - O(length of number )
46:49 Fast Exponentiation Tc - Log(n)
54:47 T.C - O(n) S.C - O(n)
1:02:17 Subset question TC - O(2^N) SC - O(N)
1:11:10 Max 3 jump ( Tc - O(3^N) SC- O(N))
1:15:12 Subsequence Question ( Tc - O( 2^N ) SC - O(N) )
1:26:24 Permutations (Tc - O(N*Log(N)) SC - O(N)
1:31:33 Source To Destination ( TC- O(2^(n^2)) SC -O(n^2).

[amaanansari]

16:22 Tail Recursion
Time Complexity: O(n) Space Complexity: O(n)


17:40 Head Recusion
Time Complexity: O(n) Space Complexity: O(n)


23:20 Time Complexity: O(n) Space Complexity: O(n)


29:54
With recursion, its Time complexity would be O(n^2) and space complexity O(n)
It can be done using the iterative method with Time complexity of O(n) and space complexity O(1).


39:40
Time Complexity: O(n) Space Complexity: O(n)
n= length of number


46:47
Time complexity O(log(n))


56:30
void PowerSet(char *set, int size)
{
unsigned int pow_size = pow(2, size);
int counter, j;
for(counter = 0; counter < pow_size; counter++)
{
for(j = 0; j < size; j++)
{
if(counter & (1 << j))
cout << set[j];
}
cout << endl;
}
}


1:02:10
Time Complexity: O(2^n) Space Complexity: O(n)
1:10:50
Time Complexity: O(3^n) Space Complexity: O(n)
1:15:15
Time Complexity: O(2^n) Space Complexity: O(n)
1:16:30
Time complexity: O(n*n!) Space complexity: O(n)

[tusharnain]

You teach far better then Apna College C++ classes, You nailed it.

[parikshitrathore]

---16:23 Tail Recursion (printing first, then Calling our Recursive Function) [T.C O(n) & S.C O(n)]

---17:37 Head Recursion ( first calling our Recursive Function And Then Printing) [T.C O(n) & S.C O(n)]

---23:22 T.C O(n) & S.C O(n)

---30:05 T.C O(2^n) & S.C O(n)
Optimization Using Iteration

#include <iostream>
using namespace std;

int main()
{
int n;
cin>>n;
int num1 =0;
int num2 =1;
int answer =0;
for ( int i = 2; i <= n; i++)
{
answer = num1+num2;
num1 = num2;
num2 = answer;
}
cout<<answer;
}

---39:44 T.C - O(length_of_number) and S.C - O(length_of_number )

---46:50 T.C O( log(n))

---54:50 T.C O(n) & S.C O(n)

---1:02:10 Subset T.C O(2 ^ n) & S.C O(n)

[keshav_jha_]

Finally i have completed this whole video and saare questions k answers mene notepad me likhte ja raha tha ab me yaha paste kar de raha hu.
16:24 tail recursion hai ye wala
17:35 head recursion h ye
23:32 Time Complex - O(n) S.C - O(n)
30:06 Time Complex - O(2^n) S.C - O(n)
iterative method se optimize ho sakta h

39:45 Time Complex - O(length of number) and S.C - O(length of number )

46:53 Fast Exponentiation TC - Log(n)
54:50 T.C - O(n) S.C - O(n)
1:02:15 Subset Question hai ye TC - O(2^N) SC - O(N)
1:11:10 Max 3 jump question ( TC - O (3^N) SC- O(N))
1:15:16 Subsequence question ( TC - O ( 2^N ) SC - O(N) )
1:26:21 Permutation (TC - O(N*Log(N)) SC - O(N)
1:31:31 Source To dstination ( TC- O(2^(n^2)) SC -O(n^2).

Rcursion pura samjhane k lie thanku bhaiya;

[ritikhooda]

16:20 => example of head recursion
time complexity : O(n)
space complexity : O(n)

23:31 : factorial program
time complexity : O(n)
space complexity : O(n)

30:09 => fibonacci sequence
time complexity : O(2^n) => yes we can optimize this time complexity using dp as it is so many overlapping subproblems.
space complexity : O(n)

38:06 => printspell
time complexity : O(n)
space complexity : o(2n)

44:32 => fast exponentiation
time complexity : O(logn)
space complexity : 0(logn)

54:48 => sorted or unsorted
time complexity : O(n)
space complexity : O(n)

1:00:34 => power set
time complexity : O(2^n)
space complexity : O(n)

1:10:24 => staircase problem
time complexity : O(3^n) i am not sure
space complexity : o(n)

1:14:51 => print all subsequences
time complexity : O(2^n)
space complexity : O(n)

1:26:31 => print all permutations
time complexity : O(n*n!) => I used google to find this.
space complexity : O(n)

1:29:02 => total ways to reach destination
time complexity : it is also exponential but we can also solve this type of problem using bfs..
space complexity : O(n)

[shivamsahu]

Thank You Bhaiya for making this video. this video really helped me.
Here are my answers to all the questions. And Guys Please share this video to helps others people.

Q1
16:25 => it is a Tail recursion. because processing(work) occurs before the recursive call.
TC: O(N) and SC: O(N) --> space taken by stack mem.

17:32 => it is a head recursion. because here recursive call comes before others processing in the function.
TC: O(N) and SC: O(N) --> space taken by stack mem.

Q2
23:26 => Factorial problem TC: O(N) and SC: O(N) -->space taken by stack mem.

Q3

30:02 => Before Optimisation of Fibonacci Problem TC: O(2^N) and SC: O(N)
-->space taken by stack mem.
Yes, it can be optimized by using Dynamic Programming and iterative method.
iterative method: ( TC: O(N) and SC: O(1))
int fib(int n)
{
int a = 0, b = 1, c; //creating a, b variable to maintain previous two fib numbers
if( n == 0)
return a;
for(i = 2; i <= n; i++)
{
c = a + b;
a = b;
b = c;
}
return b;
}

Q4
39:43 T.C: O(n) and S.C: O(n) where n is the number of digits of a given number

Q5
41:56 => TC: O(N) and SC: O(N)
45:56 => TC: Log(N) and SC: on(N)
where N is power of given number like : a^N

Q6
47:25 => Sorted or unsorted array problem T.C: O(n) and S.C: O(n)

Q7
54:58 => Subset question T.C: O(2^n) and S.C: O(n)


Q8
1:11:08 => jump stair problem T.C: O(3^n) and S.C: O(n)

Q9
1:12:03 => Subsequence problem T.C: O(2^n) and S.C: O(n)

Q10
1:16:15 => Parmutation problem T.C: O(n*n!) and S.C: O(string len)

Q11
The time complexity of problem-11 recursive solution is exponential




Thank you for reading my answers. Again I am saying, this video is very helpful for me. Please like, share this video to helps others people.

[saharshbrnwl]

Thanks Bhaiya it was quite helpful...❤🖤❤
Aur ye rha answers:
1) 16:21 Tail recursion 5, 4, 3, 2, 1 Time Complexity: O(n) Space Complexity: O(n)
2) 17:39 Head recursion 1, 2, 3, 4, 5
3) 23:21 Time complexity: O(n) Memory Complexity: O(n)
4) 29:50 Fibbonaci without recurssion Time complexity: O(n) using iternative method
5) 39:43 Digit_To_Spelling Time complexity: O(length of num) Space complexity: O(length of num)
6) 56:31 Exponent : Time complexity: O(n) Space complexity: O(1)
7) 1:11:10 Sorted_Or_Unsorted : Time complexity: O(n) Space complexity: O(n)
8) Subset Time complexity: O(2^n) Space complexity: O(n)
9) Stairs Time complexity: O(3^n) Space complexity: O(n)
10) 1:15:16 Subsequence: Time complexity: O(2^n) space complexity: O(n)
11) 1:26:20 Permutation:Time complexity: O(n*n!) space complexity: O(n)
12) Source_To_Destination : Time complexity: O(n*n) space complexity: O(n*n)