Understanding Recursion

1.1 Definition of Recursion and its Key Concepts.

Recursion is when something does itself over and over again. Imagine you've got instructions, and part of those instructions is to follow the instructions themselves. It's like you're giving a command to repeat the command.

Real-life examples:

Mirrors opposite each other:

Imagine you're standing between two mirrors. You see your reflection, and in that reflection, you see another reflection, and it goes on and on. This is an example of recursion because each mirror shows the reflection of the other mirror.

Nesting Dolls:

A nesting doll is a doll that has another doll inside it, and inside that is yet another one, and so on. When you reach the smallest doll, there's nothing more to open. This is like the base case in recursion — the point where you stop.

Pizza Slicing:

Imagine you're cutting a pizza in half. Then you take one half and cut it in half again, and continue this until the slices are too small to cut. The cutting process is recursive, and the point where you can't cut anymore is the base case.

Important! Recursion isn't just about repeating a command infinitely, but more like breaking down a complex task into parts, where the approach to solving the parts is the same as solving the whole task.

How does it work?

To understand recursion, you should know two key concepts:

• Base Case: this is the condition where recursion stops. For example, in the nesting doll example, the base case is when you open the smallest doll and there's nothing inside.
• Recursive Case: this is when the task is repeated with smaller parts. In the pizza example, you cut a piece, then cut the half, and so on.

Why is it useful?

Recursion helps solve complex tasks by breaking them into simpler parts. Instead of solving the entire task at once, you solve it piece by piece.

Other Life Examples:

Story within a Story:

Imagine the hero of a story is telling another story, and the hero of that story begins another story. When one of the stories ends, you go back to the previous story. The base case is when the last story ends.

Recursive Drawing:

You draw a big triangle, then at each corner of that triangle, you draw a smaller triangle, and so on until the triangles are too small to draw. The base case is when the triangle gets so small you can't draw it anymore.

1.2 Base Case: Definition and Examples.

Base Case is the condition that stops the recursive calls and allows the function to return a specific value. It's usually the simplest and most obvious solution to the task that doesn't require further recursion.

Examples of base cases:

Factorial of a Number:

The factorial of a number n is denoted as F(n) == 1*2*3*…*n. It's also clear that F(n) == n* F(n-1).

Base Case: the factorial of 0 or 1 is 1. F(0) == F(1)==1

def factorial(n):
    if n == 0 or n == 1:
        return 1  # Base case
    else:
        return n * factorial(n - 1)
        

Fibonacci Numbers:

Fibonacci numbers are a sequence: 1, 1, 2, 3, 5, 8, 13, … Where each number is the sum of the two preceding ones. For F(n) == F(n-1) + F(n-2)

Base Case: the first two Fibonacci numbers are 1, therefore the "zeroth" Fibonacci number is 0. Or F(0) = 0 and F(1) = 1.

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

1.3 Recursive Case: Definition and Examples

Recursive Case is the part of the function that solves a task by calling itself with new parameters that bring the solution closer to the base case. Each recursive call reduces or modifies the task to eventually reach the base case.

Examples of Recursive Cases:

Factorial of a Number:

Recursive case: the factorial of a number n is n multiplied by the factorial of n-1.

def factorial(n):
    if n == 0 or n == 1:
        return 1  # Base case
    else:
        return n * factorial(n - 1)  # Recursive case
        

Fibonacci Numbers:

Recursive case: F(n) is the sum of F(n-1) and F(n-2).

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

1.4 Examples of Recursive Algorithms

1. Traversing a Binary Tree:

Example of "in-order" traversal.

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
        
def inorder_traversal(node):
    if node:
        inorder_traversal(node.left)
        print(node.value)
        inorder_traversal(node.right)
        
# Example usage:
root = Node(1)
root.left = Node(2)
root.right = Node(3)
inorder_traversal(root)
        

2. Finding the Maximum Element in a List:

def find_max(lst):
    if len(lst) == 1:
        return lst[0]  # Base case
    else:
        max_of_rest = find_max(lst[1:])  # Recursive case
        return max(lst[0], max_of_rest)
        
# Example usage:
print(find_max([1, 5, 3, 9, 2]))  # Output: 9
        
        

3. Recursive Binary Search:

def binary_search(arr, target, left, right):
    if left > right:
        return -1  # Base case: item not found
    mid = (left + right) // 2
    if arr[mid] == target:
        return mid  # Base case: item found
    elif arr[mid] < target:
        return binary_search(arr, target, mid + 1, right)  # Recursive case
    else:
        return binary_search(arr, target, left, mid - 1)  # Recursive case
        
# Example usage:
arr = [1, 2, 3, 4, 5, 6, 7]
print(binary_search(arr, 5, 0, len(arr) - 1))  # Output: 4