[CS50 Practice - #Recursive atoi]

Recursive atoi

Learning Goals

• 문자열에 대한 심화 이해
• 재귀 함수 생성 연습

Background

C 프로그래밍 언어가 처음 만들어졌던 1970년대로 시간여행을 한다고 상상해 보세요. 당신은 문자열을 정수로 변환하는 방법을 찾기 위해 프로그래머로 고용되었습니다. (2주차에는 atoi라는 이와 같은 함수를 사용했을 수도 있습니다.) 개발 프로세스를 철저하게 진행하고 가장 효율적인 방법을 결정하기 전에 여러 가지 접근 방식을 시도해 볼 계획입니다.

이 문제에서는 루프를 사용하여 양의 정수를 처리하는 atoi의 간단한 구현부터 시작합니다. 재귀를 사용하는 구현으로 이를 재작업하고 싶습니다. 재귀 함수는 메모리 집약적일 수 있으며 항상 최선의 솔루션은 아니지만 재귀를 사용하면 더 간단하고 우아한 솔루션을 제공할 수 있는 몇 가지 문제가 있습니다.

(이 페이지 하단으로 스크롤하여 atoi 구현이 실제로 어떤 모습인지 확인하세요.)

Hints

• 문자열의 마지막 문자(\0 앞의 문자)의 인덱스를 가져오는 것부터 시작합니다.
• 이 문자를 숫자 값으로 변환합니다. 이를 위해 일부 문자를 뺄 수 있나요?
• Null 종결자를 왼쪽으로 한 위치 이동하여 문자열에서 마지막 문자를 제거합니다.
• 이 값에 새 단축 문자열의 정수 값을 10배 더한 값을 반환합니다.
• 재귀 함수를 생성할 때 base case가 필요하다는 점을 기억하세요.

Demo

Demo 보기

Getting Started

1. GitHub 계정을 사용하여 cs50.dev에 로그인합니다.
2. 터미널 창 내부를 클릭하고 cd를 실행합니다.
3. 코드 공간에 atoi.zip이라는 zip을 다운로드하려면 wget https://cdn.cs50.net/2022/fall/labs/3/atoi.zip을 실행한 다음 Enter 키를 누르세요. wget과 다음 URL 또는 해당 문제에 대한 다른 문자 사이의 공백을 간과하지 않도록 주의하세요!
4. 이제 upzip atoi.zip을 실행하여 atoi라는 폴더를 만듭니다.
5. 더 이상 ZIP 파일이 필요하지 않으므로 rm atoi.zip을 실행하고 프롬프트에서 "y" 다음에 Enter를 입력하면 됩니다.

Implementation Details

재귀 버전의 변환에서는 마지막 문자부터 시작하여 정수 값으로 변환합니다. 그런 다음 문자열을 줄이고 마지막 문자를 제거한 다음, 단축된 문자열을 입력으로 사용하여 재귀적으로 변환을 호출하면 다음 문자가 처리됩니다.

생각해보기

재귀 함수를 만들 때마다 base case가 필요한 이유는 무엇입니까?

A More Thorough Implementation

atoi의 실제 버전은 음수는 물론 선행 공백 및 숫자가 아닌 문자도 처리해야 합니다. 다음과 같이 보일 수 있습니다.

#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.](From techiedelight.com/implement-atoi-function-c-iterative-recursive.)

나의 풀이

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

int convert(string input);

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])) // isdigit: char형이 숫자에 해당하는 ASCII 코드 값인지 아닌지 판별
        {
            printf("Invalid Input!\n");
            return 1;
        }
    }

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

int convert(string input)
{
    // TODO
    int length = strlen(input); // 문자열 길이

    // input[length-1] - '0'의 의미 : 
    // 마지막 문자(정수)의 아스키코드에서 정수'0'의 아스키코드를 빼면 원래의 숫자가 나온다
    // ex) 숫자 8(ASCII: 56): 56 - 48 = 8
    int last = input[length - 1] - '0';

    if (length == 1) //  Base Case
    {
        return last;
    }
    else
    {
        input[length - 1] = '\0';
        printf("%s\n", input);
        return (10 * convert(input) + last);
    }
}