Рекурсия. Пример работы с натуральным числом

Сайт не является учебником по программированию. Это только небольшой авторский сборник информации в помощь начинающим программистам.
    ЗАДАЧА Дано натуральное число:

  • Определить его максимальную и минимальную цифры
  • Определить, на сколько его максимальная цифра превышает минимальную
  • Найти сумму его максимальной и минимальной цифр

Для начала вспомним, что

  • Отрицательные и нецелые числа натуральными не являются

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

Пример решения с помощью рекурсии

В этом примере исходное число не изменяется, каждый вызов функции записывается в стек и поэтому получается некоторое количество совершенно разных чисел N. Обратите внимание, что перед N у рекурсивной функции указано, что N является константой.

Минимум и максимум вычисляются непосредственно внутри рекурсивной функции. Так как планируется изменять минимум и максимум, то чтобы не создавать кучу разных чисел, обозначающих минимум и максимум, с минимумом и максимом мы работаем напрямую. (Принятие параметра по ссылке не создаёт локальной копии переменной внутри функции)

Имеет смысл присмотреться к тому, что возвращает функция getnumber,

Возвращается функция. Первый параметр N/10 обозначает, что каждое следующее значение N, которое будет создано и записано в стек, будет в 10 раз меньше чем текущее.
Ограничение if (N==0) return N; прекращает вызов рекурсивной функции и возвращает обычное число, а не функцию.

Например если число N=12 345, то в стеке будут созданы такие N
12 345
1 234
123
12
1
(1/10=0 — возврат не рекурсивный) == 0

Итого 6 различных N

Но Минимум и максимум не будут создаваться, так как параметр принимается по ссылке, то для каждой из 6 записанных функции в стеке, эти значения будут обрабатываться по одному адресу памяти, т.е. напрямую. Это дает возможность изменять эти значения в зависимости от результатов проверки условий.

==================
12 345 % 10 == 5 //Получили самое правое число
12 34 % 10 == 4   //Получили второе число справа-налево
123 % 10 ==3     //Третье справа-налево

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

=================
Знаю, что описал не очень-то и понятно, но буду надеяться, что описал вполне доступным языком для начинающих программистов и что-то кому-то помог понять.

Все комментарии на сайте проверяются, поэтому ваш комментарий может появиться не сразу. Для вставки кода в комментарий используйте теги: [php]ВАШ_КОД[/php]

3 комментария: Рекурсия. Пример работы с натуральным числом

  • Аноним говорит:

    🙄 😯

  • dmitrey говорит:

    почему если мы зададим N через консоль , выдает неверный ответ?

    Автор сайта отвечает:
    а поточнее

    dmitrey говорит:
    если N не константа, а мы ее вводим через cin >>

    Автор сайта отвечает:
    Пример некорректно работает если вводить отрицательное число, т.к. каждая цифра получается отрицательной. Если вводить целое положительное, то у меня пример работает.

  • Павел говорит:

    мне не понятна перезапись минимума и максимума. насколько мне известно, функция swap меняет местами введенные в нее параметры

    Автор сайта отвечает:
    Этот пример приведён не для решения задачи, а для помощи в изучении рекурсии.
    Тут вообще-то применяется функция swap внутри рекурсивной функции.
    Можно без swap, просто присвоить min=temp, max=temp в тех местах (как сейчас уже и есть).

Добавить комментарий

Ваш e-mail не будет опубликован.

Поиск

 
     

Яндекс.Метрика

НАГРАДИ АВТОРА САЙТА
WEBMONEY
R375024497470
U251140483387
Z301246203264
E149319127674

Демотиватор

Выражаю свою признательность

  • Максиму очень признателен за указание на мои ошибки и неточности.
  • Sergio ===> за оказание помощи в исправлении моих ошибок
  • Gen ===> за правильное стремление помочь другим новичкам и выявления моих ошибок