Computer Science
Grade 9
20 min
Patterns in Computers
Patterns in Computers
Tutorial Preview
1
Introduction & Learning Objectives
Learning Objectives
Define recursion and identify its base case and recursive step in a function.
Trace the execution of a simple recursive function, such as factorial.
Implement a basic recursive function in a programming language to solve a problem.
Explain how fractals are generated using self-similar, recursive patterns.
Define what a design pattern is and give an example of its purpose.
Identify the structure of the Singleton design pattern and explain its use case.
Ever seen a picture that contains a smaller version of itself, over and over again? 🖼️ That's a powerful pattern called recursion, and computers are experts at creating it!
In this lesson, we'll move beyond simple loops to explore advanced patterns. You'll learn about recursion, where functio...
2
Key Concepts & Vocabulary
TermDefinitionExample
RecursionA programming technique where a function calls itself in order to solve a problem. It breaks a large problem down into smaller, identical sub-problems.To calculate the factorial of 5 (5!), you multiply 5 by the factorial of 4 (4!). To get 4!, you multiply 4 by 3!, and so on, until you reach the base case.
Base CaseThe condition within a recursive function that stops the recursion. It's the simplest version of the problem that can be solved directly without making another recursive call.In a factorial function `factorial(n)`, the base case is when `n` is 1 or 0. The function simply returns 1, stopping the chain of calls.
Recursive StepThe part of a recursive function where it calls itself, but with a modified input that moves it closer to the base case.I...
3
Core Syntax & Patterns
The Structure of a Recursive Function
function recursiveFunction(input) {
// 1. Base Case
if (input meets stop condition) {
return simplest_answer;
}
// 2. Recursive Step
else {
return calculation_using(recursiveFunction(modified_input));
}
}
Every recursive function must have at least one base case to prevent it from running forever. It must also have a recursive step that modifies the input to ensure it eventually reaches the base case.
The Singleton Design Pattern
class Singleton {
private static instance;
private constructor() { /* ... */ }
public static getInstance() {
if (!Singleton.instance) {
Singleton.instance = new Singleton();
}
return Singleton.instance;
}
}
This pattern ensures only one object of a class can ever be...
4 more steps in this tutorial
Sign up free to access the complete tutorial with worked examples and practice.
Sign Up Free to ContinueSample Practice Questions
Challenging
Imagine a recursive function `sum(n)` to calculate 1 + 2 + ... + n. Based on the logic of the `factorial(n)` example, what would the correct recursive step be?
A.return n * sum(n - 1);
B.return n + sum(n - 1);
C.return sum(n - 1);
D.return n + (n - 1);
Challenging
The tutorial mentions converting loops to recursion. What is a potential disadvantage of using a deep recursive function (e.g., counting to 1,000,000) compared to a simple loop, based on the concepts discussed?
A.recursive function is always harder to write.
B.recursive function can cause a stack overflow error, while a loop will not.
C.loop is better at creating self-similar patterns.
D.recursive function cannot have a stopping condition.
Challenging
Which of the following problems is LEAST suited for a simple recursive solution as described in the tutorial (i.e., breaking it into smaller, identical sub-problems)?
A.Calculating the nth Fibonacci number, where F(n) = F(n-1) + F(n-2).
B.Searching for a file in a folder that contains other folders.
C.Calculating the total of all items in a simple, one-dimensional shopping list.
D.Drawing a fractal tree where each branch grows smaller branches.
Want to practice and check your answers?
Sign up to access all questions with instant feedback, explanations, and progress tracking.
Start Practicing Free