K&R C Programs Exercise 4-13 - C Program Examples

Exercise 4-13. Write a recursive version of the function reverse(s), which reverses the string s in place.

An iterative reverse uses two indices walking inward from both ends, swapping until they meet. The recursive version does the same with the call stack: each call receives left and right indices, swaps those two characters, then recurses on the inner substring. Base case: left ≥ right (zero or one character remaining — nothing to swap).

Solution

/* K&R Exercise 4-13 — recursive reverse(s) in place
 * Compile: gcc -ansi -Wall ex4-13.c -o ex4-13 */
#include <stdio.h>
#include <string.h>

static void rev(char s[], int left, int right)
{
    char tmp;
    if (left >= right)
        return;
    tmp = s[left];
    s[left] = s[right];
    s[right] = tmp;
    rev(s, left + 1, right - 1);
}

void reverse(char s[])
{
    rev(s, 0, strlen(s) - 1);
}

int main(void)
{
    char s1[] = "hello";
    char s2[] = "abcde";
    char s3[] = "a";
    char s4[] = "";
    char s5[] = "ab";

    reverse(s1); printf("%s\n", s1);  /* olleh */
    reverse(s2); printf("%s\n", s2);  /* edcba */
    reverse(s3); printf("%s\n", s3);  /* a     */
    reverse(s4); printf("%s\n", s4);  /* (empty) */
    reverse(s5); printf("%s\n", s5);  /* ba    */
    return 0;
}

Recursion Trace for “hello”

rev("hello", 0, 4)  swap h↔o → "oellh"
  rev("oellh", 1, 3)  swap e↔l → "olllh" ... wait

Actually each swap operates at the given indices in the same array — let’s trace correctly:

s = "hello"
rev(s, 0, 4): swap s[0]='h' ↔ s[4]='o' → "oellh"
  rev(s, 1, 3): swap s[1]='e' ↔ s[3]='l' → "olllh"...

More carefully: "hello" → swap h/o → "oellh" → swap e/l → "olllh" … hmm wait that’s wrong. Let me retrace: "hello" is h e l l o. Swap index 0 and 4: o e l l h. Swap index 1 and 3: o l l e h. Base: left=2, right=2, done. Result: "olleh". Yes — correct.

Compile and Run

gcc -ansi -Wall ex4-13.c -o ex4-13
./ex4-13

Sample Output

olleh
edcba
a

ba

What This Exercise Teaches

Structural recursion — the string reverse is a classic example where the problem naturally reduces: reversing s[0..n] = swap endpoints + reverse s[1..n-1]
Wrapper + helper pattern — the public reverse(s) computes the initial indices and delegates to the recursive helper; callers don’t need to know about indices
Edge cases — empty string (strlen = 0, so right = -1, which is less than left = 0; base case fires immediately), single character, even and odd lengths all handled correctly by the same left ≥ right base case

Set Up Your C Environment

← Exercise 4-12 |
Chapter 4 Solutions |
Exercise 4-14 →

Book: The C Programming Language, 2nd Ed — Kernighan & Ritchie