I don't understand the recursion in this code. It's the answer to the CS50 pset3 atoi practice problem

#include <cs50.h>
#include <ctype.h>
#include <math.h>
#include <stdio.h>
#include <string.h>

int convert(string input);
int number = 0;
int main(void)
    string input = get_string("Enter a positive integer: ");

    for (int i = 0, n = strlen(input); i < n; i++)
        if (!isdigit(input[i]))
            printf("Invalid Input!\n");
            return 1;

    // Convert string to int
    printf("%i\n", convert(input));

int convert(string input)
    // TODO
    int n = strlen(input);

    if (n == 0)
        return number;
    char last_digit = input[n - 1];
    int converted_last_digit = last_digit - '0';
    input[n-1] = '\0';

    return converted_last_digit + 10 * convert(input);

Heres the solution to the pset 3 practice problem atoi, and frankly, it leaves me with more questions than answers. First off, I have zero idea on how the variable "number" becomes the number. It’s initialized at the top as 0, but somehow it becomes the number you put in at the end of all this? Next, I have no idea what adding 10 at the last line of code will even do. Why 10? And when you do convert(input) at the end, how do you even end up with the number you put in? Lets say I put in 123. It starts with the last number (3), then the second to last number(2) and then the first number (1) . So why doesn’t it return 321? Actually, I’m surprised it even returns a 3 digit number at all. When we get to the point that the converted_last_digit variable is equal to the 3, it loops again to get 2 and then 1. But where are those numbers stored? When it loops again, 2 is now equal to converted_last_digit. Then 1 is equal to converted last digit. That should be it right? How are those numbers coming back? Why isn’t it just returning 1? How are those numbers saved?

>Solution :

The variable number is never changed in this code. It is always 0. You could just as well say return 0;.

OK, say you start with "123". You call convert("123");. That pulls off the final digit, so converted_last_digit is 3. Now, you do:

    return 3 + 10 * convert("12");

That calls the function again, with a new string. Thanks to the magic of the stack, this one has its own separate set of variables. In the processing of convert("12"), we again pull off the last digit. That’s 2. So, we do:

    return 2 + 10 * convert("1");

That third call to convert returns 1.

Now, we unwind everything. The result of convert("1") was 1. So, that next-to-the-last statement becomes:

    return 2 + 10 * 1;

which returns 12 to the outer function. That statement then becomes:

    return 3 + 10 * 12;

which returns 123. The magic happens when things unwind.

Leave a Reply