Tips, Notes, Patterns & Problem solving based on the Recursion concepts

• Tips
• Notes
• Patterns
• Problem solving

• The problem-solving mindset to solve recursion problems comes with Practice!
• This is the most important concept from all of the Data Structures and Algorithms concepts
• Recursion provides the base knowledge for more than 90% of the topics involving problem-solving
• Clear understanding of Recursion is important to solve problems like:
  • Binary Trees
  • Linked lists
  • Binary Search Trees
  • Dynamic Programming
  • Heaps
  • Graphs
  • Traversals
• Prerequisites for Recursion:
  • Functions
  • Memory Management
• You will face difficulties while learning Recursion, so don't skip it! don't give up!
• Because once you understand recursion its very easy to proceed with problem solving
• Don't break your learning streak!
• Do not overthink!

• Algorithms allows us to use data structures and perform actions on that data
  • Data Structures + Algorithms = Programs
  • Example:
    • Class {} + function() = Programs
• Most commonly used algorithms:
  • Sorting
  • Searching + BFS + DFS
  • Recursion
  • Dynamic Programming
• Certain algorithms allow us to improve the time complexity to smaller and better ones.

• Until function is not finished execution, it will remain in call stack
• When a function finishes execution, it is removed from the stack and the flow of the program is restored to where that function was called

• A function that calls itself

• Condition where our recursion will stop making new calls
• No base condition -> Function calls will keep happening and the stack will be filled again and again
• For every call of a function will take some memory in stack
• When the memory of computer will exceed the limit -> StackOverflow error

• It helps us in solving bigger/complex problems in a simple way
• You can convert recursion solutions into iteration and vice versa
• Space complexity: O(N) where N is the number of recursive calls, hence it's not constant
• It helps us in breaking down bigger problems into smaller problems

1. Identify if you can break down problem into smaller problems
2. Write the recurrence relation if needed
3. Draw the recursion tree for a small example
4. See how the values and what type of values (int, string, etc) are returned at each step and see where the function calls will come out of. And in the end, you will come out of the main function

• Visualization of Function calls and call stack with Recursion tree
• Variables (Which variable type to use in which place and what to return)
  • Argument variables -> Will go into the next function call
  • Return type
  • Variables present in function body -> Are specific to that function call

• See the flow of functions and see how they are getting into stack
• Identify and focus on left tree calls and right tree calls
• Draw the tree and pointers again and again using pen and paper
• Use the debugger to see the flow of the program

• When the last function call is the last statement in the body, it is called Tail Recursion
• Take the programs NumbersExampleRecursion and Fibonacci to understand tail recursion
  • In the numbers example, the print(i) recursive call is the last statement, hence it is a Tail Recusion
  • Whereas, in the Fibonacci program, the last statement is a return statement which is waiting for the execution of the two recursive calls fibo(n-1) and fibo(n-2). Hence it is not a Tail Recursion.

• Usage of accumulator for storing answers
• Factorial Example:
• 
• Fibonacci Example:
• 

1. Linear recurrence relation -> Fibonacci Number
2. Divide & Conquer recurrence relation -> Binary Search

1. Stack is Building
   • Perform operations when function call stack is building
2. Stack is falling
   • Perform operations when function call stack is falling
3. Half - Half choice
   • Two or more recursive calls are made on the basis of input
4. Use functional arguments
   • Use functional arguments to store and pass computations to recursive calls
   • These functional arguements are also called as accumulators
5. Use Static variable
   • Use static variable to store outside the scope of recursive functions
6. Base case return value
   • Base case Return value is void non-computational recursive functions
   • Base case Return value is 0 for addition based computations in recursive functions
   • Base case Return value is 1 for product based computations in recursive functions
   • Base case Return value is functional arguments for persistent storage based computations in recursive functions

Sheet Link

• Time Complexity: (2^N) + ((2^N) * log(2^N))
  • For every index, we have two recursive choices (pick & don't pick)
  • So, if the no. of indices is N, then the time complexity for all the choices in the recursive tree is 2^N
  • As per the question, we have to return the answer - sum of individual subsets, in the increasing order. Hence, for sorting the answer it will take (2^N) * log(2^N)