Functions, Scope, Storage Duration, and Recursion

Introduction

Functions are the principal unit of modularity in C. They allow a large program to be decomposed into named operations with defined inputs, outputs, and side effects. Scope determines where an identifier may be referenced; linkage determines whether declarations in different scopes denote the same entity; and storage duration determines how long an object exists. Recursion extends functional decomposition by allowing a function to invoke itself, directly or indirectly.

These concepts are closely related. A local automatic object normally exists only while execution remains within a block, a static object persists for the entire execution of the program, and a dynamically allocated object persists until explicitly released. Correct reasoning about these properties is essential in embedded systems, operating systems, compilers, signal-processing software, and safety-critical applications.

Learning Objectives

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

• distinguish declarations, definitions, parameters, arguments, and return values;
• design functions with appropriate interfaces and contracts;
• explain block, file, function, and prototype scope;
• distinguish scope from linkage and storage duration;
• select among automatic, static, allocated, and thread storage duration;
• reason about function call stacks and recursive activation records;
• implement and analyse recursive algorithms;
• identify common defects involving lifetime, aliasing, reentrancy, and undefined behaviour;
• apply these ideas to a realistic embedded-systems problem.

1. Functions as Abstraction Units

A function is a named sequence of statements that may accept arguments, perform computation, modify objects, and return a value. In a C program, execution begins in main, after which control may pass through a sequence of function calls.

A function declaration, commonly called a prototype, specifies an interface:

int max_sample(const int samples[], size_t count);

This declaration states that the function returns int, has the name max_sample, and accepts a pointer to constant int together with a size_t count. It does not define the algorithm. A definition supplies the body:

int max_sample(const int samples[], size_t count)
{
    if (count == 0) {
        return 0;              /* Interface policy for empty input */
    }

    int maximum = samples[0];
    for (size_t i = 1; i < count; ++i) {
        if (samples[i] > maximum) {
            maximum = samples[i];
        }
    }
    return maximum;
}

The parameter declaration const int samples[] is adjusted by the language to a pointer parameter in a function parameter list. Consequently, the function does not know the array length from the pointer; count must be supplied separately.

1.1 Interface, contract, and side effects

A high-quality function has a contract consisting of:

• preconditions: requirements before invocation, such as a non-null pointer or nonzero length;
• postconditions: properties guaranteed after successful completion;
• frame or side-effect conditions: objects that may be modified, files that may be accessed, or signals that may be generated.

For example, a function that computes an average could require count > 0, promise a result within a specified numerical range, and promise not to modify the input array. Explicit contracts improve testing and facilitate formal verification.

C passes arguments by value. A scalar argument is copied:

void increment(int x) { ++x; }

Calling increment(value) does not change value. To modify the caller's object, the function receives its address:

void increment(int *x)
{
    if (x != NULL) {
        ++*x;
    }
}

The pointer itself is passed by value, but it points to the caller's object. This distinction is fundamental: C has no pass-by-reference parameter mechanism in the C++ sense.

A function may return an object value, a pointer, or no value (void). It must never return a pointer to an automatic object that has ceased to exist. Returning a pointer to a static object is possible, but introduces shared state and may reduce reentrancy.

1.2 Function types and pointers

Functions have types. A pointer to a function can be stored and passed as data:

int compare_ints(const void *a, const void *b)
{
    const int x = *(const int *)a;
    const int y = *(const int *)b;
    return (x > y) - (x < y);
}

Such pointers support callback interfaces, interrupt dispatch tables, finite-state machines, and configurable algorithms. The pointed-to function must be called through a compatible function type. Converting an incompatible function pointer and calling through it produces undefined behaviour.

A declaration using static at file scope can restrict a function's linkage:

static void update_checksum(...);

This makes the function private to its translation unit, an important encapsulation practice in multi-file projects.

1.3 Evaluation order and side effects

Function arguments are evaluated before the call, but the order among separate arguments is generally unspecified. Therefore, code such as:

f(i++, i++);       /* Do not rely on an order */

is unsuitable for portable programming because the same scalar object is modified more than once without an intervening sequence point. More generally, side effects should be separated into distinct statements when their ordering matters.

2. Scope, Linkage, and Visibility

These terms are related but not interchangeable.

• Scope is the region of source code in which an identifier is visible.
• Linkage determines whether declarations in different scopes or translation units refer to the same entity.
• Storage duration describes how long the object exists during execution.
• Visibility is often used informally for whether a declaration can be seen by a particular source file; it should not be confused with scope.

2.1 Scope categories

C defines four important scopes.

A function parameter has block scope beginning at its declaration and extending through the function body. A label has function scope even though it is declared within a block.

Nested blocks may hide outer declarations:

int status = 1;
{
    int status = 2;
    printf("%d\n", status);       /* 2 */
}
printf("%d\n", status);           /* 1 */

The inner identifier does not change the outer object; it merely hides it within the nested scope. Excessive shadowing is discouraged because it increases maintenance and review risk.

2.2 External, internal, and no linkage

An identifier with no linkage denotes a distinct entity in its scope. Ordinary block-scope variables generally have no linkage. An identifier with internal linkage denotes an entity accessible throughout one translation unit, typically produced by static at file scope. An identifier with external linkage may denote the same entity across translation units, commonly through declarations using extern.

A robust multi-file design places public declarations in a header and private definitions in a source file:

/* filter.h */
#ifndef FILTER_H
#define FILTER_H
int filter_step(int sample);
#endif

/* filter.c */
#include "filter.h"
static int previous_sample;

int filter_step(int sample)
{
    int output = (sample + previous_sample) / 2;
    previous_sample = sample;
    return output;
}

Here previous_sample has internal linkage and cannot be directly accessed by other translation units. The public function forms the controlled interface.

2.3 extern, tentative definitions, and headers

The declaration

extern int error_count;

states that the object is defined elsewhere. Exactly one appropriate definition must be supplied in the program, for example:

int error_count = 0;

A header should normally contain declarations, type definitions, macros, and static inline functions where appropriate—not a non-static object definition that will be included in multiple source files. Include guards or equivalent mechanisms prevent repeated inclusion in one translation unit.

3. Storage Duration and Object Lifetime

C objects have one of four storage-duration categories.

Storage duration is not identical to storage location. An automatic object is commonly placed on a stack, but the C standard does not require a stack implementation. A compiler may keep an object in a register or optimize it away while preserving observable behaviour.

3.1 Automatic duration

Automatic objects are created when execution enters their block and cease to exist when execution leaves it. Their values are indeterminate if not initialized. Reading an indeterminate value can be erroneous, particularly for objects of automatic storage duration that were never initialized.

int compute(void)
{
    int result = 0;     /* initialized before use */
    return result;
}

A pointer to an automatic object becomes invalid after the object's lifetime ends. This is a dangling pointer, even if the numerical address appears unchanged.

3.2 Static duration

File-scope objects and objects declared with static inside a block have static storage duration. They are initialized before program startup. If no explicit initializer is supplied, they are initialized to zero (or the appropriate null representation for pointers).

unsigned long calls(void)
{
    static unsigned long count;
    return ++count;
}

count retains its value between calls, but its linkage is none because it is declared at block scope. Static local state is useful for counters and persistent filters, but it makes the function stateful and potentially non-reentrant.

The keyword static has two distinct effects depending on location: at file scope it commonly specifies internal linkage; at block scope it specifies static storage duration. Context must therefore be considered.

3.3 Allocated duration

Dynamic allocation supports objects whose required lifetime or size is not known at compile time:

int *buffer = malloc(n * sizeof *buffer);
if (buffer == NULL) {
    /* allocation failure */
}
/* use buffer */
free(buffer);
buffer = NULL;

The multiplication n sizeof buffer must be checked for integer overflow when n can be externally controlled. Every successful allocation should have a clear owner responsible for exactly one eventual release. Common defects include leaks, double frees, use-after-free, and freeing a non-allocated pointer.

realloc requires care: assigning its result directly to the only pointer can lose the original allocation if the operation fails. A temporary pointer is safer:

int *tmp = realloc(buffer, new_count * sizeof *buffer);
if (tmp != NULL) {
    buffer = tmp;
}

3.4 Thread storage duration and concurrency

A _Thread_local object provides one instance per thread. It can simplify thread-specific error state, but it does not automatically make an algorithm safe: objects shared by threads still require appropriate synchronization. In embedded or real-time systems, static and dynamic allocation policies should also account for deterministic timing and fragmentation.

4. Recursion and Activation Records

Recursion occurs when a function directly or indirectly calls itself. A recursive algorithm requires:

1. a base case that terminates recursion;
2. a recursive case that moves toward the base case;
3. sufficient resources for all active calls.

A mathematical model helps express correctness. For factorial, with nonnegative integer n,

The C implementation is:

unsigned long long factorial(unsigned int n)
{
    if (n == 0U) {
        return 1ULL;
    }
    return (unsigned long long)n * factorial(n - 1U);
}

The mathematical recurrence does not guarantee that the C result fits its return type. For a 64-bit unsigned long long, factorial values eventually overflow the type; the implementation should impose a documented range or detect overflow when correctness requires it.

Each call has an activation record containing parameters, automatic objects, and a return location. For factorial(4), calls remain active as factorial(4), factorial(3), factorial(2), factorial(1), and factorial(0) is reached. The calls then return in reverse order. If the maximum recursion depth is d, stack usage is commonly O(d), although the exact memory representation is implementation-dependent.

4.1 Recursive complexity

For a recurrence such as

where c is constant and the base case takes constant time, the running time is O(n). Factorial therefore has linear call count. A naïve recursive Fibonacci implementation has

and makes repeated calls, giving exponential time in its direct form. Memoization changes the time complexity to O(n) and uses O(n) additional storage; an iterative version achieves O(n) time and O(1) additional storage.

4.2 Divide and conquer

Recursion is especially natural for trees and divide-and-conquer algorithms. Merge sort divides an input of size n into two subproblems, recursively sorts them, and merges them. Its recurrence is approximately:

under the assumptions of balanced division and linear-time merging. This yields O(n log n) time. The auxiliary storage depends on the implementation; a conventional merge sort commonly needs O(n) temporary storage.

4.3 Tail recursion and C implementation

A recursive call is tail-recursive when it is the final operation of the function. Some compilers optimize tail calls, but C does not require tail-call elimination. Therefore, tail recursion must not be assumed to provide constant stack use in portable code. An explicit loop is often preferable in resource-constrained systems.

Recursion can also be unsafe in interrupt handlers, signal handlers, or concurrent code when it uses non-reentrant library functions or shared static state. The decision to use recursion should consider maximum depth, stack limits, timing determinism, and failure handling—not merely elegance.

5. Worked Example: A Reentrant Recursive Tree Search

Consider a binary search tree node:

struct node {
    int key;
    struct node *left;
    struct node *right;
};

A recursive search is:

const struct node *find_node(const struct node *root, int key)
{
    if (root == NULL || root->key == key) {
        return root;
    }
    if (key < root->key) {
        return find_node(root->left, key);
    }
    return find_node(root->right, key);
}

The const qualification communicates that the search does not modify nodes. If the tree has height h, the search takes O(h) time and uses O(h) call-stack space. In a balanced tree, h ≈ log₂ n, where n is the number of nodes; in a degenerate chain, h = n. Thus, the same source algorithm has different practical behaviour depending on data shape.

An iterative version avoids recursion depth:

const struct node *find_node_iter(const struct node *root, int key)
{
    while (root != NULL && root->key != key) {
        root = (key < root->key) ? root->left : root->right;
    }
    return root;
}

The iterative implementation uses O(1) additional call-stack space, while preserving O(h) time.

6. Applied Case: Embedded Sensor Filtering

Background

An illustrative sensor node samples temperature periodically and computes a two-sample moving average. The firmware must be deterministic, testable, and safe when invoked by different application tasks.

Problem

A first implementation stores the previous sample in a file-scope global variable. A diagnostic task and the sampling task can call the filtering function concurrently, producing inconsistent results. A second implementation allocates a new buffer for every sample, causing unpredictable allocation time and possible memory exhaustion.

Analysis

The filter has state, but the state need not be globally shared. Dynamic allocation is unnecessary because the window size is fixed. A context structure can make state explicit:

struct average2 {
    int previous;
    int initialized;
};

int average2_update(struct average2 *ctx, int sample)
{
    if (ctx == NULL) {
        return 0;                  /* documented error policy */
    }
    if (!ctx->initialized) {
        ctx->previous = sample;
        ctx->initialized = 1;
        return sample;
    }
    int result = (ctx->previous + sample) / 2;
    ctx->previous = sample;
    return result;
}

Approach and outcome

Each task receives a separate context, or access is protected by an appropriate synchronization mechanism. The function has no hidden static state and is therefore easier to test and reason about. It uses automatic intermediate storage and caller-owned persistent state. No allocation occurs during sampling, improving timing predictability.

The integer average shown assumes that truncation toward zero is acceptable and that addition cannot overflow int. For sensor ranges that may approach the integer limits, a wider intermediate type or a checked averaging method is required. This illustrates why an apparently simple arithmetic expression must be evaluated against data-range assumptions.

Learning points

• state ownership should be explicit;
• static state is not automatically thread-safe;
• fixed-size embedded operations often benefit from static allocation or caller-owned buffers;
• function contracts must document invalid inputs and numerical limits;
• reentrancy, timing, and memory policy are design requirements, not afterthoughts.

7. Common Defects and Best Practices

7.1 Defect patterns

• Calling a function without a visible compatible prototype can cause incorrect argument assumptions in older or nonconforming code.
• Returning the address of an automatic local object creates a dangling pointer.
• Using an object after free creates undefined behaviour.
• Using a static local for convenience can introduce hidden coupling and race conditions.
• Declaring a global definition in a widely included header can cause multiple-definition problems.
• Recursion without a progressing argument may never terminate.
• Large automatic arrays and deep recursion can exhaust available stack resources.
• Comparing or manipulating function pointers as though they were ordinary object pointers is nonportable.

7.2 Engineering practices

Use prototypes and compile with strong diagnostics, for example warnings for missing declarations, conversions, shadowing, and unreachable code. Keep interfaces small and use const to express non-modification. Prefer file-private (static) functions and objects unless external access is required. Define ownership for allocated memory. Document maximum recursion depth and use iterative alternatives where stack limits are strict. Test boundary cases: empty input, null pointers where permitted, maximum sizes, allocation failure, and integer overflow.

Static analysis, sanitizers, unit tests, fuzzing, and code review are valuable. In safety-related development, traceability from requirements to function contracts and tests is often required by organizational or industry standards. Tools assist reasoning but do not replace knowledge of the C abstract machine.

8. Contemporary and Professional Considerations

Modern compilers perform aggressive optimization based on the C standard's rules concerning aliasing, lifetime, and undefined behaviour. Code that appears to work at one optimization level may fail when optimized if it violates those rules. C23 introduces and clarifies several language facilities, but portability across compilers and embedded toolchains remains a practical constraint.

In concurrent and embedded applications, the central question is not simply whether a function returns the correct value in isolation. Engineers must also ask whether it is reentrant, interrupt-safe, deterministic, memory-safe, and compatible with the platform's calling convention. A function's scope and linkage should support modular architecture; its storage duration should support ownership and timing requirements; and its recursion strategy should fit resource limits.

Chapter Summary

Functions provide modular interfaces through parameters, return values, and controlled side effects. C passes arguments by value, although pointers allow a function to modify caller-owned objects. Prototypes enable type checking, while function pointers support callbacks and dispatch mechanisms.

Scope specifies where an identifier is visible; linkage specifies whether declarations denote the same entity; and storage duration specifies how long an object exists. Block-scope automatic objects are temporary, static objects persist for the program's execution, allocated objects require explicit ownership and release, and thread-local objects are private to individual threads. The keyword static has different consequences at file and block scope.

Recursion relies on a base case and progress toward that case. Each call consumes an activation record, so recursion depth affects stack use. Recursive algorithms are natural for trees and divide-and-conquer problems, but iterative or memoized alternatives may provide better resource behaviour. Professional C programming requires attention to lifetime, reentrancy, concurrency, integer limits, allocation failure, and undefined behaviour.

Key Terms

Function: Named unit of executable code with a defined interface.

Prototype: Declaration that specifies a function's return type and parameters.

Definition: Declaration that supplies an entity's implementation or storage.

Parameter: Named input object in a function definition.

Argument: Expression supplied at a function call.

Scope: Region of source code in which an identifier is visible.

Linkage: Rule determining whether declarations denote the same entity.

Translation unit: Source file after preprocessing, including included content.

Automatic storage duration: Lifetime associated with execution of a block.

Static storage duration: Lifetime extending from program initialization to termination.

Allocated storage duration: Lifetime controlled by allocation and deallocation operations.

Thread storage duration: Lifetime of one object for the execution of a thread.

Reentrancy: Ability to invoke a function again safely before an earlier invocation finishes.

Activation record: Runtime data associated with one active function call.

Recursion: Function invocation directly or indirectly by itself.

Base case: Terminating condition of a recursive definition.

Dangling pointer: Pointer whose referenced object no longer exists.

Internal linkage: Linkage restricting an entity to one translation unit.

Undefined behaviour: Execution for which the C standard imposes no requirements.

Review Questions

Short Answer Questions

1. Distinguish a function declaration from a function definition.
2. Why does a function receiving an array parameter also need a length parameter?
3. Explain the difference between scope and storage duration.
4. What two effects can the keyword static have in C?
5. State the three essential properties of a sound recursive algorithm.

Long Answer Questions

1. Explain C's four scope categories and illustrate each with an appropriate declaration.
2. Compare automatic, static, allocated, and thread storage duration, including typical risks and uses.
3. Discuss linkage in multi-file programs and design a suitable header/source-file organization.
4. Explain how activation records affect recursive algorithms and compare recursive and iterative implementations.
5. Analyse the advantages and disadvantages of static local state in embedded software.

Analytical / Application Questions

1. A function returns a pointer to a local array. Identify the defect, explain why it occurs, and propose two safe redesigns.
2. A recursive tree search takes linear time on some inputs and logarithmic time on others. Relate this behaviour to tree height and propose a strategy for predictable performance.
3. Design a sensor-processing function that is reentrant, avoids dynamic allocation during sampling, and documents its numerical assumptions and error policy.

Multiple Choice Questions with Answers

Question 1

Which statement correctly describes C argument passing?

A. All arguments are passed by reference.

B. Arguments are passed by value; a pointer value can refer to a caller-owned object.

C. Only arrays are passed by value.

D. Arguments are passed through global variables.

Correct Answer: B. Arguments are passed by value; a pointer value can refer to a caller-owned object.

Question 2

A file-scope function declared with static normally has which property?

A. Automatic storage duration

B. External linkage across all translation units

C. Internal linkage limited to its translation unit

D. Thread storage duration

Correct Answer: C. Internal linkage limited to its translation unit

Question 3

When does an ordinary block-scope local variable without static normally cease to exist?

A. When compilation ends

B. When the enclosing block is exited

C. When the program terminates only

D. When another function is declared

Correct Answer: B. When the enclosing block is exited

Question 4

Which is necessary for a terminating recursive function?

A. A global variable

B. A dynamic allocation

C. A base case and progress toward it

D. A function pointer

Correct Answer: C. A base case and progress toward it

Question 5

What is the principal danger of returning the address of an automatic local variable?

A. The pointer necessarily becomes a null pointer

B. The object no longer exists after the function returns

C. The object becomes static automatically

D. The compiler converts it to a function pointer

Correct Answer: B. The object no longer exists after the function returns

Question 6

For a balanced binary search tree with n nodes, its height is typically approximately:

A. n²

B. n

C. √n

D. log₂ n

Correct Answer: D. log₂ n

Question 7

Which declaration gives an object static storage duration but no linkage because it is block-scoped?

A. static int count; inside a function

B. extern int count; inside a function

C. auto int count; at file scope

D. register int count; at file scope

Correct Answer: A. static int count; inside a function

Question 8

What is a major risk of a naïve recursive Fibonacci implementation?

A. It cannot have a base case

B. It performs repeated subcomputations and has exponential time growth

C. It always uses dynamic allocation

D. It has constant time for every input

Correct Answer: B. It performs repeated subcomputations and has exponential time growth

Question 9

Which practice best protects the original allocation when realloc fails?

A. Free the original pointer before calling realloc

B. Assign realloc directly to the only pointer

C. Store the result in a temporary pointer and replace the original only on success

D. Call realloc with a null size unconditionally

Correct Answer: C. Store the result in a temporary pointer and replace the original only on success

Question 10

Why can hidden static state make a function unsuitable for concurrent use?

A. Static objects cannot be initialized

B. Multiple invocations may access shared state without synchronization

C. Static objects always have automatic duration

D. Static state prevents compilation

Correct Answer: B. Multiple invocations may access shared state without synchronization