Codingbat - Recursion

Recursion

- Recursion == Induction.

- When dealing with recursion, think of proof by induction.

    => Base case / Assumption that it is true at k / prove at k+1.

How to tackle recursion.

1) Come up with the base cases. 

    - When to end the function? At which condition should it end? When will this function stop?

        => Think the condition of arguments when the function is ended.

    - Obvious base cases like when n == 0, string's length is 0 or string.length() < 2.

    - Try to be as specific as possible when in comes to the base case.

        => Reach the very end of execution.

2) Starting from the base case, try to solve the question when n == 2 or 3.

    - Approach with small n and outline the pattern.

2) Find a pattern and think what the new argument of next execution would be by the pattern. This will help outline the flow of the execution.

    - How the pattern affect the next argument?

    - Would be n+1? remainder? substring? next element in an array?

3) Believe that the function will do what it is supposed to do. Let it flow.

    - Try not to overthink when implementing. Do not trace every stage of each execution.

        => Understand what the problem is, ideate how it is supposed to be, draw an outline of the mechanism to reach base case, then let it run.

4) If any condition exists, think of any association with base case, return clause position, and next execution. 

    - Again, let it run. Do not overthink how each execution will be carried out with conditions.

5) Return is just there to maintain the value returned from the method. 

    - It's same as passing arguments to the previous method.

        => No return statement is as if there is no argument passing to the previous method.