Re 2. Problems on Recursion | Strivers A2Z DSA Course

take U forward

5 chapters7 takeaways9 key terms5 questions

Overview

This video, the second in a DSA course on recursion, covers fundamental recursive problems. It begins by explaining how to print a name or any string 'n' times using recursion, emphasizing the use of parameters instead of global variables and defining base cases. The video then progresses to printing numbers linearly from 1 to 'n' and then from 'n' to 1. A key concept introduced is 'backtracking,' demonstrated by printing numbers from 1 to 'n' without using the increment operator, by placing the print statement after the recursive call. Finally, it poses a challenge to print numbers from 'n' to 1 using a similar backtracking approach without the decrement operator, encouraging viewer participation.

How was this?

Save this permanently with flashcards, quizzes, and AI chat

Chapters

Define a recursive function that takes current count 'i' and total count 'n' as parameters.
The base case is when 'i' exceeds 'n', at which point the function returns.
In the recursive step, print the name and then call the function with 'i+1' and 'n'.
This approach avoids global variables and manages state through function parameters.
Time and space complexity are both O(n) due to 'n' function calls and stack depth.

This problem introduces the core mechanics of recursion: base cases, recursive steps, and parameter passing, which are foundational for solving more complex recursive problems.

Calling a function `f(i, n)` where `n=3`. Initially `f(1, 3)` prints 'raj' and calls `f(2, 3)`. `f(2, 3)` prints 'raj' and calls `f(3, 3)`. `f(3, 3)` prints 'raj' and calls `f(4, 3)`. `f(4, 3)` hits the base case (i > n) and returns, unwinding the stack.

This is a direct extension of printing a name 'n' times.
The recursive function `f(i, n)` checks if `i > n` as the base case.
If not the base case, it prints the current value of 'i' and then calls itself with `f(i+1, n)`.
The initial call is typically `f(1, n)`.

This problem reinforces the pattern of using recursion for sequential operations and demonstrates how to adapt the previous solution to print numerical sequences.

To print 1 to 4, `f(1, 4)` prints 1 and calls `f(2, 4)`. `f(2, 4)` prints 2 and calls `f(3, 4)`. `f(3, 4)` prints 3 and calls `f(4, 4)`. `f(4, 4)` prints 4 and calls `f(5, 4)`. `f(5, 4)` hits the base case and returns.

To print from 'n' down to 1, the recursive function needs to decrement the counter.
The base case is when 'i' becomes less than 1.
The recursive step involves printing 'i' and then calling the function with `f(i-1, n)`.
The initial call should be `f(n, n)` to start the countdown from 'n'.

This problem introduces the concept of changing the order of operations within the recursive step, showing how to achieve a descending sequence.

To print 3 to 1, the initial call is `f(3, 3)`. `f(3, 3)` prints 3 and calls `f(2, 3)`. `f(2, 3)` prints 2 and calls `f(1, 3)`. `f(1, 3)` prints 1 and calls `f(0, 3)`. `f(0, 3)` hits the base case (i < 1) and returns.

This problem requires printing 1 to 'n' but prohibits the use of `i+1` in the recursive call.
The solution uses a 'backtracking' approach where the print statement is placed *after* the recursive call.
The function `f(i, n)` calls itself with `f(i-1, n)` first.
The base case is `i < 1`, at which point it returns.
The print statement `print(i)` executes only after the recursive call returns, effectively printing in ascending order.

This demonstrates the power of the call stack and the order of execution. Placing the action after the recursive call allows the stack to unwind and execute actions in reverse order of calls, achieving a desired output sequence.

To print 1 to 3: Initial call `f(3, 3)`. It calls `f(2, 3)`. `f(2, 3)` calls `f(1, 3)`. `f(1, 3)` calls `f(0, 3)`. `f(0, 3)` hits base case and returns. Then `f(1, 3)` prints 1. Then `f(2, 3)` prints 2. Then `f(3, 3)` prints 3. Output: 1, 2, 3.

This is a challenge problem: print 'n' to 1 without using `i-1` in the recursive call.
It requires a similar backtracking approach, placing the action after the recursive call.
The solution involves calling the function recursively with a modified parameter that eventually leads to the desired print order.
The exact implementation is left as an exercise for the viewer.

This problem tests the learner's understanding of how the placement of operations relative to recursive calls dictates the order of execution and output, pushing them to think creatively within constraints.

Null

Key takeaways

1Recursion solves problems by breaking them into smaller, self-similar subproblems.
2A base case is crucial to prevent infinite recursion.
3Function parameters are preferred over global variables for managing state in recursive functions.
4The order of operations (before or after the recursive call) significantly impacts the output sequence.
5Backtracking involves performing an action after the recursive call returns, often used to achieve reversed or conditional sequences.
6Understanding the recursion tree and call stack is key to debugging and predicting recursive behavior.
7Recursive solutions often have equivalent iterative solutions, but recursion can offer more elegant code for certain problems.

Key terms

RecursionBase CaseRecursive StepCall StackParameter PassingBacktrackingTime ComplexitySpace ComplexityO(n)

Test your understanding

1What is the purpose of a base case in a recursive function?
2How does passing parameters in recursive calls differ from using global variables, and why is it generally preferred?
3Explain the concept of backtracking in recursion and how placing a print statement after the recursive call achieves a specific output order.
4If a recursive function `f(i, n)` prints 'i' before the recursive call `f(i+1, n)`, what kind of sequence will be printed?
5How would you modify the 'print n to 1' recursive solution if you were not allowed to use the decrement operator `i-1`?