Каким образом работают рекурсивные вызовы

Question

Пытаюсь осилить рекурсию. Задача: вывести все цифры числа в прямом порядке через пробел или другой разделитель, используя только целочисленную арифметику и рекурсию. Сторонние пакеты НЕЛЬЗЯ. Я написал придумал такое решение:

package main

func main() {
    rec(198, 0)
}

func rec(n, m int) (int, int) {
    if n == 0 {
        //убрать лишний ноль в конце перевернутого числа
        m /= 10
        //завершить выполнение когда все цифры числа будут выведены.
        if m == 0 {
            //функция перестает вызываться рекурсивно, когда все цифры выведены в прямом,
            //по отношению к начальному числу, порядке.
            return 0, 0
        }
        //вывести остаток от деления m на 10. Получаем последнюю цифру перевернутого числа
        print(m%10, " ")
        //убрать ту цифру которую уже вывели.
        m /= 10
    }
    //рекурсивный переворот начального числа(делается в первую очередь)
    //когда все разряды прибавлены к m и умножены на 10,
    //получаем не цифры в обратном порядке, а именно перевернутое число.
    //но в конце у него будет 0, его потом убираем внутри n==0 && m!=0
    m += n % 10
    //запускаем функцию с аргментом без последней цифры начального числа,
    //которую уже включили в перевернутое число
    //m умножаем на 10, как раз чтобы получить не просто цифры в обратном порядке а именно число.
    //когда число будет переврнуто и функция провалится в условие n==0 && m!=0
    //функция будет вызываться так же рекурсивно но с 0 в качестве обоих аргументов.
    return rec(n/10, m*10)
}

Но у меня есть подозрение, что можно сделать как то без той части условия, где n=0 && m!=0. Но пока что не пойму как. Подскажите пожалуйста, если знаете.

UPD:

package main


func main() {
    rec(123456789098765432)
    println()
}

func rec(n int) {
    if n < 10 {
        print(n)
    } else {
        rec(n / 10)
        print(" ", n%10)
    }
}

в этом подходе результат рекурсивных вызовов работает по принципу стека чтоли? LIFO? Во первых принты не выполняются при каждом else а сначала вызываются все экземпляры функции rec() а уже потом происходит вывод, но вывод происходит в обратном порядке по отношению к вызовам rec() но если выводы поставить перед вызовом rec(), то порядок вывода будет прямой по отношению к вызовам, но обратный по отношению к начальному числу.

Answer 1

Что-то вы намудрили:

func main() {
      print_digits(1023)
}

func print_digits(n int) {
    if (n>9) {
        print_digits(n/10)
    }   
    fmt.Print(n%10, " ")
}

>> 1 0 2 3

Answer 2

Рекурсивный алгоритм проектируется так:

определить окончание рекурсии
определиться с порядком действий: сначала обрабатываем элемент, затем передаём дальше по цепочке, или сначала обрабатываем цепочку, и только затем выполняем действие над элементом.

В вашем случае окончание рекурсии - число, состоящее из одной цифры. С ним можно сделать только одно - напечатать его и вернуть управление.

Теперь про действия. Если в числе больше одной цифры, то удобно вы можете извлечь только крайнюю правую, взяв остаток от деления на 10. Это и есть тот элемент, над которым выполняется действие - печать с разделителем. Но печатать вам нужно слева направо, поэтому с порядком тоже понятно - сначала рекурсия, которая напечатает цифры слева, и только затем печатаем крайнюю правую цифру.

Получается вот какая функция:

// Печатает цифры числа с разделителем `delim` между цифрами.
// Печатает в `os.Stdout`
func print_digits(n uint, delim string) {
    if n < 10 {
        // Самая левая цифра, перед ней не печатаем разделитель
        fmt.Print(n)
    } else {
        // Печатаем цифры слева
        print_digits(n/10, delim)
        // Печатаем разделитель и крайнюю правую цифру
        fmt.Print(delim, n%10)
    }
}

Сначала проверяем, завершена ли рекурсия: if n < 10 {}. Рекурсия у нас заканчивается в самой левой цифре, поэтому разделитель не печатаем:

    if n < 10 {
        // Самая левая цифра, перед ней не печатаем разделитель
        fmt.Print(n)
    }

Теперь тело рекурсии:

        // Печатаем цифры слева
        print_digits(n/10, delim)
        // Печатаем разделитель и крайнюю правую цифру
        fmt.Print(delim, n%10)

Проверка для чисел 1 (разделитель -), 10 (разделитель +) и 123 (разделитель /): https://go.dev/play/p/eXps2XXKLqO

1
1+0
1/2/3

Работает ))

PS. На самом деле есть ещё третий вариант рекурсии - сначала делаем половину действия, вызываем рекурсию, и после выполняем вторую половину. Но в вашем случае это не требуется.

БЛОГ НА HUSL

Каким образом работают рекурсивные вызовы

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