"To understand recursion, you must first understand recursion."
zyBooks Ch 4.1 - 4.9
Recursion can be defined as an operation in terms of itself. To solve problems recursively, we break down the problem into smaller occurrences of the same problem.
Recursive programming refers to the writing of methods that call themselves to solve problems recursively.
Recursion is well suited for solving certain types of problems and can be used as a solution to iterative problems (loops). Some problems can, in fact, be solved better with recursion. The solutions are more simple and elegant.
An recursive algorithm involves at least 2 cases:
Base case: A simple occurrence that can be answered directly.
Recursive case: A more complex occurrence of the problem that cannot be directly answered, but can instead be described in terms of smaller occurrences of the same problem.
It is possible to have more than one base or recursive case, but all recursive problems must have at least one of each. One of the challenges of recursive programming is correctly identifying these cases.
Use the Java visualizer to visualize the execution of the example methods
https://cscircles.cemc.uwaterloo.ca/java_visualize/
https://www.geeksforgeeks.org/recursion-in-java/
zyBooks Ch 4.1 - 4.9 Participation Activities
https://github.com/ava11235/it212/blob/main/RecursionExamples.java
Upon successful completion of the material, students will be able to:
- Identify problems best solved with recursion.
- Identify base and recursive cases of such problems.
- Implement recursive algorithms in Java.
- Implement binary search recursively.
- Apply best practices to debugging recursive code.
- Implement well known recursive methods such as Fibonacci sequence, GCD and factorial.
- Implement recursive probabilities exploration.
- Understand common memory problems associated with the use of recursion, such as stack overflow.