Проверка числа на палиндром рекурсивно

Question

Помогите с палиндромом (точнее с рекурсией).

Задается число. Его нужно проверить на зеркальность. Решил это с помощью цикла while. Но по условию задачи нужно реализовать метод через рекурсию. Разрешено использовать только арифметические операторы (массивы тоже нельзя). Вот какой код у меня получился.

class Program
{
    public static bool IsPalindromicNumber (int number)
    {
        if (number < 0)
        {
            throw new ArgumentException($"{number} is less than zero!");
        }

        int numberTemp = number;

        int value;

        int numberRevers = 0;

        while (numberTemp > 0)
        {
            value = numberTemp % 10;
            numberRevers = numberRevers * 10 + value;
            numberTemp /= 10;
        }

        if (numberRevers == number)
        {
            return true;
        }
        else
        {
            return false;
        }
    }

    static void Main(string[] args)
    {
        int a = int.Parse(Console.ReadLine());
        Console.WriteLine(IsPalindromicNumber(a));
    }

Помогите его перевести на язык рекурсии.

Answer 1

На заметку. Все классические алгоритмы проверки палиндромности не переворачивают всё число целиком, они переворачивают только половину числа и проверяют перевёрнутую половину с оставшейся.

public bool IsPalindrome(int x)
{
    // Special cases:
    // As discussed above, when x < 0, x is not a palindrome.
    // Also if the last digit of the number is 0, in order to be a palindrome,
    // the first digit of the number also needs to be 0.
    // Only 0 satisfy this property.
    if(x < 0 || (x % 10 == 0 && x != 0))
        return false;

    int revertedNumber = 0;
    while(x > revertedNumber)
    {
        revertedNumber = revertedNumber * 10 + x % 10;
        x /= 10;
    }

    // When the length is an odd number, we can get rid of the middle digit by revertedNumber/10
    // For example when the input is 12321, at the end of the while loop we get x = 12, revertedNumber = 123,
    // since the middle digit doesn't matter in palidrome(it will always equal to itself), we can simply get rid of it.
    return x == revertedNumber || x == revertedNumber/10;
}

В массивах это может показаться вам непринципиальным моментом, но когда вы доберётесь до односвязных списков вы поймёте, что без этого ваш алгоритм будет работать за O(N^2)

Но чтобы показать вам принцип работы рекурсии -- буду объяснять на вашем алгоритме полного переворота строки, вам так будет легче понять рекурсию.

Вот по факту ваш алгоритм, выкинул некритичные для понимания подробности:

/*
    Time: O(log n)
    Space: O(1)
*/
public static bool IsPalindromicNumber(int number)
{
    int numberReversed = 0;
    int numberOriginal = number;

    while (number > 0)
    {
        var currentDigit = number % 10;
        numberReversed = numberReversed * 10 + currentDigit;
        number /= 10;
    }

    return numberReversed == numberOriginal;
}

А вот ваш алгоритм, записанный в рекурсивной форме:

/*
    Time: O(log n)
    Space: O(log n) for storing call stack
*/
public static bool IsPalindromicNumber(int number)
{
    return IsPalindromicNumber(number, 0, number);
}

public static bool IsPalindromicNumber(int number, int reversed, int original)
{
    if(number == 0)
    {
        return reversed == original;
    }
    else
    {
        var currentDigit = number % 10;
        reversed = reversed * 10 + currentDigit;
        number /= 10;
        return IsPalindromicNumber(number, reversed, original);
    }
}

Если непонятно - рекомендую посмотреть это видео, там разобраны (на примере палиндрома для строки) оба варианта и мне кажется, что наглядно показан call stack во время вызовов методов.

После просмотра разберите подробно call stack и содержимое переменных при выполнении рекурсивного кода в разные моменты моменты времени.

Вот например, фрагмент для проверки числа 1221:

БЛОГ НА HUSL

Проверка числа на палиндром рекурсивно

Ответы (1 шт):