Aditya verma

Intro

• make I/P smaller ? but why?

  • we take some decisions which leads to smaller inputs

  • so in recursion we take decisions which makes the input smaller

• recursion — decision space

• recursive tree — soul of recursion

  • create a recursive tree then we will be done with the question

  • ex — create all subsets of a string

  • recursion == choices + decision

• 2 steps to solve any recursive problem

Approach to recursion problem

• Recursive tree — IP/OP method (decision tree)

  • create a decision tree where we take desicision at each step

• Base condition — Induction/hypothesis

  • Base condition

  • Hypothesis

  • induction —

• Choice Digram (DP)

• one more

• Recursive tree

  • at each input we have option to do a action and for each action we have input and output

  • Based on each action the input gets smaller and smaller

  • for each node in the tree we have number of