Recursion

Notes:

0) Many algorithms need to be implemented recursively, like backtracking.

1) It's a function/procedure/method, calls itself again with a smaller range of arguments (break it into simpler problems) or with different arguments (useless if use recursion with the same arguments).

2) keeps calling itself until something so simple or simpler than before (base case), can be solved easily or until an exit condition occurs.

3) Recursion must stop. so, a valid base case or end-condition must be reached, else leads to stack overflow error.

4) When a method/function/procedure is called:

        – caller is suspended,
        – "state" of caller saved,
        – new space allocated for variables of new method.

5) Powerful and elegant technique, uses "solving a smaller problem of the same type" method to solve.

6) Examples: Factorial, Fibonacci, etc.

    Q: Recursive or Iterative?        A: Iterative

    Q: Why?                                 A:It's Faster and doesn't consume a lot of memory.

7) But some problems:

      - can only be solved in recursive, or

      - more efficient in recursive, or

      - iterative solutions are difficult to conceptualize.

   Examples: Tower of Hanoi, Searching (DFS, BFS), etc.

To be continued...