Lets Code Them Up!

Recursion – Notes

  • Have you ever seen the Russian Doll? If you open a Russion Doll from top, it has another smaller russian doll inside it. If you again open that Russian Doll, it has another small Russian Doll inside it, and so on. Until you reach the tinyest doll which cannot be opened. This is similar to recursion. 
  • Recursion solves a problem by solving a smaller instance of the same problem, unless the problem is so small that we can just solve it directly.
  • Slower than iterative and stack methods and is rearely used. We need to know them because companies test them and some problems solve better by recursion
  • Recursion is useful with logic involving multiple branches, nested data structures, unknown count of loops or iterative approach is complex.

Recursion Terminology

  • Base Case – when to stop
  • Recursive Case – calls itself 
  • Scope Variables – parent variables that can be accessed by child
  • State – current values of variables of stack that tracks where you are in your recursive algo
  • Single recursion – each recursive case calls itself one time, eg – factorial, fibonacci
  • Multiple recursion – each case calls itself multiple times creating a branching effect. 
  • Top Down Approach – start at input, call itself recursively to reach base case. Could be single or multiple recusion
  • Bottom Up Approach – start at some defined value, build a path to reach input. Usually only single recursive pattern.

Implement Recursion

  • Helper Method – actual recursive method
  • Wrapper Method – method that calls recursive method, public method called by user

Example – Top-Down Approach

Class Fibonacci{

public static int fibonacci(int n){
       return calculateFib(n);
}

private static int calculateFib(int n){
        if(n == 0 || n == 1)
           return n;
        return calculateFib(n - 1) + calculateFib(n - 2);
}
}

Megha