Understanding Tail Call Optimization in Objective‑C

This article analyzes the tail‑call mechanism of Objective‑C objects and details how the compiler optimizes objc_msgSend through tail‑call optimization (TCO). It originates from a submission by the 360 QiShare team.

What is a tail call? A tail call occurs when the last operation of a function is a single call to another function (or itself), with no additional computation.

Correct tail‑call example:

- (NSInteger)funcA:(NSInteger)num {
    // Some codes...
    if (num == 0) {
        return [self funcA:num]; // tail‑call → self
    }
    if (num > 0) {
        return [self funcB:num]; // tail‑call → funcB
    }
    return [self funcC:num]; // tail‑call → funcC
}

The final statement of funcA merely calls another function, satisfying the tail‑call definition.

Incorrect tail‑call examples:

// Not a tail call 1:
- (NSInteger)funcA:(NSInteger)num {
    NSInteger num = [self funcB:num];
    return num; // returns a value, not a call
}

// Not a tail call 2:
- (NSInteger)funcA:(NSInteger)num {
    return [self funcB:num] + 1; // additional +1 operation
}

Both examples violate the rule because the last operation either returns a computed value or performs extra work after the call.

Where does Objective‑C’s tail‑call optimization appear? The article provides a demo that uses breakpoints and memory inspection to show the presence or absence of TCO.

Scenario 1 – No optimization: Adding “.0” prevents tail‑call optimization, causing each call to push a new stack frame, leading to O(n) space and potential stack overflow.

Scenario 2 – With optimization: The compiler reuses the same stack frame, achieving O(1) space while maintaining O(n) time.

The essential principle of TCO is stack‑frame reuse: when a function’s last action is a sole call to another function, the current frame can be handed over to the callee, eliminating the need for a new frame.

Key conditions for TCO in Objective‑C:

The tail‑call function does not need to access variables from its own frame.

After the call, the caller has no further statements to execute.

The result of the call is directly returned.

In release builds, the compiler applies this optimization; it is omitted in debug builds.

Source code: https://github.com/QiShare/QiRecursiveDemo.git