как вставить элемент в начале при использовании рекурсии?

Question

Мне нужно заполнить массив цифрами натурального числа, используя рекурсию. Проблема в том, что я не очень хорошо понимаю рекурсию.

int fill(long long number, int arr[10])
{
    if(number<10)
    {
        arr[0]=number;
        return arr[10];
    }
    else
    {
        arr[0]=number%10;
        for(int i=0;i>10;i++)
        {
            arr[i+1]=arr[i];
        }
        return fill(number/10, arr);
    }
}

Если кто-то может чем-то помочь, это будет очень цениться.

Answer 1

Если у вас есть проблема, которую необходимо решить с помощью рекурсии, вам, вероятно, не следует использовать for -loops. Цель состоит в том, чтобы каждая итерация fill() заполняла одну ди git в правильной позиции в массиве и при необходимости снова вызывала себя, чтобы заполнить оставшиеся цифры. У вас уже есть правильная структура в вашем коде, но она неэффективна из-за дополнительных for -l oop. Вы можете избежать этого, используя возвращаемое значение fill(), чтобы отслеживать, где вы должны разместить цифры. Вот возможное решение:

int fill(long long number, int arr[10])
{
    if (!number)
        return 0;

    int pos = fill(number / 10, arr);
    arr[pos] = number % 10;
    return pos + 1;
}

В этой реализации мы будем называть себя рекурсивно, пока число не станет равным нулю. Когда он равен нулю, мы возвращаем 0. Возвращаемое значение используется, чтобы указать, где в массиве мы должны написать di git. Поэтому после того, как мы достигнем самого глубокого уровня рекурсии и вернемся в первый раз, мы записываем наиболее значимые ди git в arr[0]. Тогда мы вернемся 0 + 1. Это означает, что на один уровень рекурсии вверх у нас есть pos = 1, и мы записываем второй по значимости di git в arr[1], а затем мы возвращаем 1 + 1 и так далее, пока не напишем наименее значимый di git и тогда мы закончили. Возвращаемое значение начального вызова fill() тогда равно количеству цифр, записанных в arr.

Есть еще две проблемы с этой функцией. Первый - когда number больше 10 цифр. В этом случае он будет писать после конца массива. Таким образом, вам нужно добавить некоторую проверку, чтобы предотвратить это, или убедиться, что массив достаточно большой, чтобы содержать максимально возможное значение long long (что составляет 20 цифр, если long long - 64-бит). Проверьте LLONG_MAX из заголовка climits.h , чтобы получить максимальное значение для вашей платформы. Во-вторых, эта функция не очень хорошо обрабатывает отрицательные числа. Если вы хотите, чтобы он обрабатывал только неотрицательные числа, измените его на unsigned long long. В этом случае имейте в виду, что наибольшее число - ULLONG_MAX, а на 64-битных платформах это, вероятно, означает 21 цифру.

Answer 2

Я не собираюсь решать это за вас, вот как вы должны думать, если вы хотите освоить рекурсию (что действительно часто бывает трудно для людей, которые сталкиваются с ней впервые).

1. Ваша функция должна заполнять первые элементы массива цифрами и возвращать количество цифр.

2. Предположим, что число> = 10. Вы вызвали fill ( число / 10, обр.) Он вернул x, который является количеством цифр в числе / 10 Что тебе теперь делать? что вы должны вернуть?

3. Предположим, что число <10. Что делать? Что вы должны вернуть? </p>

Answer 3

arr [i + 1] итератор для l oop будет иметь UB, когда i = 9 и i = 10