Recursion examples for Beginners (step by step code execution walkthrough with python code)

 

Factorial

Explanation and Example

Factorial Definition:

  • The factorial of a non-negative integer n is the product of all positive integers less than or equal to n.
  • It can be defined recursively as:
    • factorial(0) = 1 (Base Case)
    • factorial(n) = n * factorial(n-1) (Recursive Case)
    
    +----------------------------------+
    | factorial(n)                     |
    |      +---------------------------+
    |      | Base Case:                |
    |      |   factorial(0) = 1        |
    |      +---------------------------+
    |      | Recursive Case:           |
    |      |   factorial(n) = n *      |
    |      |                factorial(n-1)|
    |      +---------------------------+
    +----------------------------------+

Python Code for Factorial

    
    def factorial(n):
        if n == 0:
            return 1
        else:
            return n * factorial(n - 1)

    # Example Usage
    print(factorial(5))  # Output: 120

Step-by-Step Execution Walkthrough

Initial Call: factorial(5)

Function Call Stack

    
    factorial(5)
  • Input: n = 5
  • Calls: factorial(4)

Next Call

    factorial(5)
    factorial(4)
  • Input: n = 4
  • Calls: factorial(3)

Next Call

    factorial(5)
    factorial(4)
    factorial(3)
  • Input: n = 3
  • Calls: factorial(2)

Next Call

    factorial(5)
    factorial(4)
    factorial(3)
    factorial(2)
  • Input: n = 2
  • Calls: factorial(1)

Next Call

    factorial(5)
    factorial(4)
    factorial(3)
    factorial(2)
    factorial(1)
  • Input: n = 1
  • Calls: factorial(0)

Base Case Reached

    factorial(5)
    factorial(4)
    factorial(3)
    factorial(2)
    factorial(1)
    factorial(0)
  • Input: n = 0
  • Returns: 1

Returning Values

    factorial(1) returns 1 * 1 = 1
    factorial(2) returns 2 * 1 = 2
    factorial(3) returns 3 * 2 = 6
    factorial(4) returns 4 * 6 = 24
    factorial(5) returns 5 * 24 = 120 

Tree-like Structure for factorial(5)

factorial(5)
    |
    |-- Select 5:
    |
    |-- factorial(4)
    |   |
    |   |-- Select 4:
    |   |
    |   |-- factorial(3)
    |       |
    |       |-- Select 3:
    |       |
    |       |-- factorial(2)
    |           |
    |           |-- Select 2:
    |           |
    |           |-- factorial(1)
    |               |
    |               |-- Select 1:
    |               |
    |               |-- factorial(0)
    |                   |
    |                   |-- Select 0:
    |                   |
    |                   |-- Returns 1 (Base Case)
    |
    |-- Returns 1
    |-- Returns 1 * 1 = 1
    |-- Returns 2 * 1 = 2
    |-- Returns 3 * 2 = 6
    |-- Returns 4 * 6 = 24
    |-- Returns 5 * 24 = 120 

Fibonacci Numbers

Explanation and Example

Fibonacci Definition:

  • The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones, starting from 0 and 1.
  • It can be defined recursively as:
    • fibonacci(0) = 0 (Base Case)
    • fibonacci(1) = 1 (Base Case)
    • fibonacci(n) = fibonacci(n-1) + fibonacci(n-2) (Recursive Case)
    
    +-------------------------------------+
    | fibonacci(n)                        |
    |      +------------------------------+
    |      | Base Case:                   |
    |      |   fibonacci(0) = 0           |
    |      |   fibonacci(1) = 1           |
    |      +------------------------------+
    |      | Recursive Case:              |
    |      |   fibonacci(n) = fibonacci(  |
    |      |               n-1) + fibonacci(n-2)|
    |      +------------------------------+
    +-------------------------------------+

Python Code for Fibonacci

    
    def fibonacci(n):
        if n == 0:
            return 0
        elif n == 1:
            return 1
        else:
            return fibonacci(n - 1) + fibonacci(n - 2)

    # Example Usage
    print(fibonacci(5))  # Output: 5

Step-by-Step Execution Walkthrough

Initial Call: fibonacci(5)

Function Call Stack

    
    fibonacci(5)
  • Input: n = 5
  • Calls: fibonacci(4) and fibonacci(3)

Next Call

    fibonacci(5)
    fibonacci(4)
  • Input: n = 4
  • Calls: fibonacci(3) and fibonacci(2)

Next Call

    fibonacci(5)
    fibonacci(4)
    fibonacci(3)
  • Input: n = 3
  • Calls: fibonacci(2) and fibonacci(1)

Next Call

    fibonacci(5)
    fibonacci(4)
    fibonacci(3)
    fibonacci(2)
  • Input: n = 2
  • Calls: fibonacci(1) and fibonacci(0)

Base Cases Reached

  • fibonacci(1): Returns 1
  • fibonacci(0): Returns 0

Returning Values

    fibonacci(2) returns 1 + 0 = 1
    fibonacci(3) returns 1 + fibonacci(1) = 1 + 1 = 2
    fibonacci(4) returns 2 + fibonacci(2) = 2 + 1 = 3
    fibonacci(5) returns 3 + fibonacci(3) = 3 + 2 = 5

Tree-like Structure for fibonacci(5)

fibonacci(5)
    |
    |-- Select 5:
    |
    |-- fibonacci(4)
    |   |
    |   |-- Select 4:
    |   |
    |   |-- fibonacci(3)
    |       |
    |       |-- Select 3:
    |       |
    |       |-- fibonacci(2)
    |           |
    |           |-- Select 2:
    |           |
    |           |-- fibonacci(1)
    |               |
    |               |-- Select 1:
    |               |
    |               |-- Returns 1 (Base Case)
    |           |
    |           |-- fibonacci(0)
    |               |
    |               |-- Select 0:
    |               |
    |               |-- Returns 0 (Base Case)
    |
    |-- Returns 1 + 0 = 1
    |-- fibonacci(1)
    |   |
    |   |-- Select 1:
    |   |
    |   |-- Returns 1 (Base Case)
    |
    |-- Returns 1 + 1 = 2
    |-- fibonacci(2)
    |   |
    |   |-- Select 2:
    |   |
    |   |-- fibonacci(1)
    |       |
    |       |-- Select 1:
    |       |
    |       |-- Returns 1 (Base Case)
    |   |
    |   |-- fibonacci(0)
    |       |
    |       |-- Select 0:
    |       |
    |       |-- Returns 0 (Base Case)
    |
    |-- Returns 1 + 0 = 1
    |-- Returns 2 + 1 = 3
    |-- fibonacci(3)
    |   |
    |   |-- Select 3:
    |   |
    |   |-- fibonacci(2)
    |       |
    |       |-- Select 2:
    |       |
    |       |-- fibonacci(1)
    |           |
    |           |-- Select 1:
    |           |
    |           |-- Returns 1 (Base Case)
    |       |
    |       |-- fibonacci(0)
    |           |
    |           |-- Select 0:
    |           |
    |           |-- Returns 0 (Base Case)
    |
    |-- Returns 1 + 0 = 1
    |-- fibonacci(1)
    |   |
    |   |-- Select 1:
    |   |
    |   |-- Returns 1 (Base Case)
    |
    |-- Returns 1 + 1 = 2
    |-- Returns 3 + 2 = 5

Permutations

Explanation and Example

Permutations Definition:

  • A permutation is a re-arrangement of elements in a particular order.
  • For a given set of n elements, there are n! (n factorial) possible permutations.
  • It can be defined recursively as:
    • Permutations of an empty list ([]) is an empty list.
    • For each element in the list, we generate permutations by recursively permuting the rest of the elements and combining them.
    
    +-----------------------------------------+
    | permutations(lst)                       |
    |      +----------------------------------+
    |      | Base Case:                       |
    |      |   permutations([]) = [[]]        |
    |      +----------------------------------+
    |      | Recursive Case:                  |
    |      |   For each element in lst:       |
    |      |       Recursively permute rest   |
    |      |       Combine with current element|
    |      +----------------------------------+
    +-----------------------------------------+

Python Code for Permutations

    
    def permutations(lst):
        if len(lst) == 0:
            return [[]]
        perm_list = []
        for i in range(len(lst)):
            elem = lst[i]
            rest = lst[:i] + lst[i+1:]
            for p in permutations(rest):
                perm_list.append([elem] + p)
        return perm_list

    # Example Usage
    print(permutations([1, 2, 3]))

Step-by-Step Execution Walkthrough

Initial Call: permutations([1, 2, 3])

Function Call Stack

permutations([1, 2, 3])
  • Input: lst = [1, 2, 3]
  • Calls: permutations([2, 3]), permutations([1, 3]), permutations([1, 2])

Case 1: permutations([2, 3])

permutations([1, 2, 3]) permutations([2, 3])
  • Input: lst = [2, 3]
  • Calls: permutations([3]), permutations([2])

Next Call: permutations([3])

permutations([1, 2, 3]) permutations([2, 3]) permutations([3])
  • Input: lst = [3]
  • Calls: permutations([])

Base Case Reached

  • permutations([]): Returns [[]]

Returning Values

permutations([3]) returns [[3]] permutations([2, 3]) returns [[2, 3], [3, 2]]

Case 2: permutations([1, 3])

permutations([1, 2, 3]) permutations([1, 3])
  • Input: lst = [1, 3]
  • Calls: permutations([3]), permutations([1])

Next Call: permutations([3])

permutations([1, 2, 3]) permutations([1, 3]) permutations([3])
  • Input: lst = [3]
  • Calls: permutations([])

Base Case Reached

  • permutations([]): Returns [[]]

Returning Values

permutations([3]) returns [[3]] permutations([1, 3]) returns [[1, 3], [3, 1]]

Case 3: permutations([1, 2])

permutations([1, 2, 3]) permutations([1, 2])
  • Input: lst = [1, 2]
  • Calls: permutations([2]), permutations([1])

Next Call: permutations([2])

permutations([1, 2, 3]) permutations([1, 2]) permutations([2])
  • Input: lst = [2]
  • Calls: permutations([])

Base Case Reached

  • permutations([]): Returns [[]]

Returning Values

permutations([2]) returns [[2]] permutations([1, 2]) returns [[1, 2], [2, 1]]

Final Returning Values

permutations([1, 2, 3]) returns [ [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1] ] 

Tree-like Structure for permutations([1, 2, 3])

    
    permutations([1, 2, 3])
    |
    |-- Select 1:
    |
    |-- permutations([2, 3])
    |   |
    |   |-- Select 2:
    |   |
    |   |-- permutations([3])
    |   |   |
    |   |   |-- Select 3:
    |   |   |
    |   |   |-- permutations([])
    |   |   |   |
    |   |   |   |-- [[]]
    |   |   |
    |   |   |-- returns [[3]]
    |   |
    |   |-- Select 3:
    |       |
    |       |-- permutations([])
    |       |   |
    |       |   |-- [[]]
    |       |
    |       |-- returns [[2]]
    |
    |-- returns [[2, 3], [3, 2]]
    |
    |-- Select 2:
    |
    |-- permutations([1, 3])
    |   |
    |   |-- Select 1:
    |   |
    |   |-- permutations([3])
    |   |   |
    |   |   |-- Select 3:
    |   |   |
    |   |   |-- permutations([])
    |   |   |   |
    |   |   |   |-- [[]]
    |   |   |
    |   |   |-- returns [[3]]
    |   |
    |   |-- Select 3:
    |       |
    |       |-- permutations([1])
    |       |   |
    |       |   |-- permutations([])
    |       |   |   |
    |       |   |   |-- [[]]
    |       |   |
    |       |   |-- returns [[1]]
    |
    |-- returns [[1, 3], [3, 1]]
    |
    |-- Select 3:
    |
    |-- permutations([1, 2])
    |   |
    |   |-- Select 1:
    |   |
    |   |-- permutations([2])
    |   |   |
    |   |   |-- Select 2:
    |   |   |
    |   |   |-- permutations([])
    |   |   |   |
    |   |   |   |-- [[]]
    |   |   |
    |   |   |-- returns [[2]]
    |   |
    |   |-- Select 2:
    |       |
    |       |-- permutations([1])
    |       |   |
    |       |   |-- permutations([])
    |       |   |   |
    |       |   |   |-- [[]]
    |       |
    |       |-- returns [[1]]
    |
    |-- returns [[1, 2], [2, 1]]
    |
    |-- Final Result: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

Support Our Efforts and Earn Together ðŸš€

Visit https://parucodes.github.io/ today and start your journey to becoming a fast, accurate, and confident touch typist.

If you find our website useful and want to support us, consider joining the exciting world of Bitcoin mining on your mobile phone. Follow this link: Mine PI Bitcoin and use my username prarthanadp as your invitation code. With the referral code prarthanadp, you'll receive a special referral bonus.

Thank you for your support! Let's grow and earn together! 🌟

Comments

Post a Comment

Popular posts from this blog

Handling hierarchical Data using Dictionaries for beginners (with python code)

  Handling Hierarchical Data with Python Dictionaries 1. Introduction to Hierarchical Data Hierarchical data is organized into a tree-like structure with different levels of depth. Each level contains unique objects that are connected to objects in the level above. This type of data is common in various domains, such as organizational structures, file systems, and biological classifications. 2. Example Data We'll create a 5-level hierarchical data structure. The data represents an organizational hierarchy with departments, teams, managers, employees, and tasks. data = { "Department1": { "TeamA": { "Manager1": { "Employee1": { "Task1": "Complete report", "Task2": "Attend meeting" }, "Employee2": { "Task1": "Write...
Read more

Word Search in Maze using Depth First Search (with python code and step by step code execution walkthrough)

  1. Introduction In this blog, we will explain how to solve the word search problem in a maze using Depth First Search (DFS) algorithm. We will use a 3x3 maze and search for the word 'the' in the maze. The word 'the' is located in the second row of the maze. 2. Algorithm Explanation The DFS algorithm is used to explore all possible paths in the maze to find the target word. We start from each cell in the maze and recursively explore its neighbors to find the word. 2.1 Steps of the Algorithm Start from each cell in the maze. Check if the current cell matches the current character of the word. Mark the current cell as visited. Recursively explore the neighboring cells (up, down, left, right). Unmark the current cell and backtrack if the word is not found. Return true if the word is found, otherwise return false. 3. Python Code def dfs(maze, word, i, j, index): if index == len(word): return True if i < 0 or i >= len(maze) or j < 0 or j >= len(...
Read more