Recursion over arrays and strings
To recurse over a collection you shrink the range you are looking at, usually by moving the start forward or the end backward.
After this lesson
You should be able to
- Write a recursive function that sums or searches an array.
- Use the null terminator as the base case for a string.
- Choose the parameters that make the smaller problem expressible.
Shrink the range, not the array
You cannot make an array smaller, but you can look at less of it. Passing n - 1 means consider only the first n - 1 elements, so the sum of n elements is the last element plus the sum of the rest.
The base case is an empty range, n == 0, whose sum is 0. Notice this is the same identity value that an accumulator starts at in a loop — the reasoning transfers.
int sum_array(const int data[], int n)
{
if (n == 0) /* empty range */
return 0;
return data[n - 1] + sum_array(data, n - 1);
}Strings end themselves
A string does not need a length parameter, because the terminator marks the end. The base case is text[0] == '\0', and the recursive case advances the pointer by one — text + 1 is the same string starting one character later.
This is where pointer arithmetic earns its keep. text + 1 does not copy anything; it is a new address one char further along.
int count_char(const char *text, char target)
{
if (*text == '\0') /* base case */
return 0;
return (*text == target ? 1 : 0) + count_char(text + 1, target);
}Two ends moving inward
Some problems shrink from both sides. To test a palindrome, compare the first and last characters; if they match, test the string between them. The base case is a range of zero or one characters, which is always a palindrome.
Passing two indices rather than one is what makes that expressible. Choosing the right parameters is most of the design work in a recursive function.
Try it yourself
Write a recursive function that reports whether a string is a palindrome, ignoring case.
Need a hint?
Pass a left index and a right index, and move them towards each other.
Check the worked solution
The base case left >= right covers both the empty middle and the single leftover character, so odd and even lengths need no separate handling. tolower comes from ctype.h and makes the comparison case-insensitive; without it "Madam" would fail on its first comparison.
#include <stdio.h>
#include <string.h>
#include <ctype.h>
int is_palindrome(const char *s, int left, int right)
{
if (left >= right) /* base case */
return 1;
if (tolower(s[left]) != tolower(s[right]))
return 0;
return is_palindrome(s, left + 1, right - 1);
}
int main(void)
{
const char *word = "Madam";
int n = strlen(word);
printf("%s\n", is_palindrome(word, 0, n - 1) ? "Palindrome" : "Not");
return 0;
}Quick check
What is the natural base case for a recursive function over a C string?
Why this lesson exists
Syllabus mapping
Recursive Functions with Array and String Parameters
Maps to course outcomes CO4, CO5.