Topics › Recursion and Backtracking › Get a Strong Hold

Recursive Implementation of atoi()

Medium TUF ID 2862 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

Implement atoi, the C library function that converts a string to a 32-bit signed integer, and do it with recursion instead of loops. The conversion rules are the ones LeetCode uses for “String to Integer (atoi)”:

1. Skip any leading spaces.
2. Read one optional sign character, + or -.
3. Read digits until the first non-digit character or the end of the string. Everything after that is ignored.
4. If no digits were read, the answer is 0.
5. If the value is outside the range [-2^31, 2^31 - 1], clamp it to the nearest bound.

Constraints: 0 ≤ s.length ≤ 10^4; s may contain letters, digits, spaces, +, - and ..

Example 1

s = "   -42"
answer = -42             // skip three spaces, read '-', read "42"

Example 2

s = "4193 with words"
answer = 4193            // parsing stops at the space after "4193"

Example 3

s = "-91283472332"
answer = -2147483648     // below the int range, so it is clamped to Integer.MIN_VALUE

The problem is a classic “translate a loop into recursion” exercise: the parser is naturally a sequence of small steps, and each step can become a recursive call that handles one character and leaves the rest to the next call. The iterative version is included as a baseline so that both recursive versions can be checked against it.

Approach 1: The iterative parser

Intuition. Walk an index i through the string, in the exact order of the rules: spaces, sign, digits. Accumulate the digits into a long and stop as soon as the number has left the int range.

Algorithm.

1. Advance i while s[i] is a space.
2. If s[i] is + or -, record the sign and advance.
3. While s[i] is a digit: value = value * 10 + digit. If sign * value is above Integer.MAX_VALUE or below Integer.MIN_VALUE, return that bound immediately.
4. Return sign * value as an int.

static int iterative(String s) {
    int n = s.length(), i = 0;
    while (i < n && s.charAt(i) == ' ') i++;                      // 1. skip leading spaces
    int sign = 1;
    if (i < n && (s.charAt(i) == '+' || s.charAt(i) == '-')) {    // 2. one optional sign
        if (s.charAt(i) == '-') sign = -1;
        i++;
    }
    long value = 0;
    while (i < n && isDigit(s.charAt(i))) {                        // 3. digits, until the first non-digit
        value = value * 10 + (s.charAt(i) - '0');
        if (sign * value > Integer.MAX_VALUE) return Integer.MAX_VALUE;   // 4. clamp as soon as the int range is left
        if (sign * value < Integer.MIN_VALUE) return Integer.MIN_VALUE;
        i++;
    }
    return (int) (sign * value);
}

Complexity. Time O(n): every character is visited at most once. Space O(1).

The clamp inside the loop matters for correctness, not only for speed. A long holds about 19 digits, so a 25-digit input would overflow it if we parsed everything first. Checking after every digit means value is at most about 2.1 × 10^10 when the check fires, which is far inside the long range.

Only ASCII '0' to '9' count as digits. Character.isDigit also accepts digits from other scripts, which atoi does not.

Approach 2: Recursion with an accumulator

Intuition. A loop is a function whose state lives in local variables. To turn it into recursion, move the state into parameters: the index i and the running value acc. Each call looks at exactly one character. If it is a digit, fold it into the accumulator and call again on i + 1; otherwise the number is complete and the call returns it. Skipping spaces is the same idea with a boolean condition and no accumulator.

Algorithm.

1. skipSpaces(s, 0) returns the index of the first non-space character by calling itself on i + 1 while s[i] is a space.
2. Read the optional sign at that index.
3. parseDigits(s, i, sign, 0): if s[i] is not a digit (or i is the end), return sign * acc. Otherwise compute next = acc * 10 + digit, clamp if it has left the int range, and recurse with i + 1 and next.

static int recursiveAccumulate(String s) {
    int i = skipSpaces(s, 0);
    int sign = 1;
    if (i < s.length() && (s.charAt(i) == '+' || s.charAt(i) == '-')) {
        if (s.charAt(i) == '-') sign = -1;
        i++;
    }
    return parseDigits(s, i, sign, 0);
}

static int skipSpaces(String s, int i) {
    if (i < s.length() && s.charAt(i) == ' ') return skipSpaces(s, i + 1);
    return i;
}

static int parseDigits(String s, int i, int sign, long acc) {
    if (i == s.length() || !isDigit(s.charAt(i))) return (int) (sign * acc);   // base case: the digit run has ended
    long next = acc * 10 + (s.charAt(i) - '0');
    if (sign * next > Integer.MAX_VALUE) return Integer.MAX_VALUE;              // clamp now, before acc could ever overflow a long
    if (sign * next < Integer.MIN_VALUE) return Integer.MIN_VALUE;
    return parseDigits(s, i + 1, sign, next);
}

Complexity. Time O(n), one call per consumed character. Space O(n) for the call stack in the worst case, because Java does not eliminate tail calls.

Notice how shallow the digit recursion really gets: parseDigits returns from the clamp after at most eleven digits, so a string like "1111...1" of ten thousand ones costs eleven frames, not ten thousand. The depth is dominated by the leading spaces.

The recursive call is the last thing each function does, which is what makes this a tail recursion: nothing is left to do on the way back up, the result just passes straight through every frame. That is why it mirrors the loop so closely.

Approach 3: Recursion that returns a value

Intuition. Positional notation is itself recursive: the number written by the digits d_0 d_1 ... d_k is ten times the number written by d_0 ... d_(k-1), plus d_k. So define valueOf(start, end) as the value of the digit run s[start, end), with valueOf(start, start) = 0, and let each call combine the result of the smaller problem on the way back up. This is the other fundamental recursion shape: work after the call instead of before it.

To use it we need to know where the digit run ends, which is a second small recursion, endOfDigits.

Algorithm.

1. Skip spaces and read the sign as before; let i be the first digit position.
2. end = endOfDigits(s, i): recurse while s[i] is a digit, return the first index that is not.
3. valueOf(s, i, end): if end == start return 0; otherwise 10 * valueOf(s, start, end - 1) + digit(end - 1), capped at 10^10.
4. Apply the sign, clamp to the int range, return.

static int recursiveReturn(String s) {
    int i = skipSpaces(s, 0);
    int sign = 1;
    if (i < s.length() && (s.charAt(i) == '+' || s.charAt(i) == '-')) {
        if (s.charAt(i) == '-') sign = -1;
        i++;
    }
    int end = endOfDigits(s, i);
    long signed = sign * valueOf(s, i, end);
    if (signed > Integer.MAX_VALUE) return Integer.MAX_VALUE;
    if (signed < Integer.MIN_VALUE) return Integer.MIN_VALUE;
    return (int) signed;
}

static int endOfDigits(String s, int i) {
    if (i < s.length() && isDigit(s.charAt(i))) return endOfDigits(s, i + 1);
    return i;
}

static long valueOf(String s, int start, int end) {
    if (end == start) return 0;                                   // base case: no digits means zero
    long prefix = valueOf(s, start, end - 1);                     // everything except the last digit
    long value = prefix * 10 + (s.charAt(end - 1) - '0');
    return Math.min(value, 10_000_000_000L);
}

Dry run on s = " -42":

Complexity. Time O(n). Space O(n) stack: endOfDigits and valueOf each go one frame deep per digit, so unlike Approach 2 a long run of digits does produce a deep recursion.

The cap at 10^10 plays the role of the early clamp. We cannot clamp inside valueOf because the sign is applied outside it, but we do not need the exact value either: anything at or above 10^10 is beyond both int bounds, so after the sign is applied the final clamp gives the right answer, and the cap keeps the long from overflowing on inputs of twenty or more digits.

Edge cases and pitfalls

• Two signs. "+-12" is 0. Only one sign character is consumed; the second one is a non-digit that ends the number before any digit is read.
• No digits at all. "", " " and "words and 987" all give 0. The digit recursion hits its base case immediately.
• Leading zeros. " 0000000000012345678" is 12345678. Zeros are ordinary digits and the value stays 0 until a non-zero digit arrives, so no special handling is needed.
• Overflow. "2147483648" is one more than Integer.MAX_VALUE and must clamp. "9223372036854775808" does not even fit in a long; a parser that accumulates everything before checking would wrap around. Both the early clamp (Approaches 1 and 2) and the cap (Approach 3) avoid this.
• Whitespace. Only the space character is skipped. A tab or newline is a non-digit and ends the parse.
• Trailing garbage. "4193 with words" and "00000-42a1234" show that parsing stops at the first non-digit after the digits began, and that a sign is only legal before the first digit.
• Recursion depth. One frame per character in skipSpaces, endOfDigits and valueOf. For 10^4 characters this is fine; for a string of several hundred thousand digits the recursive versions would throw StackOverflowError and the loop is the right tool. The tests go to 3000 digits.
• -0. The sign is applied to 0, which is still 0.

Related problems

• String to Integer (atoi) is the same conversion in the strings section, solved iteratively.
• Check if String is Palindrome or Not is another recursion that walks a string with an index parameter.
• Pow(x, n) is the next recursion in the sheet, where the subproblem shrinks by half instead of by one character.
• Understand recursion by print something N times introduces the before-the-call and after-the-call distinction that separates Approaches 2 and 3 here.