Использование рекурсии для определения количества цифр

Question

В настоящее время я застрял в одной строке кода, который я не до конца понимаю.Итак, я читаю примеры кодов из книги, и одна из «программ» использовала рекурсию для определения количества цифр в целом числе n.Одна строка кода, в которой я застрял и не до конца понимаю:

if (number >= 10) {
    return numberOfDigits(number / 10) + 1;

Например, это возвращает число 42, возвращающее 2, что и должно быть.Но как именно функция возвращает 2?42, деленное на 10, равно 4,2 или 4. Этот плюс 1 равен 5, так как же он возвращает 2?

Answer 1

Полный метод, вероятно, выглядит примерно так:

public int numberOfDigits(int number) {
    if (number >= 10) {
        return numberOfDigits(number / 10) + 1;
    }

    // base case: only one digit
    return 1;
}

В результате проверки, если мы передадим двузначное число, будет выполнен оператор if, который будет возвращать любой рекурсивный вызоввход / 10 есть, плюс один.Допустим, входные данные были 42.В этом случае он вернул бы numberOfDigits(42 / 10) + 1.Мы знаем, что numberOfDigits(4) возвращает 1, поэтому это вернет всего 2. Это правильно.

Используя индуктивные рассуждения, мы можем построить, чтобы убедить себя в любом количестве произвольной длины.

Примечание: в моих путешествиях я чаще видел, как базовый случай обрабатывался сначала с помощью оператора if, а индуктивный случай по умолчанию.Итак, я бы ожидал увидеть этот код:

public int numberOfDigits(int number) {
    if (number < 10) return 1;

    return numberOfDigits(number / 10) + 1;
}

Answer 2

Рекурсия - это способ получить один вызов метода для выполнения некоторой работы, в то же время откладывая оставшуюся часть работы до выполнения другого рекурсивного вызова.Здесь рекурсивный метод «количество цифр» говорит, что количество цифр в числе равно 1 для последней цифры плюс количество цифр, оставшихся после удаления последней цифры.

Вreturn, + 1 считает последнюю цифру в номере, а number / 10 выполняет усечающее целочисленное деление для удаления последней цифры.В рекурсивном вызове подсчитываются цифры в номере с удаленной последней цифрой.

То, что вы не показали, является базовым случаем рекурсии, когда число однозначное (не больше или не равно *).1009 *).Это просто 1 цифра.Значение 4 не учитывается при расчете.Метод эффективно подсчитывает цифры, по одной за раз, пока не останется больше цифр.На цифру приходится один рекурсивный вызов метода.