Recursion and a first linked list
Records, files and recursion13 min readLesson 6 of 6
6.1 A function that calls itself
A recursive function solves a problem by calling itself on a smaller version of the input. Two parts are required: a base case that returns without recursing, and a step that makes progress toward it.
Every call gets its own parameters and local variables on the stack. The call that started last finishes first, so results come back in reverse order of the calls.
Without a base case, or with a step that does not shrink, the calls continue until the stack runs out. The program usually stops with a stack overflow, and the message rarely names the missing base case.
#include <stdio.h>
static void countdown(int n)
{
if (n <= 0) {
printf("liftoff\n");
return;
}
printf("%d\n", n);
countdown(n - 1);
}
int main(void)
{
countdown(3);
return 0;
}Output
3 2 1 liftoff
6.2 Work before and after the call
The position of the recursive call changes the order of the output. Printing before the call produces descending values; printing after the call produces ascending values as the stack unwinds.
A value can also be built on the way back. return n + sum_to(n - 1); adds each level's n after the deeper call returns.
That ordering is the main idea to grasp. Once it makes sense, recursive code over a tree or a list is easier to read than the equivalent loop.
#include <stdio.h>
static void print_after(int n)
{
if (n <= 0) return;
print_after(n - 1);
printf("%d\n", n);
}
static int sum_to(int n)
{
if (n <= 0) return 0;
return n + sum_to(n - 1);
}
int main(void)
{
printf("%d\n", sum_to(10));
print_after(4);
return 0;
}Output
55 1 2 3 4
6.3 Recursion on text
A string can be processed one character at a time by passing text + 1 to the recursive call. The base case is the terminator, and each call handles the first character.
Printing before the call gives the string in order. Printing after the call gives it in reverse, because printing happens as the calls return.
A pointer parameter makes the shrinking obvious. text + 1 is the rest of the string, and *text is the current character.
#include <stdio.h>
static void print_reverse(const char *text)
{
if (*text == '\0') return;
print_reverse(text + 1);
putchar(*text);
}
int main(void)
{
print_reverse("stack");
putchar('\n');
return 0;
}Output
kcats
6.4 A struct that points to itself
A linked list node contains a value and a pointer to another node of the same type. The definition is legal because a pointer has a known size even when the type is incomplete.
struct Node { int value; struct Node *next; }; is enough. A struct cannot contain an instance of itself, because the size would be infinite, but a pointer to itself is fine.
The last node points at NULL, and that null pointer is the base case for every recursive function that walks the list.
#include <stdio.h>
#include <stdlib.h>
struct Node { int value; struct Node *next; };
static struct Node *push_front(struct Node *head, int value)
{
struct Node *node = malloc(sizeof *node);
if (node == NULL) return head;
node->value = value;
node->next = head;
return node;
}
int main(void)
{
struct Node *head = NULL;
head = push_front(head, 10);
head = push_front(head, 20);
head = push_front(head, 30);
for (struct Node *it = head; it != NULL; it = it->next) printf("%d\n", it->value);
return 0;
}Output
30 20 10
6.5 Recursive traversal and release
A list walk has two natural forms. A loop moves a pointer along next; recursion calls itself with head->next and treats NULL as the base case.
Freeing a list with a loop needs a second pointer saved before free, because the node becomes unreadable afterwards. The recursive version frees the rest of the list first, then frees the current node.
Both versions are correct, though the recursive one uses stack space in proportion to the list length, which matters for very long lists.
#include <stdio.h>
#include <stdlib.h>
struct Node { int value; struct Node *next; };
static void free_list(struct Node *node)
{
if (node == NULL) return;
free_list(node->next);
free(node);
}
int main(void)
{
struct Node *a = malloc(sizeof *a), *b = malloc(sizeof *b);
if (a == NULL || b == NULL) { free(a); free(b); return 1; }
a->value = 1; a->next = b;
b->value = 2; b->next = NULL;
free_list(a);
printf("released\n");
return 0;
}Output
released
6.6 Recursion or a loop
Recursion suits structures that branch or that are defined in terms of themselves, such as trees and linked nodes. A linked list qualifies, and a loop is equally clear.
A loop avoids stack growth and is usually faster for a linear walk. Recursion can be shorter and easier to check against a recursive definition.
C does not guarantee tail call optimisation. A function that calls itself as its last action still uses a frame in most builds, so a list of a million nodes overflows the stack with the recursive version.
#include <stdio.h>
static int depth(int n)
{
if (n == 0) return 0;
return 1 + depth(n - 1);
}
int main(void)
{
printf("%d\n", depth(5000));
return 0;
}Output
5000
6.7 Choosing the base case carefully
The base case must be reachable and must be checked first. A function that tests the recursive condition before the base case recurses forever.
Each step has to make measurable progress. For a countdown that means n - 1; for a list it means node->next; for a string it means text + 1.
Recursion on an array usually passes an index or a pointer plus a remaining count. Both shrink together, and the compiler cannot check that they do.
#include <stdio.h>
static int find(const int *values, int low, int high, int target)
{
if (low > high) return -1;
int mid = low + (high - low) / 2;
if (values[mid] == target) return mid;
if (values[mid] < target) return find(values, mid + 1, high, target);
return find(values, low, mid - 1, target);
}
int main(void)
{
int values[7] = {2, 4, 6, 8, 10, 12, 14};
printf("%d\n", find(values, 0, 6, 10));
printf("%d\n", find(values, 0, 6, 5));
return 0;
}Output
4 -1