Skip to main content

Recursion

A beautiful Example MUST WATCH

How to know When to use Recursion​

  • when I face a problem where I have to take a for loop for each of the given n elements. i.e.
    • lets say in Subsets, Permutation, Combinations, I have to take each element from the given sequence and add other elements to it, so my first thought would be to use a for loop but I would have to take n number of for loops, which is not possible.
    • So basically what recursion does is it repeats a piece of code again and again just like for loop, but unlike for loop we can set the condtion for how many loops recuraion can take by recursion's base case

Recursion is based on Mathemeatical Induction​

Principle of Mathematical Induction​

(Example of How to write Induction)[https://usaco.guide/plat/matrix-expo?lang=cpp#proof-by-induction]

proof by contrapositive​

Recursive Leap of Faith​

Time Complexity of Recursion​

  • generally Time Complexity = no. of Nodes

Master Theorem​

Space Complexity of Recursion​

Depth of Recursion​

Auxiliary Space taken by Recursion = Depth of Recursion

Resources to Learn​