Recursion: Basics

Definition

Recursion is a programming concept where a function calls itself in its own definition.

Terminology

• Base Case: The condition that stops the recursion

factorial(n):
 if n <= 0: // base case
   return 1
 else:
   return n * factorial(n-1)

• Recursive Case: The case where the function calls itself
• Stack Overflow: If the base case is not reached or defined, a stack overflow error may occur due to the continuous (infinite) addition of functions to the stack
• Direct Recursion: Function calls itself
• Indirect Recursion: One function calling another, forming a cycle
• Tailed Recursion: When the recursive call is the last operation in the function, and its result is directly returned

factorial_tail(n, result=1):
  if n <= 1:
    return result
  else:
    return factorial_tail(n-1, n*result)

• Non-Tailed Recursion: When the recursive call is not the last operation
• Mutual Recursion: Two or more functions call each other in a cycle

is_even(n):
  if n == 0:
    return True
  else:
    return is_odd(n-1)

is_odd(n):
  if n == 0:
    return False
  else:
    return is_even(n-1)

• Tabulation: Tabulation is a bottom-up approach in dynamic programming that involves storing subproblem results in a table and employs an iterative implementation. This method is particularly effective for problems with a substantial number of inputs and is preferred when subproblems do not overlap
• Memoization: Memoization is a top-down dynamic programming approach that involves caching the results of function calls through a recursive implementation. This method is effective for problems with a relatively small set of inputs, especially when the subproblems exhibit overlapping subproblems

Advantages

• Elegant solution to complex problems
• Simplifies code and improves readability
• Can lead to efficient solutions

Disadvantages

• May lead to infinite recursion if not handled properly
• Can be less efficient in certain cases compared to iterative solutions

Use Cases

• Mathematical problems like factorial, Fibonacci
• Tree and graph traversals
• Divide and conquer algorithms
• Backtracking problems

Algorithmic Steps

• Define a base case: Identify the simplest case for which the solution is known
• Define a recursive case: Break the problem into smaller subproblems and call the function recursively
• Ensure termination: Make sure the recursive function reaches the base case to avoid infinite loops
• Combine solutions: Combine the solutions of subproblems to solve the original problem

Memory Allocation

Memory is allocated on the stack for each function call, with each call having its own copy of local variables. De-allocation occurs when the base case is reached.

Comparison

Method	Amount of calls to find 5th element	Amount of calls to find 10th element	Amount of calls to find 5th using Memoization/Tabulation	Amount of calls to find 10th using Memoization/Tabulation
Factorial	6	11	3	6
Fibonacci	15	177	9	19

Step-by-Step

Fibonacci

• Mathematical formula: F(n) = F(n-1) + F(n-2)
• Initial Call: start with the initial call to fibonacci(5)
• Base Case Check: function checks if the base case is met. In this case, if n is 0 or 1, the Fibonacci number is n. Since 5 is not 0 or 1, we proceed to the recursive case

if n == 0 or n == 1:
return n

• Recursive Case: since n is 5, we enter the recursive case

else:
return fibonacci(n - 1) + fibonacci(n - 2)

• First Recursive Call: function makes a recursive call to calculate fibonacci(4)
• Base Case Check (First Recursive Call): base case is not met for n = 4, so we proceed to the recursive case

else:
return fibonacci(4 - 1) + fibonacci(4 - 2)

• Second Recursive Call (First Nested): function makes another recursive call to calculate fibonacci(3)
• Base Case Check (First Nested Recursive Call): once again, the base case is not met for n=3

else:
return fibonacci(3 - 1) + fibonacci(3 - 2)

• Third Recursive Call (First Nested): another recursive call is made to calculate fibonacci(2)
• Base Case Check (First Nested Recursive Call): base case is met for n = 2. The function returns 2

if n == 0 or n == 1:
return n

• First Nested Recursive Return: recursive call fibonacci(2) returns 2
• Second Nested Recursive Return (First Nested): recursive call fibonacci(3) receives the result (2) and makes another recursive call to fibonacci(1)
• Base Case Check (Second Nested Recursive Call): base case is met for n = 1. The function returns 1

if n == 0 or n == 1:
return n

• Second Nested Recursive Return: The recursive call fibonacci(1) returns 1
• First Recursive Return: recursive call fibonacci(3) receives the results (2 and 1) and returns 3
• Second Recursive Return: recursive call fibonacci(4) receives the results (3 and 2) and returns 5
• Final Return: initial call to fibonacci(5) receives the result (5) and returns 5 + 3 = 8
• Result: final result is fibonacci(5) = 8

Factorial

• Mathematical formula: n! = n * (n-1) * (n-2) * … * 2 * 1
• Initial Call: factorial(5)
• Base Case Check: function checks if the base case is met. In this case, if n is 0 or 1, the factorial is 1. Since 5 is not 0 or 1, we proceed to the recursive case

if n == 0 or n == 1:
return 1

• Recursive Case: since n is 5, we enter the recursive case

else:
return n * factorial(n - 1)

• Recursive Call: The function makes a recursive call to calculate factorial(4)
• Base Case Check (Recursive Call): again, the base case is not met for n = 4, so we proceed to the recursive case
• Recursive Call (Nested): function makes another recursive call to calculate factorial(3)
• Base Case Check (Nested Recursive Call): once again, the base case is not met for n = 3
• Recursive Call (Further Nested): another recursive call is made to calculate factorial(2)
• Base Case Check (Further Nested Recursive Call): the base case is not met for n = 2
• Recursive Call (Deeper Nesting): final recursive call is made to calculate factorial(1)
• Base Case Check (Deeper Nesting Recursive Call): now, the base case is met for n = 1. The function returns 1

if n == 0 or n == 1:
return 1

• Recursive Return (Deeper Nesting): recursive call factorial(1) returns 1
• Recursive Return (Further Nesting): recursive call factorial(2) receives the result (1) and returns 2 * 1 = 2
• Recursive Return (Nested): recursive call factorial(3) receives the result (2) and returns 3 * 2 = 6
• Recursive Return: recursive call factorial(4) receives the result (6) and returns4 * 6 = 24
• Final Return: initial call to factorial(5) receives the result (24) and returns 5 * 24 = 120
• Result: final result is 5! = 120

Practice

Practice

Factorial Recursive

factorial_recursive(n):
  if n == 0 or n == 1:
    return 1
return n * factorial_recursive(n - 1)

Factorial Iterative

factorial_iterative(n):
  result = 1
  for i in range(1, n + 1):
    result *= i
  return result

Factorial Memoization

factorial_memoization(n, memo={}):
  if n == 0 or n == 1:
    return 1
  if n not in memo:
    memo[n] = n * factorial_memoization(n - 1, memo)
  return memo[n]

Factorial Tabulation

factorial_tabulation(n):
  table = [1] * (n + 1)
  for i in range(2, n + 1):
    table[i] = i * table[i - 1]
  return table[n]

Fibonacci Recursive

fibonacci_recursive(n):
  if n <= 1:
    return n
  return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)

Fibonacci Iterative

fibonacci_iterative(n):
  if n <= 1:
    return n
  a, b = 0, 1
  for _ in range(n - 1):
    a, b = b, a + b
  return b

Fibonacci Memoization

fibonacci_memoization(n, memo={}):
  if n <= 1:
    return n
  if n not in memo:
    memo[n] = fibonacci_memoization(n - 1, memo) + fibonacci_memoization(n - 2, memo)
  return memo[n]

Fibonacci Tabulation

fibonacci_tabulation(n):
  if n <= 1:
    return n
  table = [0] * (n + 1)
  table[1] = 1
  for i in range(2, n + 1):
    table[i] = table[i - 1] + table[i - 2]
  return table[n]

Solution

package main

func factorialRecursive(n int) int {
    if n == 0 || n == 1 {
        return 1
    }
    return n * factorialRecursive(n-1)
}

func factorialIterative(n int) int {
    result := 1
    for i := 1; i <= n; i++ {
        result *= i
    }
    return result
}

func factorialMemoization(n int, memo map[int]int) int {
    if n == 0 || n == 1 {
        return 1
    }
    if val, ok := memo[n]; ok {
        return val
    }
    memo[n] = n * factorialMemoization(n-1, memo)
    return memo[n]
}

func factorialTabulation(n int) int {
    table := make([]int, n+1)
    table[0], table[1] = 1, 1
    for i := 2; i <= n; i++ {
        table[i] = i * table[i-1]
    }
    return table[n]
}

func fibonacciRecursive(n int) int {
    if n <= 1 {
        return n
    }
    return fibonacciRecursive(n-1) + fibonacciRecursive(n-2)
}

func fibonacciIterative(n int) int {
    if n <= 1 {
        return n
    }
    a, b := 0, 1
    for i := 2; i <= n; i++ {
        a, b = b, a+b
    }
    return b
}

func fibonacciMemoization(n int, memo map[int]int) int {
    if n <= 1 {
        return n
    }
    if val, ok := memo[n]; ok {
        return val
    }
    memo[n] = fibonacciMemoization(n-1, memo) + fibonacciMemoization(n-2, memo)
    return memo[n]
}

func fibonacciTabulation(n int) int {
    if n <= 1 {
        return n
    }
    table := make([]int, n+1)
    table[1] = 1
    for i := 2; i <= n; i++ {
        table[i] = table[i-1] + table[i-2]
    }
    return table[n]
}

import java.util.HashMap;

public class Recursion {

  static int factorialRecursive(int n) {
    if (n == 0 || n == 1) {
      return 1;
    }
    return n * factorialRecursive(n - 1);
  }

  static int factorialIterative(int n) {
    int result = 1;
    for (int i = 1; i <= n; i++) {
      result *= i;
    }
    return result;
  }

  static int factorialMemoization(int n, HashMap<Integer, Integer> memo) {
    if (n == 0 || n == 1) {
      return 1;
    }
    if (memo.containsKey(n)) {
      return memo.get(n);
    }
    int result = n * factorialMemoization(n - 1, memo);
    memo.put(n, result);
    return result;
  }

  static int factorialTabulation(int n) {
    int[] table = new int[n + 1];
    table[0] = 1;
    for (int i = 1; i <= n; i++) {
      table[i] = i * table[i - 1];
    }
    return table[n];
  }

  static int fibonacciRecursive(int n) {
    if (n <= 1) {
      return n;
    }
    return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
  }

  static int fibonacciIterative(int n) {
    if (n <= 1) {
      return n;
    }
    int a = 0, b = 1;
    for (int i = 2; i <= n; i++) {
      int temp = a + b;
      a = b;
      b = temp;
    }
    return b;
  }

  static int fibonacciMemoization(int n, HashMap<Integer, Integer> memo) {
    if (n <= 1) {
      return n;
    }
    if (memo.containsKey(n)) {
      return memo.get(n);
    }
    int result = fibonacciMemoization(n - 1, memo) + fibonacciMemoization(n - 2, memo);
    memo.put(n, result);
    return result;
  }

  static int fibonacciTabulation(int n) {
    if (n <= 1) {
      return n;
    }
    int[] table = new int[n + 1];
    table[1] = 1;
    for (int i = 2; i <= n; i++) {
      table[i] = table[i - 1] + table[i - 2];
    }
    return table[n];
  }
}

function factorialRecursive(n) {
  if (n === 0 || n === 1) {
    return 1;
  }
  return n * factorialRecursive(n - 1);
}

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

function factorialMemoization(n, memo = {}) {
  if (n === 0 || n === 1) {
    return 1;
  }
  if (memo[n]) {
    return memo[n];
  }
  const result = n * factorialMemoization(n - 1, memo);
  memo[n] = result;
  return result;
}

function factorialTabulation(n) {
  const table = Array(n + 1).fill(1);
  for (let i = 2; i <= n; i++) {
    table[i] = i * table[i - 1];
  }
  return table[n];
}

function fibonacciRecursive(n) {
  if (n <= 1) {
    return n;
  }
  return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
}

function fibonacciIterative(n) {
  if (n <= 1) {
    return n;
  }
  let a = 0,
    b = 1;
  for (let i = 2; i <= n; i++) {
    const temp = a + b;
    a = b;
    b = temp;
  }
  return b;
}

function fibonacciMemoization(n, memo = {}) {
  if (n <= 1) {
    return n;
  }
  if (memo[n]) {
    return memo[n];
  }
  const result =
    fibonacciMemoization(n - 1, memo) + fibonacciMemoization(n - 2, memo);
  memo[n] = result;
  return result;
}

function fibonacciTabulation(n) {
  if (n <= 1) {
    return n;
  }
  const table = [0, 1];
  for (let i = 2; i <= n; i++) {
    table[i] = table[i - 1] + table[i - 2];
  }
  return table[n];
}

import java.util.HashMap

fun factorialRecursive(n: Int): Int {
    return if (n == 0 || n == 1) {
        1
    } else {
        n * factorialRecursive(n - 1)
    }
}

fun factorialIterative(n: Int): Int {
    var result = 1
    for (i in 2..n) {
        result *= i
    }
    return result
}

fun factorialMemoization(n: Int, memo: HashMap<Int, Int>): Int {
    return if (n == 0 || n == 1) {
        1
    } else {
        if (memo.containsKey(n)) {
            memo[n]!!
        } else {
            val result = n * factorialMemoization(n - 1, memo)
            memo[n] = result
            result
        }
    }
}

fun factorialTabulation(n: Int): Int {
    val table = IntArray(n + 1) { 1 }
    for (i in 2..n) {
        table[i] = i * table[i - 1]
    }
    return table[n]
}

fun fibonacciRecursive(n: Int): Int {
    return if (n <= 1) {
        n
    } else {
        fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2)
    }
}

fun fibonacciIterative(n: Int): Int {
    var a = 0
    var b = 1
    for (i in 2..n) {
        val temp = a + b
        a = b
        b = temp
    }
    return b
}

fun fibonacciMemoization(n: Int, memo: HashMap<Int, Int>): Int {
    return if (n <= 1) {
        n
    } else {
        if (memo.containsKey(n)) {
            memo[n]!!
        } else {
            val result = fibonacciMemoization(n - 1, memo) + fibonacciMemoization(n - 2, memo)
            memo[n] = result
            result
        }
    }
}

fun fibonacciTabulation(n: Int): Int {
    if (n <= 1) {
        return n
    } else {
        val table = IntArray(n + 1)
        table[1] = 1
        for (i in 2..n) {
            table[i] = table[i - 1] + table[i - 2]
        }
        return table[n]
    }
}

def factorial_recursive(n):
    if n == 0 or n == 1:
        return 1
    return n * factorial_recursive(n - 1)

def factorial_iterative(n):
    result = 1
    for i in range(1, n + 1):
        result *= i
    return result

def factorial_memoization(n, memo={}):
    if n == 0 or n == 1:
        return 1
    if n not in memo:
        memo[n] = n * factorial_memoization(n - 1, memo)
    return memo[n]

def factorial_tabulation(n):
    table = [1] * (n + 1)
    for i in range(2, n + 1):
        table[i] = i * table[i - 1]
    return table[n]

def fibonacci_recursive(n):
    if n <= 1:
        return n
    return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)

def fibonacci_iterative(n):
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(n - 1):
        a, b = b, a + b
    return b

def fibonacci_memoization(n, memo={}):
    if n <= 1:
        return n
    if n not in memo:
        memo[n] = fibonacci_memoization(n - 1, memo) + fibonacci_memoization(n - 2, memo)
    return memo[n]

def fibonacci_tabulation(n):
    if n <= 1:
        return n
    table = [0] * (n + 1)
    table[1] = 1
    for i in range(2, n + 1):
        table[i] = table[i - 1] + table[i - 2]
    return table[n]

fn factorial_recursive(n: u64) -> u64 {
    if n == 0 || n == 1 {
        1
    } else {
        n * factorial_recursive(n - 1)
    }
}

fn factorial_iterative(n: u64) -> u64 {
    (1..=n).product()
}

use std::collections::HashMap;
fn factorial_memoization(n: u64, memo: &mut HashMap<u64, u64>) -> u64 {
    if n == 0 || n == 1 {
        1
    } else {
        if let Some(&result) = memo.get(&n) {
            result
        } else {
            let result = n * factorial_memoization(n - 1, memo);
            memo.insert(n, result);
            result
        }
    }
}

fn factorial_tabulation(n: u64) -> u64 {
    let mut table = vec![1; (n + 1) as usize];
    for i in 2..=n as usize {
        table[i] = i as u64 * table[i - 1];
    }
    table[n as usize]
}

fn fibonacci_recursive(n: u64) -> u64 {
    if n <= 1 {
        n
    } else {
        fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)
    }
}

fn fibonacci_iterative(n: u64) -> u64 {
    let (mut a, mut b) = (0, 1);
    for _ in 2..=n {
        let temp = a + b;
        a = b;
        b = temp;
    }
    b
}

fn fibonacci_memoization(n: u64, memo: &mut HashMap<u64, u64>) -> u64 {
    if n <= 1 {
        n
    } else {
        if let Some(&result) = memo.get(&n) {
            result
        } else {
            let result = fibonacci_memoization(n - 1, memo) + fibonacci_memoization(n - 2, memo);
            memo.insert(n, result);
            result
        }
    }
}

fn fibonacci_tabulation(n: u64) -> u64 {
    if n <= 1 {
        n
    } else {
        let mut table = vec![0; (n + 1) as usize];
        table[1] = 1;
        for i in 2..=n as usize {
            table[i] = table[i - 1] + table[i - 2];
        }
        table[n as usize]
    }
}

function factorialRecursive(n: number): number {
  return n <= 1 ? 1 : n * factorialRecursive(n - 1);
}

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

function factorialMemoization(
  n: number,
  memo: Map<number, number> = new Map(),
): number {
  if (n <= 1) {
    return 1;
  }

  if (memo.has(n)) {
    return memo.get(n)!;
  }

  const result = n * factorialMemoization(n - 1, memo);
  memo.set(n, result);
  return result;
}

function factorialTabulation(n: number): number {
  const table = new Array(n + 1).fill(1);
  for (let i = 2; i <= n; i++) {
    table[i] = i * table[i - 1];
  }
  return table[n];
}

function fibonacciRecursive(n: number): number {
  return n <= 1 ? n : fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
}

function fibonacciIterative(n: number): number {
  if (n <= 1) {
    return n;
  }
  let a = 0,
    b = 1;
  for (let i = 2; i <= n; i++) {
    const temp = a + b;
    a = b;
    b = temp;
  }
  return b;
}

function fibonacciMemoization(
  n: number,
  memo: Map<number, number> = new Map(),
): number {
  if (n <= 1) {
    return n;
  }

  if (memo.has(n)) {
    return memo.get(n)!;
  }

  const result =
    fibonacciMemoization(n - 1, memo) + fibonacciMemoization(n - 2, memo);
  memo.set(n, result);
  return result;
}

function fibonacciTabulation(n: number): number {
  if (n <= 1) {
    return n;
  }

  const table = new Array(n + 1).fill(0);
  table[1] = 1;

  for (let i = 2; i <= n; i++) {
    table[i] = table[i - 1] + table[i - 2];
  }

  return table[n];
}