Recursive `atoi`

Learning Goals

Deepen an understanding of strings
Practice creating recursive functions

背景

Imagine that you travel 返回 in时间 to the 1970’s, when the C 编程 language was first created. You are hired as a programmer to come up with a way to convert strings to ints. (You可能有 used a function just like this in 第 2 周, called atoi). You want to be thorough in your development process and plan to try several approaches before deciding on the most efficient.

In this problem, you will start with a simple implementation of atoi that handles positive ints using loops. You want to rework this into an implementation that uses 递归. Recusive functions can be 内存 intensive and are not always the best solution, but there are some problems in which using 递归 can provide a simpler and 更多 elegant solution.

(Scroll to the bottom of this page to see what an implementation of atoi might actually look like.)

提示
- Start by getting the index of the last char in the string (the char before the \0).
- Convert this char into its numeric value. Can you subtract some char to do this?
- Remove the last char from the string by moving the null terminator one position to the left.
- Return this value plus 10 times the integer value of the new shortened string.
- Remember you need a base case when creating a recursive function.

演示

入门

Log into cs50.dev using your GitHub account.
Click inside the terminal window and execute cd.
Execute wget https://cdn.cs50.net/2022/fall/实验s/3/atoi.zip followed by Enter in order to 下载 a zip called atoi.zip in your codespace. Take care not to overlook the space between wget and the following URL, or any other character for that matter!
Now execute unzip atoi.zip to create 的文件夹中名为 atoi.
You 不再 need the ZIP file, so you can execute rm atoi.zip and respond with “y” followed by Enter at the prompt.

实现细节

In the recursive version of convert, start with the last char and convert it into an integer value. Then shorten the string, removing the last char, and then recursively call convert using the shortened string as input, where the 下一页 char will be processed.

Thought 问题

Why do you need a base case whenever you 创建一个 recursive function?

如何测试 Your Code

你的程序应该 behave per the例子below.

atoi/ $ ./atoi
Enter a positive integer: 3432
3432

atoi/ $ ./atoi
Enter a positive integer: 98765
98765

No check50 for this one!

To evaluate that the style of your code, type in the following at the $ prompt.

style50 atoi.c

如何提交

No need to 提交! This is an 可选练习题.

一份更多 Thorough 实现

The actual version of atoi must handle negative numbers, as well as leading spaces and non-numeric characters. It might look something like this:

#include <stdio.h>
 
// Iterative function to implement `atoi()` function in C
long atoi(const char S[])
{
    long num = 0;
    int i = 0, sign = 1;
 
    // skip white space characters
    while (S[i] == ' ' || S[i] == '\n' || S[i] == '\t') {
        i++;
    }
 
    // note sign of the number
    if (S[i] == '+' || S[i] == '-')
    {
        if (S[i] == '-') {
            sign = -1;
        }
        i++;
    }
 
    // run till the end of the string is reached, or the
    // current character is non-numeric
    while (S[i] && (S[i] >= '0' && S[i] <= '9'))
    {
        num = num * 10 + (S[i] - '0');
        i++;
    }
 
    return sign * num;
}
 
// Implement `atoi()` function in C
int main(void)
{
    char S[] = " -1234567890";
 
    printf("%ld ", atoi(S));
 
    return 0;
}

From techiedelight.com/implement-atoi-function-c-iterative-recursive.

Recursive atoi