Recursion

  • Last updated on 23rd Jun 2023

Table of Contents

Introduction

Recursion is when a function calls itself to solve a problem.

Most famous example

function factorial(n) {
  if (n === 1) { // base case
    return 1;
  } else { // recursive case
    return n * factorial(n - 1); // recursive call
  }
}

Above, a base case stops the recursion, and the recursive case keeps it going. To find the factorial of a number, the base case is when the number is 1 (since 1! = 1). The recursive case calls the function with the number minus one. Key elements include the function, the base case, and the recursive call. If the base case isn’t reachable, then we have an infinite loop.

Suit tailoring shop

// Function to calculate the total cost of tailoring suits
function totalTailoringCost(numSuits) {
  // Base case: If no suits are requested, return 0
  if (numSuits === 0) {
    return 0;
  } 
  // Recursive case: Calculate the cost of tailoring one suit and add it to the cost of tailoring the rest
  else {
    const costPerSuit = 100; // Cost of tailoring one suit
    return costPerSuit + totalTailoringCost(numSuits - 1); // Recursive call with one less suit
  }
}

// Example usage:
const numSuitsRequested = 5;
const totalCost = totalTailoringCost(numSuitsRequested);
console.log(`Total cost for tailoring ${numSuitsRequested} suits: $${totalCost}`);

Above, the totalTailoringCost function calculates the total cost of tailoring a certain number of suits. It uses recursion by breaking down the problem of tailoring multiple suits into smaller parts: tailoring one suit and tailoring the rest. This continues until the base case is reached (no suits requested), at which point the recursion stops.

We work with recursion because it helps us break down certain types problems more manageable, smaller chunks, reducing redundancy and improving readability.

In PHP and Python

<?php
// Function to calculate the total cost of tailoring suits
function totalTailoringCost($numSuits) {
  // Base case: If no suits are requested, return 0
  if ($numSuits === 0) {
    return 0;
  } 
  // Recursive case: Calculate the cost of tailoring one suit and add it to the cost of tailoring the rest
  else {
    $costPerSuit = 100; // Cost of tailoring one suit
    return $costPerSuit + totalTailoringCost($numSuits - 1); // Recursive call with one less suit
  }
}

// Example usage:
$numSuitsRequested = 5;
$totalCost = totalTailoringCost($numSuitsRequested);
echo "Total cost for tailoring $numSuitsRequested suits: $$totalCost";
?>

def total_tailoring_cost(num_suits):
    # Base case: If no suits are requested, return 0
    if num_suits == 0:
        return 0
    # Recursive case: Calculate the cost of tailoring one suit and add it to the cost of tailoring the rest
    else:
        cost_per_suit = 100  # Cost of tailoring one suit
        return cost_per_suit + total_tailoring_cost(num_suits - 1)  # Recursive call with one less suit

# Example usage:
num_suits_requested = 5
total_cost = total_tailoring_cost(num_suits_requested)
print(f"Total cost for tailoring {num_suits_requested} suits: ${total_cost}")

The logic from both flow in the same way. Checkout the resources below for a more expansive approach and explanation.

Resources