Unit 3: Functions and Recursion

1. Function Calls

A function is a named sequence of statements that performs a specific computation. When you define a function, you specify the name and the sequence of statements. Later, you can "call" the function by name.

1.1 Anatomy of a Function Call

The syntax for a function call is:

function_name(argument1, argument2, ...)

• The Caller: The code invoking the function.
• The Callee: The function being executed.
• Arguments: Values passed into the function parenthesis.

1.2 Fruitful vs. Void Functions

• Fruitful Functions: Functions that return a result. The return value can be assigned to a variable or used in an expression.
  
  PYTHON

      x = len("Hello") # len returns an integer (5)
      

• Void Functions: Functions that perform an action (like printing to the screen) but do not return a meaningful value. In Python, they technically return a special value called None.
  
  PYTHON

      result = print("Hello")
      print(result) # Output: None
      

1.3 Flow of Execution

When a function is called:

1. The program pauses execution at the point of the call.
2. Control transfers to the first line of the called function.
3. The body of the function is executed.
4. When the function ends (or hits a return statement), control returns to the caller, resuming exactly where it left off.

2. Type Conversion and Coercion

Python provides mechanisms to convert values from one data type to another. This can happen automatically (implicit) or manually (explicit).

2.1 Type Coercion (Implicit Conversion)

Python automatically converts one data type to another when it makes sense, usually to prevent data loss in mixed-mode arithmetic.

• Scenario: Adding an integer and a float.
• Behavior: Python promotes the integer to a float.

num_int = 12
num_float = 10.5

result = num_int + num_float
print(result)        # Output: 22.5
print(type(result))  # Output: <class 'float'>

2.2 Type Casting (Explicit Conversion)

This is when the programmer manually changes the data type using built-in functions.

Common Conversion Functions:

• int(x): Converts x to an integer.

  • Floats are truncated (decimals chopped off, not rounded).
  • Strings must look like integers.
    
    PYTHON

        int(3.99)   # Returns 3
        int("42")   # Returns 42
        # int("hello") -> ValueError
        # int("4.5")   -> ValueError (Cannot parse dot in integer string directly)
        

• float(x): Converts x to a floating-point number.
  

  PYTHON

      float(3)    # Returns 3.0
      float("3.14") # Returns 3.14
      

• str(x): Converts x to a string representation.
  

  PYTHON

      str(32)     # Returns "32"
      str(3.14)   # Returns "3.14"
      

3. Math Functions

Python provides a built-in module called math that extends the basic arithmetic operators (+, -, *, /) with complex mathematical functions.

3.1 Importing the Module

Before using math functions, the module must be imported.

import math

3.2 Common Math Functions

Access functions using dot notation: module_name.function_name().

3.3 Mathematical Constants

• math.pi: Mathematical constant (3.14159...)
• math.e: Mathematical constant (2.71828...)

4. Adding New Functions (Function Definition)

Defining functions allows you to break a program into smaller, manageable, and reusable chunks.

4.1 Syntax

def function_name(parameters):
    """
    Optional docstring explaining what the function does.
    """
    statement_1
    statement_2
    return value # Optional

• def: Keyword indicating the start of a function definition.
• Header: The first line (ending with a colon).
• Body: The indented block of code following the header.

4.2 Variable Scope (Local vs. Global)

• Local Variables: Variables defined inside a function. They exist only while the function is running and are destroyed when the function exits.
• Global Variables: Variables defined outside any function.
• Independence: A local variable inside a function can have the same name as a variable elsewhere; they are distinct variables.

4.3 Example: Defining a Function

def calculate_area(radius):
    """Calculates the area of a circle."""
    import math
    area = math.pi * (radius ** 2)
    return area

# Usage
result = calculate_area(5)
print(result)

5. Parameters and Arguments

While often used interchangeably, there is a technical distinction between parameters and arguments.

5.1 Definitions

• Parameter: The variable listed inside the parentheses in the function definition. (The placeholder).
• Argument: The actual value sent to the function when it is called. (The data).

5.2 Types of Arguments

Positional Arguments

Arguments must be passed in the correct order.

def subtract(a, b):
    return a - b

print(subtract(10, 5)) # Output: 5
print(subtract(5, 10)) # Output: -5 (Order matters)

Keyword Arguments

Arguments passed with key=value syntax. The order does not matter.

print(subtract(b=5, a=10)) # Output: 5

Default Parameters

You can provide a default value in the function definition. If the caller does not provide an argument, the default is used.

def greet(name, msg="Good morning"):
    print(f"Hello {name}, {msg}")

greet("Alice")                  # Uses default msg
greet("Bob", "How are you?")    # Overwrites default msg

Arbitrary Arguments (*args)

If you do not know how many arguments will be passed, use * before the parameter name. The function receives a tuple of arguments.

def sum_all(*numbers):
    total = 0
    for n in numbers:
        total += n
    return total

print(sum_all(1, 2, 3, 4)) # Output: 10

6. Recursion and its Use

Recursion is a programming technique where a function calls itself to solve a problem. It is a method of solving a problem where the solution depends on solutions to smaller instances of the same problem.

6.1 Anatomy of a Recursive Function

A recursive function must have two parts to avoid infinite loops:

1. Base Case: A condition where the function returns a value without making a recursive call. This stops the recursion.
2. Recursive Case: The part where the function calls itself with a modified argument (usually moving closer to the base case).

6.2 How Recursion Works (The Stack)

When a function calls itself, Python suspends the execution of the current function instance and pushes a new "stack frame" onto the memory stack. When the base case is reached, the stack unwinds, returning values back up the chain.

6.3 Example: Factorial

Mathematical definition:

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

print(factorial(4))

Execution Trace for factorial(3):

1. factorial(3) calls 3 * factorial(2)
2. factorial(2) calls 2 * factorial(1)
3. factorial(1) hits base case, returns 1
4. factorial(2) computes 2 * 1 -> returns 2
5. factorial(3) computes 3 * 2 -> returns 6

6.4 Example: Fibonacci Sequence

Sequence: 0, 1, 1, 2, 3, 5, 8...
Definition:

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

6.5 Uses and Limitations of Recursion

Uses:

• Solving problems that have a naturally recursive structure (e.g., tree traversals, graph search).
• Simplifying code for complex algorithms (e.g., QuickSort, MergeSort, Tower of Hanoi).
• Breaking down complex tasks into simpler sub-problems (Divide and Conquer).

Limitations:

• Memory Intensive: Every recursive call consumes stack memory. Too many calls lead to a RecursionError: maximum recursion depth exceeded.
• Performance: Recursive solutions (like the Fibonacci example above) can be slower than iterative loops due to function call overhead and redundant calculations unless optimized (memoization).