Java Recursion and Trees

Recursion

Recursion is a function/method that calls itself
A recursive function must have at least one base case (stopping condition) and one recursive case (where the function calls itself)
Each call is placed on the stack (LIFO - last in, first out)

Stack:
- Stores method call frames
- Local variables
- Handles function calls/returns
- Memory is managed automatically (LIFO)
- Limited in size; exceeding it causes StackOverflowError
- Can be visualized as a stack of plates, where each plate represents a method call

Heap:
- Stores objects and instance variables
- Memory is managed by the garbage collector
- Larger and shared by all threads; used for dynamic memory allocation

Note	Technical explanation of stack vs. heap: https://www.guru99.com/java-stack-heap.html

Forgetting the base case causes an "infinite" loop, leading to a StackOverflowError
Deep recursion can be inefficient and cause performance issues
Tail recursion optimization (TCO) is not supported in Java
- TCO is compiler feature that eliminates stack frames for certain recursive calls, allowing recursion to run without growing the stack
- JVM always creates a new stack frame for every method call
- JVM does not provide an instruction to replace a stack frame during a recursive call

Common examples include calculating sums or factorials
Sum Example: https://gist.github.com/MattToegel/97d98779bb7e065739f7b8dd3b43906c
Factorial Example: https://gist.github.com/MattToegel/1aeb8932a06599518166afe4bffc79c9
Consider using iteration instead of recursion for cases where stack memory is a concern

Code: https://gist.github.com/MattToegel/2b3ff670235e920eae6f17f9201d99ba
- Demonstrates efficiency differences between recursion and iteration for summing numbers
- Recursive approach is intuitive but can be slower for large inputs due to stack overhead
- Iterative approach avoids stack overhead and is generally faster for larger computations

Code: https://gist.github.com/MattToegel/de77e31b2e27cc6080fc2c231a4f4293
Example of searching for files matching a partial name with an optional extension
Edge Case: Ensure the program handles directories without proper read permissions to prevent crashes

Code: https://gist.github.com/MattToegel/ea4574377787b4b62415d4b455b0291c
Demonstrates recursion to find a path through a maze
Ensure the maze structure has exactly one start ('S') and one exit ('E') to avoid ambiguous results

Trees are non-linear, hierarchical data structures
Common types include binary trees, useful for searching, graphics, routing, and AI behaviors
File systems often follow a tree structure

Depth-First Search (DFS) - Depth-first search is a type of traversal that explores as deeply as possible into each branch before moving to the next sibling node.
- In-Order - Visit the left subtree first, then the root node, and finally the right subtree
- Pre-Order - Visit the root node first, then the left subtree, followed by the right subtree
- Post-Order - Visit the left subtree first, then the right subtree, and finally the root node
Breadth-First Search (BFS) / Level Order - Visits all the nodes of a level before proceeding to the next level
- Time Complexity: DFS and BFS both run in O(n) time, where n is the number of nodes

Code: Tree Traversal Example
- Includes methods for In-Order, Pre-Order, Post-Order, and BFS traversal
- Uses recursion for DFS traversals and a queue for BFS traversal
- Processes a sample tree structure to showcase traversal outputs
Use-cases
- In-Order: Retrieves sorted data from a binary search tree (e.g., for reports or data analysis)
- Pre-Order: Useful for copying or serializing tree structures (e.g., saving or reconstructing trees)
- Post-Order: Ideal for cleanup tasks like deleting a tree or evaluating postfix expressions
- BFS: Processes nodes level-by-level, useful for shortest path algorithms or rendering hierarchical data
Compile and run (assumes folder is called Module3)
- javac Module3/TreeTraversalExample.java
- java Module3.TreeTraversalExample

Source: GeeksforGeeks - Tree Traversals

Source: GeeksforGeeks - Tree Traversals

Source: GeeksforGeeks - Tree Traversals

Source: GeeksforGeeks - Tree Traversals

Code: https://gist.github.com/MattToegel/9e6e1d5fb97c9a3979b610f5586126b8
- Models decision-making: Represents NPC behavior using a tree structure (DecisionNode class) with yes/no branches
- Simulates conditions: Uses random checks (Math.random()) to mimic decision outcomes dynamically
- Logs decisions: Outputs each decision and action taken during traversal for clarity and debugging
- Handles complex scenarios: Includes decisions like healing, retreating, attacking, and finding cover
- Encapsulates logic: Each node contains a question, action, and branches for further decisions
- Expandable design: Easily add new decision points or branches to handle additional NPC behaviors
Compile and run (assumes folder is called Module3)
- javac Module3/DecisionTree.java
- java Module3.DecisionTree