Как «прочувствовать» рекурсию?

Question

[Fruts3]

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

К примеру второй раздел с задачами по рекурсиями на этом сайте:
codingbat.com/java/Recursion-2

Весь раздел базируется на одном методе(codingbat.com/prob/p145416 — show solution), восприятие которого у меня не ладится. Я разбирался в нём — рисовал принцип его работы, но всё равно сложно, у меня нет чувства его восприятия, логики; и скажем если немного поменять условие(следующая задача), я не могу понять что нужно изменить для того чтобы применить этот метод...

Я решил отложить это на потом, и порешать более легкие задачи, одну из которых для себя я придумал сам во время просмотра этого видео(только не формулой):
https://youtu.be/UfEiJJGv4CE?t=168

Задача: дано натуральное число N. Найти количество чисел в промежутке [0-N], содержащих себе цифру "3" в себе без циклов — с помощью рекурсии.

И я её решил... но мне моё решение не нравится. Я передаю два параметра - Number и Сurrent которые абсолютно одинаковые, и являются просто буферами для значений используемых в части кода которая ищет в текущем числе цифру "3" и части кода которая шагает назад от значения N к 0.

public class ThreeCounter {


    public static int ThreeCounter(int number, int current) {

        //Base case -- алгоритм прошел по всем числам
        if(current == 0) {
            return 0;
        }

        //Base case? второй рекурсии -- алгоритм прошел по всем цифрам текущего числа
        if (number == 0) {
            return ThreeCounter(current-1, current - 1);
        }

       if(number % 10 == 3) {
            return 1 + ThreeCounter(current-1, current - 1);
       }


        return ThreeCounter(number/10, current);
    }



    public static void main(String[] args) {

        int n = 100;

        System.out.println(ThreeCounter(n, n));

    }

}

Как сделать этот код "правильнее", потому что не думаю что разумно было бы постоянно писать: "СколькоТроек(тожесамоечисло, тожесамое число)"? И что посоветуете для того чтобы понять вышеупомянутый алгоритм? Там и так всё объяснено на элементарном уровне... Биться головой пока не пойму?

Comments

[Saboteur]

Чтобы понять рекурсию, сперва нужно понять рекурсию.

Answer 1

[Максим Мосейчук]

Как сделать этот код "правильнее", потому что не думаю что разумно было бы постоянно писать: "СколькоТроек(тожесамоечисло, тожесамое число)"?

private static int ThreeCounterImpl(int number, int current) { ... }
public static int ThreeCounter(int number) { return ThreeCounterImpl(number, number); }

Answer 2

[Дмитрий Александров]

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

функция_поиска( url ){
      если (url.файл()) тогда *делаем нужное к примеру смотрим расширение или имя*
      иначе цикл_перебора_содержимого_каталога вызов функция_поиска( url )

Лично я въехал с таких задач в рекурсию.

Еще и сразу, за static методы бьют по рукам а бывает и по голове. Лучше сразу учитесь их избегать и использовать только для финализированных констант.

Comments

[Максим Мосейчук]

Бъют по рукам за нестатические функции, которые не обращаются ни к каким членам объекта. В этот примере статическая функция как раз кстати.

Представьте, что для того, что бы использовать функции min/max вам пришлось бы создавать объект класса Math.

[Дмитрий Александров]

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

Answer 3

[Moskus]

Пробуйте писать программы с более наглядным результатом, желательно - графическим. Обход древовидной структуры, генерация деревьев, генерация кривых Пеано, снежинок Коха, треугольников Серпиньского. Играйте с параметрами. Это очень простые алгоритмы, в которых кроме рекурсии нет вообще ничего.