Computational Problem Solving with Java and Interactive Object Graphics

Section 12.5 Key Concepts

1. 🔗

   The call stack is a data structure that tracks all currently executing methods.
2. 🔗

   A stack frame tracks the state of each executing method on the call stack.
3. 🔗

   A stack frame contains all information about the associated active method instance.
4. 🔗

   Stack frames are pushed onto the top of the call stack when a method starts execution and popped off the top of the call stack when execution terminates.
5. 🔗

   When a method invokes itself, a new stack frame is added to the call stack so all instances of an executing method may be tracked.
6. 🔗

   The size of the call stack is limited by memory. If an excessive number of methods are invoked, the call stack may overflow resulting in a StackOverflowError being thrown.
7. 🔗

   When a method (eventually) invokes itself during execution, the process is called recursion.
8. 🔗

   When a recursively invoked method returns, the method call resolves to the returned value.
9. 🔗

   Many algorithms may be implemented using recursion.
10. 🔗

    Most recursive algorithms have alternative iterative implementations that tend to be more efficient in terms of the amount of memory used.
11. 🔗

    Computing a factorial, the Fibonacci number, and the Greatest Common Divisor have elegant recursive implementations as well as iterative implementations.
12. 🔗

    Recursive programs may be divided into direct recursion and indirect recursion.
13. 🔗

    All recursive programs must have at least one base case and at least one recursive case.
14. 🔗

    The base case executes when the recursive algorithm has reached the end of execution and no further recursion is required.
15. 🔗

    A recursive case must move the state of the program closer to the base case in some way to ensure the recursive program terminates.
16. 🔗

    There may be multiple base cases and multiple recursive cases in a recursive algorithm.
17. 🔗

    Multi-case recursion occurs when a method has more than one base case and/or more than one recursive case.
18. 🔗

    Multiple recursion occurs when the block of code that implements a single recursive case invokes multiple recursive methods or the same recursive method multiple times.
19. 🔗

    Dynamic programming is a technique used to improve performance of certain recursive methods by saving intermediate results that would otherwise be computed multiple times.