Skip to content
Tutorials Center
My learning

Topics

Lesson 13 of 38 ยท Control Flow and Functions

Function Pointers and Recursion

Learn how function pointers work, how to build callbacks and dispatch tables, how recursion solves problems like factorials and trees, and how selectors relate to both.

Two ideas in this lesson shape how Objective-C works under the hood. A function pointer lets you store a function in a variable and call it later, which is the basis of callbacks and of the runtime's method tables. Recursion lets a function solve a problem by calling itself on a smaller piece, which is a natural fit for trees, nested data and divide-and-conquer algorithms.

Function pointers

Every function has an address. A function pointer variable stores one. The declaration mirrors the function's signature with the name in parentheses:

OBJECTIVEC
int add(int a, int b)      { return a + b; }
int multiply(int a, int b) { return a * b; }

int (*operation)(int, int);     // pointer to a function taking two ints returning int
operation = add;
NSLog(@"%d", operation(3, 4));  // 7
operation = multiply;
NSLog(@"%d", operation(3, 4));  // 12

Read int (*operation)(int, int) as: operation is a pointer to a function of (int, int) returning int. Without the parentheses around *operation it would declare a function returning int *.

A typedef makes this readable:

OBJECTIVEC
typedef int (*BinaryOp)(int, int);

BinaryOp table[] = { add, multiply };
for (int i = 0; i < 2; i++) { NSLog(@"%d", table[i](6, 7)); }

Callbacks

A function that accepts a function pointer lets the caller customize its behaviour. The C library's qsort is the classic example: it knows how to sort but asks you how to compare two elements.

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

int values[] = {42, 7, 19, 3};
qsort(values, 4, sizeof(int), compareAscending);

C callbacks usually carry a void *context parameter, so that the callback can reach the data it needs. Cocoa APIs that predate blocks used this pattern (for example sortedArrayUsingFunction:context:). Modern code uses blocks, which capture their surroundings automatically.

Function pointers and selectors

A selector (SEL) is the runtime's identifier for a method name; @selector(sayHello) creates one. The runtime maps a selector to an IMP, which is a function pointer: in effect id (*)(id self, SEL _cmd, ...). Sending a message means finding the right function pointer and calling it with the receiver and selector as hidden first arguments. The first lesson's table-lookup stand-in models this. You can also use selectors directly:

OBJECTIVEC
SEL action = @selector(uppercaseString);
if ([@"abc" respondsToSelector:action]) {
    NSString *result = [@"abc" performSelector:action];   // @"ABC"
}

Recursion

A recursive function has a base case, which stops the recursion, and a recursive case that calls the function on a smaller problem:

OBJECTIVEC
NSUInteger factorial(NSUInteger n) {
    if (n <= 1) { return 1; }        // base case
    return n * factorial(n - 1);     // recursive case
}

factorial(4) waits for factorial(3), which waits for factorial(2), and so on. The calls pile up on the call stack and unwind once the base case returns. Every call uses stack memory, so a missing base case or a huge depth causes a stack overflow crash.

flowchart TB
  A["factorial(4)"] --> B["4 * factorial(3)"]
  B --> C["3 * factorial(2)"]
  C --> D["2 * factorial(1)"]
  D --> E["factorial(1) returns 1"]

The calls descend to the base case, then the products are computed on the way back.

When to use recursion

Recursion shines when the data is itself nested: directory trees, JSON, view hierarchies, expression trees.

OBJECTIVEC
void printTree(NSDictionary *node, int depth) {
    NSLog(@"%*s%@", depth * 2, "", node[@"name"]);
    for (NSDictionary *child in node[@"children"]) {
        printTree(child, depth + 1);
    }
}

For plain counting, a loop is usually clearer and cheaper. Compare an iterative factorial: it needs no stack growth. Be wary of recursion that repeats work (a naive Fibonacci recomputes the same values exponentially often); cache results or use a loop.

Stand-in: a function pointer table and callbacks

C Stand-in (C): dispatch table and qsort callback

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.

Stand-in: recursion, depth and memoization

C Stand-in (C): factorial, tree printing and cached Fibonacci

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.

Common mistakes

  • Omitting the parentheses: int *op(int, int) declares a function, not a pointer.
  • Forgetting the base case, which ends in a stack overflow.
  • Calling a null function pointer.
  • Using performSelector: with a selector that returns a struct or primitive, which is unsafe under ARC.
  • Using exponential recursion where a loop or cache would do.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does int (*op)(int, int); declare?

    The parentheses around *op make op a pointer to a function.
  2. 2. What is an IMP in the Objective-C runtime?

    IMP is a function pointer. The runtime maps selectors to IMPs.
  3. 3. What must every recursive function have?

    Without a base case the calls never stop and the stack overflows.
  4. 4. Why is naive recursive Fibonacci slow?

    The same values are recomputed exponentially often. Caching or a loop fixes that.

Summary

  • A function pointer stores the address of a function; typedef makes the syntax readable.
  • Callbacks let a library call your code; blocks are the modern, capturing form.
  • Selectors map to IMP function pointers in the runtime, which is how messaging works.
  • Recursion needs a base case and suits nested data; deep recursion uses stack space.
  • Use memoization or loops for repeated sub-problems.

Next: Variadic Functions and Storage Classes