Lesson Overview
Understand recursive thinking and connect it to searching and sorting examples.
Portfolio focus: Trace factorial(4).
Starter: think before typing
Before running this algorithms example, find the line where the main idea becomes active. Write a prediction: what must already be true for that line to work, and what should be different after it runs? The checked run ends with `factorial(4) = 24`; predict how the focus line helps produce that evidence.
Learning Objectives
- Trace a recursive method.
- Identify base case and recursive case.
- Compare simple searching approaches.
- Explain why sorting can make later searching easier.
Learning Outcomes
- By the end of the lesson, you can trace a recursive method.
- By the end of the lesson, you can identify base case and recursive case.
- By the end of the lesson, you can compare simple searching approaches.
- By the end of the lesson, you can explain why sorting can make later searching easier.
Why this idea exists
Recursion comes from mathematics and computer science: define a problem in terms of smaller versions of itself until a base case is reached. It is elegant, but it demands careful reasoning.
Sorting and searching are classic algorithmic problems because they reveal how data organisation affects performance. A sorted structure can make searching dramatically more efficient, but sorting itself has a cost.
Degree-level understanding means tracing the call stack, identifying termination conditions and explaining algorithm choice in relation to data size, ordering and required operations.
Deep dive
Mechanism in this example
The important mechanism is visible around `static int factorial(int n) {`. Read it as a concrete move in the program, not as decorative syntax: identify what value, object, branch, call or boundary is being created at that point.
Design pressure
Degree-level understanding means tracing the call stack, identifying termination conditions and explaining algorithm choice in relation to data size, ordering and required operations.
Failure mode to watch
For Recursion, Sorting and Searching, deliberately disturb the assumption behind `static int factorial(int n) {`: use an awkward value, missing input, wrong order of calls or boundary case. The useful question is how that disturbance exposes a weakness in the algorithms design.
Extension step
Extend the example by doing this: Write a base case for a recursive sum. The point is to make one small change that forces you to revisit the concept, rather than adding unrelated features.
Portfolio standard
The portfolio note should not repeat the lesson wording. It should show the edited code, the run result, and your own explanation of this evidence: compare linear and binary search in words.
Lesson visual
Type this and run it
Create RecursionSortingAndSearchingDemo.java, type the program, and run it before changing anything. This section is about reproducing the checked baseline.
public class RecursionSortingAndSearchingDemo {
public static void main(String[] args) {
System.out.println("factorial(4) = " + factorial(4));
}
static int factorial(int n) {
if (n <= 1) return 1;
return n * factorial(n - 1);
}
}Build and run it with:
javac RecursionSortingAndSearchingDemo.java && java RecursionSortingAndSearchingDemoExpected baseline: factorial(4) = 24
Run the code in your browser
Use the editor as an experiment surface. First run the checked version, then make one small change to the part of the program that demonstrates algorithms and compare the new behaviour with the reference output.
factorial(4) = 24Line-by-line explanation
Read the code as a sequence of responsibilities. The focus line for this lesson is static int factorial(int n) {; the surrounding lines prepare it, use its result or make the behaviour observable.
public class RecursionSortingAndSearchingDemo {This names the runnable class for the Recursion, Sorting and Searching example, giving the compiler and JVM one clear unit to build.
public static void main(String[] args) {This is the program entry point. In Recursion, Sorting and Searching, it keeps the demonstration of algorithms in one traceable starting script.
System.out.println("factorial(4) = " + factorial(4));This prints "factorial(4) = " + factorial(4) as the observable evidence for Recursion, Sorting and Searching. The output lets the learner check whether the algorithms idea behaved as predicted.
}This closes the innermost Recursion, Sorting and Searching block, so the immediately preceding method, branch or loop has finished.
static int factorial(int n) {This starts factorial, a named Recursion, Sorting and Searching operation. Its parameters describe what information comes in; its body decides what work is done.
if (n <= 1) return 1;This sends a Recursion, Sorting and Searching result back to the caller, so the surrounding code can use the answer.
return n * factorial(n - 1);This sends a Recursion, Sorting and Searching result back to the caller, so the surrounding code can use the answer.
}This closes the outer Recursion, Sorting and Searching structure, returning the reader to the surrounding class or file.
}This closing brace number 3 completes another layer of the Recursion, Sorting and Searching source structure Java has been checking.
Worked example
From code to explanation
Problem: Use Recursion, Sorting and Searching to complete a small portfolio-quality step: Trace factorial(4).
Method: Locate the line `static int factorial(int n) {`, explain the exact role it plays, then decide what you would change to extend the example without changing the whole program.
Reveal worked answer
The checked run should produce `factorial(4) = 24`. A strong answer links the result back to algorithms: what was created, selected, stored, called or protected, and why that matters for the portfolio task.
Trace the program
Before: Before the key operation, identify the relevant value, object, branch or resource that the algorithms concept depends on.
During: Trace `static int factorial(int n) {` as the Recursion, Sorting and Searching example executes. Say whether that operation creates data, checks a condition, calls behaviour, stores information or crosses a boundary.
After: Compare the run with the expected evidence: `factorial(4) = 24`.
Change: Now write a base case for a recursive sum, run again, and explain the smallest reason the behaviour changed.
Common misconception
A common mistake in recursion, sorting and searching is treating the example as a finished answer. For algorithms, the important question is narrower: which operation carries the idea, what does it make possible, and what would break if you changed it carelessly?
Quick checks
1. In this Recursion, Sorting and Searching example, what is the best reason to focus on `static int factorial(int n) {`?
2. Which evidence is strongest after you edit and rerun this example?
How to study this lesson
For Recursion, Sorting and Searching, predict how algorithms changes the run before you press Run.
Use the first portfolio task as your main edit: Trace factorial(4).
Use the second task as your variation: Write a base case for a recursive sum.
Finish with evidence, not a diary entry: Compare linear and binary search in words.
Portfolio Practice
- Trace factorial(4).
- Write a base case for a recursive sum.
- Compare linear and binary search in words.
Final self-check
Can you explain the key operation?
Explain the line identified in the quick check in one or two sentences. Your answer should say what it does before the output factorial(4) = 24 appears.
Can you justify the portfolio evidence?
Your evidence should include the original run, one edited run, and a short note explaining how the edit affected algorithms.
Study route
Practise algorithms by predicting the Java example, typing it, running it in the browser, tracing the result and saving portfolio evidence.
Next, move into Event-Driven Programming and carry forward one improvement from this lesson into the next program.