Recursion over strings

Overview

Strings recurse in two distinct shapes. Head-and-tail treats the string as its first character plus the rest and advances the pointer — f(s+1) — with the NUL terminator as the base case; that suits counting and scanning. Two-pointer recursion moves an index inward from each end — f(s, i+1, j-1) — with the base case being the indices meeting or crossing; that suits palindrome checks and any symmetric comparison. Picking the shape that matches the question is most of the work.

Why it matters

C strings are NUL-terminated with no length attached, so every traversal is a decision about where to stop — and getting that wrong is the origin of a large share of real-world C vulnerabilities. Practising both recursive shapes builds the habit of stating the termination condition explicitly instead of assuming it.

Core concepts

Head-and-tail. count(s, c) = (*s == c) + count(s+1, c) with base case *s == '\0'. Each call looks at exactly one character and hands the remainder onward. Note that (*s == c) is already 0 or 1, so it adds directly.

Two-pointer inward. pal(s, i, j) returns 1 when i >= j (empty or single middle character), 0 on a mismatch, else recurses with i+1, j-1. Both even and odd lengths are covered by >= — using == misses the even case where the indices cross without meeting.

The base case is the terminator. For head-and-tail it is the NUL; for two-pointer it is the index relationship. Neither is a length check, because a C string does not carry its length.

Depth equals length. Both shapes recurse once per character (or per pair), so a very long string means a very deep stack.

char signedness. Comparing or classifying characters requires care: char may be signed, so passing it directly to isalpha and friends is undefined for negative values. Cast to unsigned char first.

Syntax notes

/* two-pointer: palindrome over s[i..j] */
int pal(const char *s, int i, int j) {
    if (i >= j) return 1;              /* met or crossed - covers odd AND even lengths */
    if (s[i] != s[j]) return 0;
    return pal(s, i + 1, j - 1);
}

/* head-and-tail: count occurrences of c */
int cnt(const char *s, char c) {
    if (!*s) return 0;                 /* base case: the NUL terminator */
    return (*s == c) + cnt(s + 1, c);  /* the comparison is already 0 or 1 */
}

Key points:

• i >= j, not i == j — for an even-length string the indices cross without ever being equal.
• !*s is the idiomatic NUL test; s[0] == '\0' is the same thing spelled out.
• The caller supplies j = strlen(s) - 1, which is -1 for an empty string — so guard the empty case before calling.

Lesson

Strings recurse two ways: advance a pointer (head + tail) or move two indices inward (for palindromes). The NUL terminator or the crossing of indices is the base case.

Code examples

#include <stdio.h>
#include <string.h>
static int pal(const char*s,int i,int j){ if(i>=j) return 1; if(s[i]!=s[j]) return 0; return pal(s,i+1,j-1); }
static int cnt(const char*s,char c){ if(!*s) return 0; return (*s==c)+cnt(s+1,c); }
int main(void){
    printf("is \"level\" a palindrome? %s\n", pal("level",0,4)?"yes":"no");
    printf("'s' appears %d times in \"mississippi\"\n", cnt("mississippi",'s'));
    return 0;
}

Line by line

Common mistakes

Reading past the terminator; not advancing toward the base case.

Debugging tips

Compiler errors and warnings:

• -Wchar-subscripts when a char is used as an array index or passed to <ctype.h> functions; cast to unsigned char.
• warning: comparison between pointer and integer if you write s != '\0' instead of *s != '\0'.

Runtime symptoms:

• Palindrome check wrong for even-length strings. You used i == j as the base case; the indices cross without meeting. Use i >= j.
• Crash on an empty string. The caller passed j = strlen(s) - 1 = -1, so s[-1] is read. Guard the empty string before calling.
• Infinite recursion / crash in the counting version. You recursed on s instead of s + 1, so the pointer never advances.
• Wrong results with non-ASCII bytes. char signedness — cast to unsigned char before classification.

Technique: test "", "a", "aa", "ab", "abba", "abcba". Those six cover empty, odd, even, and both palindrome outcomes.

Memory safety

• The NUL terminator is the only bound. If a buffer is not NUL-terminated, head-and-tail recursion walks off the end of the allocation — a classic C overread. Ensure termination before traversing, or carry an explicit length.
• j = strlen(s) - 1 underflows for an empty string. With a signed int that is -1 and s[-1] is out of bounds; with size_t it wraps to a huge index. Guard the empty case explicitly.
• Depth equals length. A megabyte-long string means a megabyte of frames — stack exhaustion. Iterate for long inputs.
• char may be signed. Passing a negative char to isalpha/tolower is undefined; always cast to unsigned char.
• const char * in the signature prevents accidental modification of the caller's string.

Real-world uses

Concrete uses: Palindrome and symmetry checks appear in bioinformatics (reverse-complement sites) and in validation code. Head-and-tail traversal mirrors how tokenizers and simple parsers consume input. Recursive descent over strings is the basis of expression parsers. Two-pointer techniques generalise to array problems such as pair-sum and partitioning.

Professional best practices:

Beginner:

• Write the termination condition first and test the empty string.
• Use i >= j, not i == j, for inward recursion.

Intermediate:

• Prefer iteration for long strings; the recursive form is for clarity and for branching grammars.
• Carry an explicit length alongside the pointer when the data may not be NUL-terminated.
• Cast to unsigned char before any <ctype.h> call — a small habit that prevents undefined behaviour on non-ASCII input.

Practice tasks

1. (Beginner) Recursive palindrome. Implement int pal(const char *s, int i, int j) and a wrapper that handles the empty string. Example: "abba" -> 1; "abc" -> 0; "" -> 1. Concepts: two-pointer base case.

2. (Beginner) Count a character. Implement int cnt(const char *s, char c) head-and-tail. Example: cnt("banana",'a') -> 3. Concepts: NUL termination, pointer advance.

3. (Intermediate) Recursive strlen and reverse-print. Implement both without loops. Hint: print after the recursive call to reverse the order. Concepts: work on the way down vs on the way back up.

4. (Intermediate) Case-insensitive palindrome. Ignore case and skip non-alphanumeric characters. Requirements: cast to unsigned char before <ctype.h> calls. Example: "A man, a plan, a canal: Panama" -> 1. Concepts: character classification safety.

Summary

Strings offer two recursive shapes: head-and-tail advances a pointer with the NUL terminator as the base case, and two-pointer moves indices inward with i >= j as the base case — >= rather than == because even-length strings cross without meeting. Since a C string carries no length, the terminator is your only bound, so an unterminated buffer means an overread and strlen(s) - 1 on an empty string means an out-of-bounds index. Guard the empty case, cast to unsigned char before any <ctype.h> call, and prefer iteration when strings may be long, since depth tracks length.

Practice with these exercises

• Recursive palindrome check
• Recursive character count