Write a recursive function that returns the total number of characters across a slice of words.
sumOfLengths(words)
Process the slice by handling the first word and recursing on the rest. An empty
slice has total length 0.
Input format: space-separated words on one line (may be empty).
sumOfLengths([]string{"go", "is", "fun"}) // → 7
sumOfLengths([]string{"a"}) // → 1
sumOfLengths([]string{}) // → 0
This moves from recursing on a number down to zero, to recursing on a list by shrinking it one element at a time. The core idea transfers directly: instead of "what happens when a number reaches 0?" you ask "what happens when a list becomes empty?" — and instead of subtracting 1, you peel one element off the front.
What's the simplest list, and its obvious answer? An empty list of words has a total character count of 0 — nothing to sum. Each call should pass along a list one element shorter than what it received, so the list eventually runs out and hits this case.
Split the list into the first word and everything after it. Trust that a recursive call on "everything after the first word" correctly returns the total length of the rest. Then the total for the whole list is just the first word's length plus that trusted result — you only ever reason about one word at a time, plus a smaller version of the same problem.
Calling this on ["go", "is", "fun"] calls it on ["is", "fun"], then ["fun"], then []. That last call is the base case — it returns 0 immediately. Unwinding: the call holding ["fun"] adds 3 to the 0 it received, returning 3. The call holding ["is", "fun"] adds 2, returning 5. The outermost call adds 2 (for "go"), returning 7 — the final answer. Each frame handles one word directly; the rest is delegated downward and resolved as the stack unwinds.
Slicing off one element and recursing on the rest is the standard pattern for processing any sequence recursively — the same shape you'll use for reversing a string, checking a palindrome, or walking a linked list node by node. It works because the problem is naturally self-similar: "the total length of a list" and "the total length of a shorter list" are the same question, just smaller. As before, this costs O(n) stack depth where a loop with a running total would only need O(1) extra space.
def sum_of_lengths(words):
if len(words) == 0:
return 0
return len(words[0]) + sum_of_lengths(words[1:])
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.