Recursion with parameters and return values

The functions in the last lesson only printed. Most problems want an answer back: a sum, a count, true or false.

The question that stops learners: while ten calls wait on the stack, where does the answer live? There are two places to keep it, and once you see both, most early recursion problems look the same.

Two ways to carry an answer

Take the smallest example: the sum of the first n numbers. For n = 3, the answer is 1 + 2 + 3 = 6.

Pass it down: parameterised recursion

Give the function an extra parameter, total, that holds the sum so far. Each call adds its number and passes the new total to the next call.

JavaPythonTypeScript

int sumDown(int i, int total) {
    if (i == 0) return total; // nothing left to add
    return sumDown(i - 1, total + i);
}

// sumDown(3, 0) returns 6

• total is the sum of the numbers already added.
• The base case returns total, because by then it holds the whole answer.

Return it up: functional recursion

Here no call carries a total. Each call asks the smaller call for its sum, then adds its own number to the reply.

JavaPythonTypeScript

int sumUp(int n) {
    if (n == 0) return 0; // the sum of no numbers
    return n + sumUp(n - 1);
}

// sumUp(3) returns 6

• sumUp(n - 1) is the sum of 1 to n − 1. Trust it.
• n + is this call's own work, done after the smaller call returns.

┌────────────────────────────────────────────┐
│                                            │
│                                            │
│      call               returns            │
│      sum(3, 0)          6                  │
│        sum(2, 3)        6                  │
│          sum(1, 5)      6                  │
│            sum(0, 6)    6  base case       │
│                                            │
│                                            │
└────────────────────────────────────────────┘

┌────────────────────────────────────────────┐
│                                            │
│                                            │
│         call         returns               │
│         sum(3)       3 + 3 = 6             │
│           sum(2)     2 + 1 = 3             │
│             sum(1)   1 + 0 = 1             │
│               sum(0) 0  base case          │
│                                            │
│                                            │
└────────────────────────────────────────────┘

Read each card top to bottom for the calls (each line is called by the line above it), then bottom to top for the returns. Same answer, same number of calls. The difference is when the adding happens:

Learn both, but practise the second one most. Trees, divide and conquer and dynamic programming all return answers up.

The pass-it-down version still uses one frame per call. Some languages reuse the frame for a tail call, but Java, Python and Node do not. In our runs, sumDown(100000, 0) overflowed the stack in all three, the same as sumUp.

One shape, many problems

Most early recursion problems answer the same three questions from the last lesson. Only the answers change:

Factorial, for example, is the sum with two changes: the base case returns 1, and it multiplies.

JavaPythonTypeScript

long factorial(int n) {
    if (n <= 1) return 1; // 0! and 1! are both 1
    return n * factorial(n - 1);
}

// factorial(5) returns 120

Factorials grow fast, so watch the number type:

• In Java, an int holds factorials only up to 12!. The code returns long, which holds up to 20!.
• In Python, integers never overflow, so 30! comes out exact.
• In TypeScript, a number stays exact up to 22!. Past that, use BigInt.

Reverse an array: two pointers, one call per swap

Some problems change the input instead of building a value. To reverse an array in place, swap the two ends, then reverse the part between them.

• left marks the first item not yet swapped.
• right marks the last item not yet swapped.
• When left >= right, zero or one item is left in the middle, so there is nothing to swap.

JavaPythonTypeScript

void reverseArray(int[] arr, int left, int right) {
    if (left >= right) return; // the pointers met: done
    int temp = arr[left];
    arr[left] = arr[right];
    arr[right] = temp;
    reverseArray(arr, left + 1, right - 1);
}

// with nums = {1, 2, 3, 4, 5}:
// reverseArray(nums, 0, nums.length - 1) makes it {5, 4, 3, 2, 1}

The swap is one line in Python and TypeScript. Java has no such swap, so it uses a temp variable.

The same two-pointer recursion answers this lesson's main problem. There it returns a value.

Read the problem

Ask these before you code:

• One letter, or two equal letters? Both are palindromes. That shapes the base case.
• Even and odd lengths? Check both: "abba" and "racecar".
• Capital letters, spaces, punctuation? Not here: lowercase letters only. Some versions ask you to ignore them, so ask.
• How deep can it go? The recursion makes about n / 2 calls. For n = 1,000, that is 500 frames. That is safe in all three languages, even under Python's default limit of 1,000.

n ≤ 1,000 allows even O(n²). Every answer below is O(n), so the real question is the extra space.

Brute force: reverse and compare

The first idea: build the reversed string and compare it with the original.

JavaPythonTypeScript

boolean isPalindrome(String s) {
    return s.equals(new StringBuilder(s).reverse().toString());
}

Each language builds the reversed copy its own way: StringBuilder.reverse() in Java, the slice s[::-1] in Python, and an array that is reversed and joined in TypeScript.

Building the copy reads n letters. The comparison reads up to n more. Time is O(n), and the copy costs O(n) extra space.

It fits the limits. Its weakness: it always reads the whole string, even when the first two letters already differ.

The loop you know: two pointers

The usual loop, from string basics, puts one pointer at each end:

JavaPythonTypeScript

boolean isPalindromeLoop(String s) {
    int left = 0;
    int right = s.length() - 1;
    while (left < right) {
        if (s.charAt(left) != s.charAt(right)) return false;
        left++;
        right--;
    }
    return true;
}

O(n) time, O(1) extra space, and it stops at the first mismatch. Now write the same idea as recursion.

The key insight: a palindrome has a palindrome inside

Peel off the two end letters. If they match, the string is a palindrome exactly when the middle is one.

┌────────────────────────────────────────────┐
│                                            │
│   r a c e c a r   r and r match            │
│     a c e c a     a and a match            │
│       c e c       c and c match            │
│         e         one letter: true         │
│                                            │
│   a b c a         a and a match            │
│     b c           b and c differ: false    │
│                                            │
└────────────────────────────────────────────┘

That gives the whole function:

• Base case 1: left >= right. Zero or one letter is left, so return true.
• Base case 2: the end letters differ. Return false at once.
• Recursive case: the ends match, so the answer is the answer for the middle.

Recursive solution

JavaPythonTypeScript

boolean isPalindrome(String s, int left, int right) {
    if (left >= right) return true; // 0 or 1 letters left
    if (s.charAt(left) != s.charAt(right)) return false; // the ends differ
    return isPalindrome(s, left + 1, right - 1); // the middle decides
}

// isPalindrome("racecar", 0, 6) returns true

This is functional recursion: the answer comes back up as a return value. Each call passes the reply from its inner call up unchanged.

Cost. About n / 2 calls, each doing O(1) work, so O(n) time. The stack holds up to n / 2 + 1 frames, so O(n) extra space.

Edge cases. The empty string starts with right = -1, so the first call returns true. "a" returns true. "ab" returns false on the first comparison.

Depth. With n ≤ 1,000 the stack stays at 500 frames. Past the limits, each language gives out at a different length. In our runs, the longest palindrome that passed was:

• Python: about 2,000 letters, because the default limit is 1,000 frames.
• JavaScript (Node): about 15,000 letters. 20,000 overflowed.
• Java: about 30,000 letters. 40,000 overflowed.

For long strings, use the loop.

Side by side

In an interview, the loop is the best answer to this problem. Learn the recursive one for its shape: "handle the ends, then ask about the middle" returns in trees and in divide and conquer, where a loop is much harder to write.

How to spot this pattern

The template for "return it up", on Sum of Array Elements II:

JavaPythonTypeScript

int sumFrom(int[] arr, int i) {
    if (i == arr.length) return 0; // 1. base case: no items left
    int rest = sumFrom(arr, i + 1); // 2. trust the smaller call
    return arr[i] + rest; // 3. combine this item with the rest
}

The same shape fits other problems on this lesson's list:

• Check if the Array is Sorted II: if arr[i] > arr[i + 1], return false. Otherwise ask about the array from i + 1.
• Sum of Digits: combine n % 10 with the sum of digits of n without its last digit (n / 10 in Java, n // 10 in Python, Math.floor(n / 10) in TypeScript). Stop when n has one digit.
• Reverse a String I: the same two-pointer swap as the array, on an array of characters.
• Check if a Number is Prime: try a divisor d from 2. If d * d > n, return true. If n % d == 0, return false. Otherwise try d + 1.

take U forwardYouTube

Read more

• Functions: recursion in the MDN guide, with loops rewritten as recursion
• Tail call on Wikipedia, why some languages can run pass-it-down recursion without a deep stack
• Re 4. Problems on Functional Recursion by Striver, reversing an array and checking a palindrome

Next: a function that calls itself twice, and why Fibonacci gets slow so fast.