Recursion

Time: 3 hrs

📜 Slides

Link to Slides

🎯 Learning Objectives

By the end of this lesson, participants will be able to:

🔄 Understand recursion and its role in problem-solving.
🔁 Implement recursive functions to solve coding problems.
🎯 Recognize the base case(s) in recursive functions.
✨ Compare recursion with iteration, identifying similarities and differences and when to use one over the other.

📚 Warm Up: Factorial Calculation

(20 minutes)

Reason

This section encourages learners to understand recursion as a method of repetition, similar to iteration using loops.
This discussion also provides a segue into more complex problems, where the intricacies of iteration can present challenges.

Problem Statement

Write two different JavaScript functions that each calculate the factorial of a number.
In the first function, approach the problem by starting from the given number and working your way down to 1.
For the second function, start from 1 and work your way up to the given number.
Both functions should return the factorial of the given number. Do not use any built-in factorial functions or libraries.

Example:

increment

const n = 5;
console.log(calculateFactorialIncrement(n)); 
// Output: 120

decrement

const n = 5;
console.log(calculateFactorialDecrement(n)); 
// Output: 120

Solution

Code Example:

decrement

function calculateFactorialDecrement(n) {
  let result = 1;
  for(let i = n; i > 0; i--) {
      result *= i;
  }
  return result;
}

increment

function calculateFactorialIncrement(n) {
  let result = 1;
  for(let i = 1; i <= n; i++) {
      result *= i;
  }
  return result;
}

📚 Calculating Factorials: From Loops to Recursion

Live Coding Session

Implement the solutions for calculating factorials live in Google Code Snippets.
Demonstrate the functions' execution with a few different inputs to verify the correct output.

Introduction to Loops

Define what a loop is and explain its purpose in programming.
- A loop in programming is a control structure that is used to repeat a block of code multiple times. The number of repetitions is determined by a condition or a count.
Display a basic loop structure using a code snippet from the decrementing factorial function as an example.

function calculateFactorial(n) {
  for(let i = n; i > 0; i--) {
      console.log(i); 
  }
}

calculateFactorial(5); // This will output: 5, 4, 3, 2, 1

Emphasize how the loop starts at n and counts down to 1, but as yet does not calculate the factorial.

Initializing Result

Discuss the necessity of a result variable to hold the product of the factorial calculation.
Show the loop with the initialized result variable using a code snippet.
Explain that result will always be 1 at this point as it is not being modified within the loop.

Calculate Factorial

Illustrate how the factorial calculation is implemented inside the loop.
Use a code snippet to show the final function with the factorial calculation.
Discuss how, in each iteration, i is multiplied with the current result, which computes the factorial.
Use calculateFactorial(5) as an example, demonstrating how it calculates 5 * 4 * 3 * 2 * 1.

Recap and Challenge

Review the key points of the lesson: loops as a means of repeating code until a condition is met, the necessity to initialize a variable to hold the result before the loop, the calculation of the result within each loop iteration, and the return of the result after the loop.
Propose a challenge for learners to code two versions of the factorial function: one starting from n and working down to 1, and the other starting from 1 and working up to n.

📚 Nature of the Loop: Exploring the 5 Components of Iteration

(30 minutes)

1. Initialization

Discuss the concept of initialization in iteration, where initial values are set before the loop begins.
Explain the importance of initializing loop control variables to appropriate starting values.
Provide examples of initializing loop counters, indices, and other relevant variables.

Code Example:

let sum = 0;
let i = 1; // Initialization
for (; i <= 10; i++) {
    sum += i;
}
console.log(sum);

2. Condition

Explain the condition component of iteration, which determines when the loop should continue or terminate.
Discuss the role of the condition in controlling the flow of execution.
Illustrate different types of conditions, such as numeric comparisons or boolean expressions.

Code Example:

let sum = 0;
let i = 1;
for (let i = 1; i <= 10; i++) {
  if (i % 2 === 0) {
      sum += i;
    }
}
  console.log(sum);

3. Iteration

Explore the concept of iteration itself, focusing on the repeated execution of the loop body.
Discuss the importance of updating loop control variables to progress towards the termination condition.
Provide examples of different types of iteration, including counting loops and sentinel-controlled loops.

Code Example:

const numbers = [1, 2, 3, 4, 5];
let sum = 0;
for (let i = 0; i < numbers.length; i++) {
  sum += numbers[i];
}
console.log(sum);

4. Execution/Loop Body

Highlight the execution phase in iteration, which involves the code block or statements executed within each iteration.
Explain how the loop body defines the actions or operations to be performed during each iteration.
Demonstrate examples of loop bodies, including assignments, computations, function calls, and conditional statements.

Code Example:

let product = 1;
for (let i = 1; i <= 5; i++) {
  if (i % 2 === 0) {
      product *= i;
  }
 }
console.log(product);

5. Update/Increment

Discuss the update or increment component of iteration, which modifies the loop control variables at the end of each iteration.
Explain the purpose of the update step in achieving progress towards the termination condition.
Provide examples of different types of updates, such as incrementing a counter or modifying indices.

Code Example:

let sum = 0;
for (let i = 1; i <= 10; i += 2) {
    sum += i;
}
console.log(sum);

📚 Creating Recursion: 5 Components of Recursion

(30 minutes - 1 hr)

1. Initialization

Discuss the concept of initialization in recursion, where initial values are set before the recursive function is called.
Explain the importance of initializing variables or parameters to appropriate starting values.
Provide examples of initializing variables or parameters in recursive functions.

Code Example:

function calculateFactorial(n) {
// Base case: When n is 0, the factorial is 1
if (n === 0) {
  return 1;
}

// Recursive case: Calculate the factorial of n
return n * calculateFactorial(n - 1);
}

console.log(calculateFactorial(5)); // Output: 120

2. Condition

Explain the condition component of recursion, which determines when the recursive function should continue or terminate.
Discuss the role of the condition in controlling the flow of execution in recursive functions.
Illustrate different types of conditions, such as base case checks or specific value checks.

Code Example:

function calculateFactorial(n) {
// Base case: When n is 0, the factorial is 1
if (n === 0) {
  return 1;
}

// Recursive case: Calculate the factorial of n
return n * calculateFactorial(n - 1);
}

console.log(calculateFactorial(5)); // Output: 120

3. Recursion

Explore the concept of recursion itself, focusing on the repeated execution of the recursive function with different inputs.
Discuss the importance of changing inputs or parameters to make progress towards the base case.
Provide examples of different types of recursion, such as linear recursion or tree recursion.

Code Example:

function calculateFactorial(n) {
// Base case: When n is 0, the factorial is 1
if (n === 0) {
  return 1;
}

// Recursive case: Calculate the factorial of n
return n * calculateFactorial(n - 1);
}

console.log(calculateFactorial(5)); // Output: 120

4. Execution/Recursive Call

Highlight the execution phase in recursion, which involves the execution of the code block or statements within the recursive function.
Explain how the recursive call defines the actions or operations to be performed during each recursion.
Demonstrate examples of recursive calls, including modifications to parameters or variables.

Code Example:

function calculateFactorial(n) {
// Base case: When n is 0, the factorial is 1
if (n === 0) {
  return 1;
}

// Recursive case: Calculate the factorial of n
return n * calculateFactorial(n - 1);
}

console.log(calculateFactorial(5)); // Output: 120

5. Update/Increment

Discuss the update or increment component of recursion, which modifies the variables or parameters at each recursive call.
Explain the purpose of the update step in achieving progress towards the base case.
Provide examples of different types of updates, such as decrementing a counter or modifying parameters.

Code Example:

function calculateFactorial(n) {
// Base case: When n is 0, the factorial is 1
if (n === 0) {
  return 1;
}

// Recursive case: Calculate the factorial of n
return n * calculateFactorial(n - 1);
}

console.log(calculateFactorial(5)); // Output: 120

CastonPursuit/pursuit_9.3_Recursion_06_14_23.md

Recursion

📜 Slides

🎯 Learning Objectives

📚 Warm Up: Factorial Calculation

📚 Calculating Factorials: From Loops to Recursion

📚 Nature of the Loop: Exploring the 5 Components of Iteration

📚 Creating Recursion: 5 Components of Recursion