RECURSION
1. What is recursion, and how does it work?
Answer:
Recursion is a programming method where a function calls itself to solve smaller instances of
the same problem. It continues until a base case is reached, which stops further recursion.
Example: Factorial of n:
2. What are the two main components of a recursive function?
Answer:
Base case: Stops the recursion.
Recursive case: Reduces the problem and calls itself.
Example:
Base: factorial(1) = 1
Recursive: factorial(n) = n * factorial(n - 1)
3. How do base cases affect recursion?
Answer:
They stop the recursion from running infinitely and prevent stack overflow.
Example:
4. What is a recursive case?
Answer:
The part where the function calls itself with a simpler input.
Example:
factorial(n) = n * factorial(n - 1)
5. Difference between direct and indirect recursion?
Answer:
Direct: Function calls itself.
Indirect: Function A calls B, which calls A.
6. How does the call stack work during recursion?
Answer:
Each recursive call is pushed onto the call stack. When the base case is hit, functions are
popped off the stack in reverse.
Example:
factorial(3) → factorial(2) → factorial(1) → return values unwind.
7. Advantages and disadvantages of recursion?
Advantages:
Code is simpler for problems like tree traversal or divide-and-conquer.
Disadvantages:
Uses more memory (stack).
May cause stack overflow.
Sometimes slower than iteration.
8. What is tail recursion, and why is it important?
Answer:
Tail recursion is a special type of recursion where:
The last line of the function is the recursive call.
Nothing is done after the function calls itself.
Because of this, memory is saved (some compilers optimize it by not adding new stack
frames).
Example:
NOTE :
9. How can recursion lead to stack overflow?
Answer:
If recursion doesn’t reach the base case or the input is too large, it leads to too many calls
and memory overflow.
Example:
Calling factorial(-1) without checking for negative inputs.
10. How does recursion differ from iteration?
Answer:
Recursion: Uses function calls and call stack.
Iteration: Uses loops, usually more efficient.
11. Common problems in writing recursive functions?
Answer:
Missing base case.
Not reducing input → infinite recursion.
Stack overflow on large inputs.
Recomputing same values (like naive Fibonacci).
12. How to convert recursion to iteration?
Answer:
Use loops or an explicit stack to simulate recursion
13. What is memoization and how does it help?
Answer:
Memoization is a technique used in recursion to store the results of expensive function calls
and reuse those results when the same inputs occur again. This avoids repeated calculations
and speeds up the program.
How does memoization help?
Avoids repeated work: When a function is called multiple times with the same input,
memoization returns the stored answer instead of recalculating.
Improves efficiency: Especially useful in recursive problems like Fibonacci where the
same values get calculated many times.
Reduces time complexity from exponential to linear in many cases.
14. How does recursion help in divide and conquer?
Answer:
Divide and conquer solves problems by breaking them into subproblems, solving them
recursively, and combining results.
Example: Merge Sort
15. When should recursion be avoided?
Answer:
When the problem is simple and easily done with loops.
Input size is very large.
Risk of stack overflow or inefficient performance.
Reverse a Singly linked List :
note: head is passed by value.
Why pass the pointer by value here?
When you pass head by value, you pass a copy of the pointer (i.e., the address
stored in head).
Inside the function, you can modify the node that head points to (like changing
head->next), because the pointer points to the same memory.
But changing the value of head itself (the pointer variable) inside the function
won't affect the caller’s pointer because you only changed a copy.
This is fine because the recursion returns the new head pointer back to the caller,
who assigns it to update the external pointer.