Functions, Procedures, and Recursion

Introduction and Context

A function is a named, reusable unit of computation. Functions enable programmers to divide a large problem into smaller responsibilities, reduce duplication, test components independently, and express algorithms at an appropriate level of abstraction. In Python and C++, functions are central to procedural, object-oriented, and functional programming.

A well-designed function does more than save lines of code. It establishes a clear contract: what inputs it accepts, what result it produces, what side effects it may have, and which assumptions must hold. This chapter develops function design from basic definitions to recursion and higher-order programming.

Learning Objectives

By the end of this chapter, students should be able to:

• define and call functions and procedures in Python and C++;
• use parameters, return values, default arguments, named arguments, and references;
• explain contracts, preconditions, postconditions, and invariants;
• distinguish local, global, and nonlocal scope and understand object lifetime;
• apply decomposition, cohesion, and separation of concerns;
• implement and analyse recursive algorithms;
• explain overloading and identify ambiguity in overloaded calls;
• pass functions as arguments and return callable behavior;
• evaluate practical limitations involving performance, testing, and maintainability.

1. Functions, Procedures, and Contracts

A function maps inputs to an output, although it may also perform observable actions. A procedure is commonly used to mean a callable unit whose primary purpose is an action rather than producing a useful value. Python does not syntactically distinguish functions from procedures: every `def` statement creates a function object, and a function that reaches the end without `return` returns `None`. C++ functions may return a value or have return type `void`.

A function contract specifies:

• Preconditions: what must be true before execution;
• Postconditions: what the function guarantees after successful execution;
• Side effects: changes to external state, files, output, or mutable objects;
• Exceptions or errors: conditions under which normal completion is not possible.

For example, a function computing an average may require a non-empty collection. Its postcondition is that the returned value equals the sum of the elements divided by their count. Stating the contract prevents callers from making unsafe assumptions.

```python

def mean(values):

"""Return the arithmetic mean of a non-empty iterable."""

values = list(values)

if not values:

raise ValueError("values must not be empty")

return sum(values) / len(values)

```

The function has a clear precondition and reports its violation explicitly. Without the check, division by zero would occur for an empty list.

In C++:

```cpp

#include <stdexcept>

#include <vector>

double mean(const std::vector<double>& values) {

if (values.empty()) {

throw std::invalid_argument("values must not be empty");

}

double total = 0.0;

for (double value : values) total += value;

return total / values.size();

}

```

The `const` reference avoids copying the vector and promises that the function will not modify it.

2. Parameters, Arguments, and Return Values

A parameter is a variable in a function definition; an argument is the value supplied at a call. Parameters may be positional, keyword-based, optional, or variadic.

Python

```python

def rectangle_area(width, height):

return width * height

area = rectangle_area(4, 2.5) # positional arguments: 10.0

area2 = rectangle_area(height=2.5, width=4) # keyword arguments: 10.0

```

Python permits default values and named arguments:

```python

def greet(name, greeting="Hello"):

return f"{greeting}, {name}!"

print(greet("Amina"))

print(greet(name="Amina", greeting="Welcome"))

```

Defaults are evaluated when the function definition executes. Mutable defaults should generally be avoided because the same object is reused across calls:

```python

Unsafe pattern

def add_item(item, items=[]):

items.append(item)

return items

Safe pattern

def add_item(item, items=None):

if items is None:

items = []

items.append(item)

return items

```

Python returns one object. Multiple apparent return values are implemented as a tuple:

```python

def quotient_remainder(a, b):

if b == 0:

raise ZeroDivisionError("b must not be zero")

return a // b, a % b

q, r = quotient_remainder(17, 5) # q = 3, r = 2

```

C++

C++ normally uses positional arguments, with default arguments specified in the declaration:

```cpp

#include <string>

std::string greet(const std::string& name,

const std::string& greeting = "Hello") {

return greeting + ", " + name + "!";

}

```

C++ does not have Python-style keyword arguments. Named values can be simulated with a configuration structure or designated construction pattern, but the language itself resolves calls positionally.

A function may return a value, a reference, a pointer, or `void`. Returning a reference to a local variable is invalid because the local object is destroyed when the function returns. Returning a reference to an object owned by the caller can be valid if its lifetime exceeds the use of the reference.

3. Passing Data: Value, Reference, and Mutation

In Python, arguments are passed by object reference (sometimes described as call-by-sharing). The function receives a reference to an object. Rebinding a parameter does not rebind the caller's variable, but mutation of a mutable object is visible to the caller.

```python

def rebind(number):

number = number + 1

def mutate(numbers):

numbers.append(4)

x = 3

rebind(x) # x remains 3

values = [1, 2, 3]

mutate(values) # values becomes [1, 2, 3, 4]

```

This distinction is important when designing contracts: a function should document whether it mutates an argument.

C++ gives explicit control:

```cpp

void increment_copy(int value) { ++value; }

void increment_reference(int& value) { ++value; }

void inspect(const int& value) { / cannot modify value / }

```

`increment_copy` changes only its local copy. `increment_reference` changes the caller's object. `const int&` avoids copying while preventing modification. A pointer can also express optionality or indirect access, but references are generally preferable when a valid object is required.

4. Function Design: Decomposition, Cohesion, and Separation of Concerns

Decomposition breaks a problem into functions with manageable responsibilities. Cohesion measures how closely related the tasks within one unit are. A highly cohesive function performs one conceptually focused task. Coupling describes dependence between units; lower unnecessary coupling generally improves maintainability.

Separation of concerns keeps different responsibilities apart. For example, an order-processing system might separate:

1. input validation;

2. price calculation;

3. tax calculation;

4. persistence;

5. user-interface formatting.

A function that reads user input, calculates tax, writes a database record, and prints a receipt is difficult to test because it combines unrelated concerns. A better design might use pure calculation functions and a separate orchestration function.

```python

def subtotal(prices):

return sum(prices)

def tax_amount(amount, rate):

if amount < 0 or rate < 0:

raise ValueError("amount and rate must be non-negative")

return amount * rate

def total_price(prices, rate):

amount = subtotal(prices)

return amount + tax_amount(amount, rate)

```

For prices `[10, 20]` and rate `0.15`, the subtotal is `30`, tax is `4.5`, and total is `34.5`. The functions are cohesive and can be tested independently.

A useful design heuristic is to ask whether a function can be named precisely without using “and.” This is not an absolute rule, but vague names often indicate excessive responsibility.

5. Scope, Lifetime, and Closures

Scope is the region in which a name can be resolved. Lifetime is the period during which an object exists. These are related but not identical: a global object can have program-long lifetime, while an object may outlive the scope in which it was created if another object retains a reference to it.

Python commonly follows the LEGB lookup order: Local, Enclosing, Global, Built-in.

```python

rate = 0.10

def price_with_tax(price):

rate = 0.20

return price * (1 + rate)

```

The local `rate` shadows the global `rate`; the function returns `price × 1.20`. Excessive global state creates hidden dependencies and makes testing harder. `global` and `nonlocal` exist but should be used deliberately.

A closure is a function that retains access to variables from an enclosing scope:

```python

def make_multiplier(factor):

def multiply(value):

return value * factor

return multiply

double = make_multiplier(2)

print(double(7)) # 14

```

The returned function retains `factor` after `make_multiplier` has finished. This is an example of returning callable behavior, not merely returning data.

In C++, local variables ordinarily have automatic storage duration and are destroyed when their block ends. Objects created with dynamic allocation have a lifetime controlled by ownership mechanisms; modern C++ prefers RAII and smart pointers over manual `new` and `delete`. A lambda can capture variables by value or reference, but a reference capture must not outlive the captured object.

6. Overloading and Interfaces

Overloading means using the same function name with different parameter lists. C++ supports compile-time function overloading:

```cpp

int absolute(int x) { return x < 0 ? -x : x; }

double absolute(double x) { return x < 0.0 ? -x : x; }

```

The compiler chooses a viable overload based on argument types. Return type alone cannot distinguish overloads. Calls can become ambiguous when multiple conversions are equally good, so overload sets should be small and coherent.

Python does not support traditional signature-based overloading. A later definition replaces an earlier one. Alternatives include default parameters, `*args`, type checking, or `functools.singledispatch`:

```python

from functools import singledispatch

@singledispatch

def describe(value):

return f"object: {value}"

@describe.register

def _(value: int):

return f"integer: {value}"

```

The decorator and the registered function are correctly aligned at the left margin. This is dispatch based on the first argument's type, not C++-style compile-time overloading.

7. Recursion

A recursive function calls itself on a smaller or simpler instance of the same problem. A correct recursive design requires:

1. a base case, which can be solved directly;

2. a recursive case, which moves toward the base case;

3. a proof or argument that progress terminates.

A recursive definition of factorial is:

a) `0! = 1` (base case); and

b) `n! = n × (n − 1)!` for positive integers `n`.

```python

def factorial(n):

if not isinstance(n, int) or n < 0:

raise ValueError("n must be a non-negative integer")

if n == 0:

return 1

return n * factorial(n - 1)

```

For `factorial(4)`, evaluation is `4 × 3 × 2 × 1 × factorial(0) = 24`. Each call consumes stack space. Python has a recursion limit and does not generally optimize tail calls, so an iterative solution is preferable for very deep computations.

A naïve recursive Fibonacci function has recurrence `T(n) = T(n−1) + T(n−2) + O(1)`, leading to exponential time, approximately `O(φ^n)` where `φ` is the golden ratio. Memoization changes the time complexity to `O(n)` and space complexity to `O(n)`:

```python

from functools import lru_cache

@lru_cache(maxsize=None)

def fibonacci(n):

if not isinstance(n, int) or n < 0:

raise ValueError("n must be a non-negative integer")

if n < 2:

return n

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

```

Here `fibonacci(10)` is `55`. The cache stores previously computed results. An iterative version uses `O(1)` additional space:

```python

def fibonacci_iterative(n):

if n < 0:

raise ValueError("n must be non-negative")

a, b = 0, 1

for _ in range(n):

a, b = b, a + b

return a

```

Recursion is particularly natural for trees, nested directories, divide-and-conquer algorithms, and grammars. It is not automatically superior: stack depth, repeated work, and debugging complexity must be considered.

8. Higher-Order Functions and Callable Behavior

A higher-order function accepts a function as an argument, returns a function, or both. This supports reusable policies such as sorting criteria, validation rules, and event handlers.

Python example:

```python

def apply_twice(function, value):

return function(function(value))

result = apply_twice(lambda x: x + 3, 4) # 10

```

C++ represents callable behavior with function pointers, function objects, lambdas, and `std::function`:

```cpp

#include <functional>

int apply_twice(const std::function<int(int)>& operation, int value) {

return operation(operation(value));

}

std::function<int(int)> make_adder(int amount) {

return [amount](int value) { return value + amount; };

}

int result = apply_twice(make_adder(3), 4); // 10

```

This example both passes callable behavior to `apply_twice` and returns callable behavior from `make_adder`. The lambda captures `amount` by value, so its lifetime is safe after `make_adder` returns. For performance-sensitive generic code, a function template may avoid `std::function`'s type-erasure overhead:

```cpp

template <typename Operation>

int apply_twice_generic(Operation operation, int value) {

return operation(operation(value));

}

```

Higher-order functions support abstraction, but excessive indirection can make control flow harder to understand. Names, types, documentation, and tests remain important.

9. Worked Application: A Validation Pipeline

Background

Consider an illustrative e-commerce registration service. It must validate a username, normalize an email address, and apply a configurable policy. Input handling should not be mixed with persistence or presentation.

Problem

A monolithic function would be difficult to test and would risk storing invalid data. The system needs reusable validation rules that can be composed.

Approach

```python

def nonempty(text):

return isinstance(text, str) and bool(text.strip())

def contains_at(text):

return isinstance(text, str) and text.count("@") == 1

def validate(value, rules):

return all(rule(value) for rule in rules)

def normalize_email(email):

cleaned = email.strip().lower()

if not validate(cleaned, [nonempty, contains_at]):

raise ValueError("invalid email")

return cleaned

```

`validate` is higher-order: it accepts a collection of functions. A service layer could call `normalize_email`, then pass the result to a repository. It should not allow a validation function to write to the database, because that would violate separation of concerns.

Outcome and Learning Points

The design makes each rule independently testable and permits new rules to be added without rewriting the validation engine. However, `contains_at` is intentionally a basic illustrative rule, not a complete email standard implementation. Production systems should use carefully selected libraries, security review, and verification workflows rather than assuming that a simple pattern fully validates an address.

10. Testing, Quality, and Professional Practice

Functions should be tested against normal cases, boundary cases, invalid inputs, and side effects. Pure functions are especially easy to test because their output depends only on explicit inputs. Property-based testing can check general claims, such as the fact that sorting preserves the number of elements, while unit tests check selected examples.

Documentation should state units, accepted types, mutation behavior, errors, and complexity when relevant. Type hints in Python and static types in C++ improve communication but do not replace runtime validation where external data is involved.

Security-sensitive functions should avoid hidden side effects, validate untrusted inputs, and protect confidential data. AI-generated code must be reviewed, executed in a controlled environment, tested, and checked for licensing, security, and correctness; plausible-looking function code can still contain unsafe assumptions or incorrect edge-case behavior.

Challenges and Limitations

• Too many parameters often indicate a missing data structure or abstraction.
• Mutable shared state creates ordering and concurrency risks.
• Deep recursion can cause stack overflow or exceed language limits.
• Overloading may become ambiguous or obscure the intended operation.
• Higher-order abstractions can increase flexibility but reduce immediate readability.
• A function that is technically reusable may still have poor cohesion or an unsuitable contract.
• Performance should be measured rather than guessed; memoization trades memory for speed, and callable wrappers may have runtime costs.

Chapter Summary

Functions and procedures provide the basic units of decomposition in Python and C++. Good functions have explicit contracts, focused responsibilities, controlled side effects, and interfaces appropriate to their callers. Parameters may be passed by value or reference, and Python's object-sharing model must be distinguished from mutation and rebinding. Scope determines name visibility, whereas lifetime determines object existence. C++ supports signature-based overloading; Python uses alternatives such as defaults and dispatch tools. Recursion requires a base case, progress toward that case, and awareness of stack and time costs. Memoization can reduce repeated recursive work. Higher-order functions pass or return callable behavior and support flexible pipelines, but abstraction must remain understandable, testable, and secure.

Key Terms

Function: A named reusable unit that may accept inputs and produce a result.

Procedure: A callable unit primarily intended to perform an action.

Parameter: A variable declared in a function definition.

Argument: A value supplied to a function call.

Contract: A specification of inputs, outputs, assumptions, and effects.

Precondition: A requirement that must hold before execution.

Postcondition: A guarantee after successful execution.

Side effect: An observable change beyond calculating a local result.

Scope: The region where a name can be accessed or resolved.

Lifetime: The period during which an object exists.

Closure: A function retaining access to enclosing-scope variables.

Reference: An alias or indirect access mechanism for an existing object.

Overloading: Multiple functions with the same name and distinct parameter lists.

Recursion: Solving a problem through calls to the same function on smaller instances.

Base case: A recursive case solved without another recursive call.

Memoization: Caching results to avoid repeated computation.

Higher-order function: A function that accepts or returns callable behavior.

Cohesion: The degree to which a unit's responsibilities belong together.

Coupling: The degree of dependency between software units.

Separation of concerns: Organizing software so distinct responsibilities remain distinct.

Review Questions

Short Answer Questions

1. Distinguish a parameter from an argument.

2. What are a precondition and a postcondition?

3. Explain the difference between rebinding and mutation in Python.

4. Why does a recursive function require a base case?

5. What is the purpose of a `const` reference in C++?

Long Answer Questions

1. Compare Python's argument-passing model with C++ value and reference parameters, using examples.

2. Explain how decomposition, cohesion, coupling, and separation of concerns affect maintainability.

3. Describe Python scope and object lifetime, including closures.

4. Compare traditional C++ overloading with Python's approaches to alternative behavior by type or signature.

5. Analyse naïve and memoized recursive Fibonacci in terms of time, space, and practical limitations.

Analytical / Application Questions

1. Design a function contract and implementation strategy for processing a non-empty list of transaction amounts, including validation and error handling.

2. Refactor a monolithic registration function into validation, normalization, persistence, and presentation responsibilities. Explain the cohesion and coupling improvements.

3. Choose between iteration, recursion, and memoized recursion for traversing a large directory tree. Justify the choice using structure, stack depth, repeated work, and testability.

Multiple Choice Questions with Answers

Question 1

What does a Python function return when it reaches the end without executing a return statement?

A. 0

B. None

C. False

D. An empty tuple

Correct Answer: B. None

Question 2

Which C++ parameter allows modification of the caller's object without copying it?

A. int value

B. const int& value

C. int& value

D. int* const value

Correct Answer: C. int& value

Question 3

Why is a mutable list generally unsafe as a Python default parameter?

A. Lists cannot be passed to functions

B. The same default list can be reused across calls

C. Python converts lists to tuples

D. Default parameters are evaluated after every call

Correct Answer: B. The same default list can be reused across calls

Question 4

What is the essential purpose of a recursive base case?

A. To increase stack usage

B. To force function overloading

C. To terminate recursive decomposition

D. To convert recursion into iteration automatically

Correct Answer: C. To terminate recursive decomposition

Question 5

What is the value of the Python expression factorial(4) as defined in the chapter?

A. 8

B. 16

C. 24

D. 32

Correct Answer: C. 24

Question 6

What is the principal effect of memoization on the recursive Fibonacci implementation?

A. It removes the base case

B. It stores previous results to avoid repeated computation

C. It guarantees constant memory use

D. It changes Fibonacci values

Correct Answer: B. It stores previous results to avoid repeated computation

Question 7

Which statement about C++ function overloading is correct?

A. Functions may be distinguished by return type alone

B. Overloads must always have different names

C. Overloads can have the same name with different parameter lists

D. Overloading occurs only at run time

Correct Answer: C. Overloads can have the same name with different parameter lists

Question 8

Which example is a higher-order operation?

A. Adding two integer literals

B. Passing a function to another function

C. Declaring a local integer

D. Assigning a string constant

Correct Answer: B. Passing a function to another function

Question 9

For prices [10, 20] and a tax rate of 0.15, what total does the chapter's total_price function return?

A. 30.15

B. 34.50

C. 35.00

D. 45.00

Correct Answer: B. 34.50

Question 10

Which design most directly demonstrates separation of concerns?

A. One function validates input, writes to a database, and formats output

B. Every function accesses global state

C. Validation, calculation, persistence, and presentation are separate components

D. A single function contains all application behavior

Correct Answer: C. Validation, calculation, persistence, and presentation are separate components