Python Functions & Recursion

Functions are self-contained blocks of code that perform a specific task. They help organize code into manageable pieces, reduce repetition, and make programs easier to understand and maintain.

Why Use Functions?

• Code Reusability: Write once, use multiple times
• Modularity: Break complex problems into smaller, manageable pieces
• Abstraction: Hide implementation details, focus on what the function does
• Maintainability: Easier to debug and update code
• Collaboration: Different programmers can work on different functions

Function Components

# Function definition
def function_name(parameters):
    """docstring"""  # Optional documentation
    # function body
    # ...
    return value  # Optional return statement

# Function call
result = function_name(arguments)

# Example
def greet(name):
    return f"Hello, {name}!"

message = greet("Alice")
print(message)  # Output: Hello, Alice!

# Return statement
def add(a, b):
    return a + b  # Returns the sum

# Functions without return statement return None
def print_sum(a, b):
    print(a + b)  # Prints but returns None

result = add(3, 5)  # result = 8
result = print_sum(3, 5)  # Prints 8, result = None

Python functions follow a specific syntax that makes them flexible yet consistent. Understanding the syntax is key to writing effective functions.

Basic Syntax Rules

1. Start with the def keyword followed by the function name and parentheses
2. Parameters are placed inside the parentheses (can be empty)
3. End the line with a colon
4. The function body is indented (typically 4 spaces)
5. Optional return statement to send a value back to the caller
6. Optional docstring to document the function's purpose

Anatomy of a Function

def calculate_grade(score, max_score=100):
    """
    Calculate a letter grade based on percentage.
    
    Args:
        score (float): The student's score
        max_score (float): Maximum possible score (default 100)
        
    Returns:
        str: Letter grade (A, B, C, D, or F)
    """
    percentage = (score / max_score) * 100
    
    if percentage >= 90:
        return "A"
    elif percentage >= 80:
        return "B"
    elif percentage >= 70:
        return "C"
    elif percentage >= 60:
        return "D"
    else:
        return "F"

# Using the function
grade = calculate_grade(85)
print(f"Grade: {grade}")  # Output: Grade: B

Parameters are variables in a function definition, while arguments are the actual values passed to the function when it's called. Python supports several types of parameters.

Types of Parameters

Parameter Examples

# Positional arguments
def describe_pet(animal_type, pet_name):
    print(f"I have a {animal_type} named {pet_name}.")

# These calls are equivalent
describe_pet("hamster", "Harry")  # Positional
describe_pet(animal_type="hamster", pet_name="Harry")  # Keyword
describe_pet(pet_name="Harry", animal_type="hamster")  # Order doesn't matter with keywords

# Default parameter values
def describe_pet(pet_name, animal_type="dog"):
    print(f"I have a {animal_type} named {pet_name}.")

describe_pet("Willie")  # animal_type defaults to "dog"
describe_pet("Harry", "hamster")  # animal_type is "hamster"

# Important: Mutable default values can be problematic
def add_item(item, items=[]):  # Wrong - same list used in all calls
    items.append(item)
    return items

def add_item_fixed(item, items=None):  # Correct
    if items is None:
        items = []
    items.append(item)
    return items

# Variable-length arguments
def make_pizza(*toppings):
    """Print the list of toppings that have been requested."""
    print("Making a pizza with the following toppings:")
    for topping in toppings:
        print(f"- {topping}")

make_pizza('pepperoni')
make_pizza('mushrooms', 'green peppers', 'extra cheese')

# Combining with regular parameters
def build_profile(first, last, **user_info):
    """Build a dictionary containing everything we know about a user."""
    user_info['first_name'] = first
    user_info['last_name'] = last
    return user_info

user_profile = build_profile('albert', 'einstein',
                             location='princeton',
                             field='physics')
print(user_profile)

Variable scope determines where in your program a variable is accessible. Python has four types of variable scopes.

Types of Variable Scope

Scope Examples

# Global variable
global_var = "I'm global"

def test_scope():
    # Local variable
    local_var = "I'm local"
    print(global_var)  # Accessible: I'm global
    print(local_var)   # Accessible: I'm local
    
    def inner_function():
        # Enclosing scope
        inner_var = "I'm in inner function"
        print(local_var)  # Accessible: I'm local
        print(global_var) # Accessible: I'm global
        
    inner_function()
    # print(inner_var)  # Not accessible - would cause error

test_scope()
# print(local_var)  # Not accessible - would cause error

The global and nonlocal Keywords

x = "global"

def outer():
    x = "outer"  # Enclosing scope
    
    def inner():
        nonlocal x  # Refers to x in the enclosing (outer) scope
        x = "inner"  # Modifies the outer x
        
    inner()
    print(x)  # Output: inner

def change_global():
    global x  # Refers to the global x
    x = "changed"  # Modifies the global x

outer()
print(x)  # Output: global (not changed by nonlocal)

change_global()
print(x)  # Output: changed

Python comes with many built-in functions that are always available. These functions perform common tasks and are optimized for performance.

Commonly Used Built-in Functions

length = len("Hello")  # 5
length = len([1, 2, 3])  # 3

t = type(5)  # <class 'int'>
t = type("hello")  # <class 'str'>

numbers = range(5)  # 0, 1, 2, 3, 4
numbers = range(1, 6)  # 1, 2, 3, 4, 5
numbers = range(0, 10, 2)  # 0, 2, 4, 6, 8

lst = list([1, 2, 3])
d = dict(a=1, b=2)
s = set([1, 2, 3])
t = tuple([1, 2, 3])

numbers = [3, 1, 4, 2]
sorted_nums = sorted(numbers)  # [1, 2, 3, 4]
sorted_nums = sorted(numbers, reverse=True)  # [4, 3, 2, 1]

numbers = [1, 2, 3, 4, 5, 6]
even = filter(lambda x: x % 2 == 0, numbers)
# even = [2, 4, 6]

Interactive Built-in Functions Demo

Recursion is a technique where a function calls itself to solve a problem by breaking it down into smaller subproblems of the same type.

Key Elements of Recursion

• Base Case: The condition that stops the recursion
• Recursive Case: The part where the function calls itself
• Progress Toward Base Case: Each recursive call should move closer to the base case

Classic Recursion Example: Factorial

def factorial(n):
    """
    Calculate n! using recursion.
    
    n! = n * (n-1) * (n-2) * ... * 1
    0! = 1 (by definition)
    """
    # Base case
    if n == 0:
        return 1
    # Recursive case
    else:
        return n * factorial(n - 1)

# Test the function
print(factorial(5))  # Output: 120
print(factorial(0))  # Output: 1

Another Example: Fibonacci Sequence

def fibonacci(n):
    """
    Return the nth Fibonacci number.
    
    Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, ...
    Each number is the sum of the two preceding ones.
    """
    # Base cases
    if n == 0:
        return 0
    elif n == 1:
        return 1
    # Recursive case
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)

# Test the function
for i in range(10):
    print(f"F({i}) = {fibonacci(i)}")

When to Use Recursion

• Problems that can be naturally divided into similar subproblems
• Tree and graph traversal algorithms
• Problems with recursive mathematical definitions (factorial, Fibonacci)
• Divide and conquer algorithms (merge sort, quick sort)
• Backtracking algorithms (solving puzzles, maze navigation)

When to Avoid Recursion

• Problems with simple iterative solutions
• When recursion depth might be too large (Python has a recursion limit)
• Performance-critical applications where iterative solutions are faster

Here are some practical examples of functions and recursion in real-world scenarios.

def calculator(a, b, operation='add'):
    operations = {
        'add': a + b,
        'subtract': a - b,
        'multiply': a * b,
        'divide': a / b if b != 0 else 'Error: Division by zero'
    }
    return operations.get(operation, 'Invalid operation')

result = calculator(10, 5, 'multiply')
print(result)  # Output: 50

def get_valid_input(prompt, input_type=str, 
                   validation_func=lambda x: True):
    while True:
        try:
            user_input = input_type(input(prompt))
            if validation_func(user_input):
                return user_input
            else:
                print("Invalid input. Try again.")
        except ValueError:
            print("Invalid format. Try again.")

# Example usage
age = get_valid_input("Enter your age: ", int, 
                     lambda x: 0 <= x <= 120)

def count_words(filename):
    try:
        with open(filename, 'r') as file:
            content = file.read()
            words = content.split()
            return len(words)
    except FileNotFoundError:
        return f"The file {filename} was not found."

word_count = count_words('sample.txt')
print(f"Word count: {word_count}")

Interactive Recursion Demo: Fibonacci Sequence

Advanced Example: Recursive File Search

import os

def find_files(directory, pattern):
    """
    Recursively find all files in directory that match pattern.
    
    Args:
        directory (str): Path to search in
        pattern (str): Pattern to match (e.g., '*.txt')
        
    Returns:
        list: Paths of matching files
    """
    matches = []
    try:
        for item in os.listdir(directory):
            path = os.path.join(directory, item)
            if os.path.isfile(path):
                if pattern in item:
                    matches.append(path)
            elif os.path.isdir(path):
                # Recursive call for subdirectories
                matches.extend(find_files(path, pattern))
    except PermissionError:
        print(f"Permission denied: {directory}")
    return matches

# Find all Python files in current directory and subdirectories
python_files = find_files('.', '.py')
for file in python_files:
    print(file)

Follow these best practices to write clean, maintainable, and efficient functions.

1. Write Clear, Descriptive Names

# Bad function names
def proc_data(d): 
    # unclear what it does
def x(y, z):
    # meaningless names

# Good function names
def calculate_average(grades):
    # clear what it does
def validate_email_address(email):
    # descriptive and specific

2. Keep Functions Focused and Short

# Too many responsibilities
def process_user_data(user_data):
    # validates data
    # saves to database
    # sends welcome email
    # generates report
    # ... too many things!

# Better - separate concerns
def validate_user_data(user_data):
    # validation only

def save_user_to_db(user_data):
    # database operations only

def send_welcome_email(user_email):
    # email sending only

3. Use Docstrings for Documentation

def calculate_compound_interest(principal, rate, time, compounds_per_year):
    """
    Calculate compound interest.
    
    Formula: A = P(1 + r/n)^(nt)
    
    Args:
        principal (float): Initial investment
        rate (float): Annual interest rate (as decimal)
        time (float): Time in years
        compounds_per_year (int): Number of compounding periods per year
        
    Returns:
        float: Final amount after compound interest
    """
    return principal * (1 + rate/compounds_per_year) ** (compounds_per_year * time)

4. Avoid Side Effects When Possible

# Function with side effect (modifies external state)
total = 0

def add_to_total(amount):
    global total
    total += amount  # side effect

# Better - pure function (no side effects)
def add_numbers(a, b):
    return a + b  # no side effects, same input always gives same output

5. Use Appropriate Parameter Types

# Use default parameters for optional values
def connect_to_db(host='localhost', port=5432, timeout=30):
    # connection logic

# Use *args for variable positional arguments
def sum_numbers(*args):
    return sum(args)

# Use **kwargs for variable keyword arguments  
def create_person(**attributes):
    return attributes

6. Handle Errors Gracefully

def safe_divide(dividend, divisor):
    """
    Safely divide two numbers.
    
    Returns:
        float: Result of division, or None if division by zero
    """
    try:
        return dividend / divisor
    except ZeroDivisionError:
        print("Error: Division by zero")
        return None
    except TypeError:
        print("Error: Both arguments must be numbers")
        return None

7. Recursion Best Practices

• Always define a base case to prevent infinite recursion
• Ensure each recursive call progresses toward the base case
• Consider using memoization to cache results and avoid redundant calculations
• Be aware of Python's recursion limit (usually around 1000)
• For deep recursion, consider iterative solutions or increasing recursion limit

# Recursion with memoization
def fibonacci_memo(n, memo={}):
    """
    Fibonacci with memoization to improve performance.
    """
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fibonacci_memo(n-1, memo) + fibonacci_memo(n-2, memo)
    return memo[n]