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

Вот пример с использованием sync.WaitGroup для координации завершения всех горутин:

package main

import (
    "fmt"
    "sync"
)

var k, m, n int

func out(temp []int) {
    for _, v := range temp {
        fmt.Printf("%d", v)
    }
    fmt.Println()
}

func rec(idx int, temp []int, wg *sync.WaitGroup) {
    defer wg.Done() // Уменьшаем счетчик горутин

    if idx == n {
        out(temp)
        return
    }

    for i := 0; i <= m; i++ {
        newTemp := make([]int, len(temp))
        copy(newTemp, temp)
        newTemp[idx] = i

        wg.Add(1) // Увеличиваем счетчик горутин
        go rec(idx+1, newTemp, wg)
    }
}

func main() {
    k, m, n = 0, 1, 3 // Пример значений
    temp := make([]int, n) // создаем копию массива `temp` чтобы избежать конфликтов данных
    var wg sync.WaitGroup

    wg.Add(1)
    go rec(0, temp, &wg)

    wg.Wait() // Ждем завершения всех горутин
}

Ваш код вполне себе работает: https://go.dev/play/p/n3FS3JCuhvH Зачем вам нужны горутины?

В общем случае вызов горутины из горутины не является рекурсией:

func f() { go f() }

Это не рекурсия. Рекурсия использует общий стек, а инструкци go создаёт новый стек. Это порождение параллельного потока, а не рекурсия.

Порождение горутины из горутины имеет смысл для алгоритмов навроде map-reduce. Горутина разбивает задание на части и порождает дочерние горутины для их обработки, затем собирает результаты и как-то их объединяет.

У вас последовательный алгоритм перебора последовательности. Его можно распараллелить, например, создав горутины, которые пишут каждая в своё место массива. Но там надо быть супер осторожным, чтобы гарантировать, что состояние консистентно (например, горутины не меняют уже завершенные последовательности) и что обновление полно (например, горутины не пропускают какие-то наборы чисел. Я сомневаюсь, что распараллеливание даст какой-то значимый выигрыш.

Вот (тупой) пример параллельного перебора: https://go.dev/play/p/6INx-iLL8kJ

type Task struct {
    Prefix []int
    MaxLen int
    MaxInt int
}

var printQueue chan []int = make(chan []int, 1024)

func printer(ctx context.Context) {
    for {
        select {
        case slice := <-printQueue:
            out(slice)
        case <-ctx.Done():
            return
        }
    }
}

func worker(t Task, wg *sync.WaitGroup) {
    defer wg.Done()
    if len(t.Prefix) >= t.MaxLen {
        // fmt.Println("DEBUG: worker: done")
        printQueue <- t.Prefix
        return
    }
    kidsWg := &sync.WaitGroup{}
    for i := 0; i < t.MaxInt; i++ {
        newPrefix := append(slices.Clone(t.Prefix), i)
        kidsWg.Add(1)
        go worker(
            Task{
                Prefix: newPrefix,
                MaxLen: t.MaxLen,
                MaxInt: t.MaxInt,
            },
            kidsWg,
        )
    }
    kidsWg.Wait()
}

Воркеры в рабочем цикле перебирают целые числа, прилепляют их к текущему массиву и передают детям для дальнейшей обработки. Когда длина последовательности достигла масимума, воркер отправляет последовательность на финальную обработку в принтер. Барьеры WaitGroup используются для того, чтобы узнать, когда работа над заданием закончена.

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

Можно задаться вопросом зачем нужна рекурсия через горутины. Горутины ускорят генерацию, но скорость ограничена скоростью вывода, не генерацией. Но к этому вернёмся позже.

Рекурсия через горутины

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

Печатается такая структура в два шага: цифры рекурсивно собираются в буфере strings.Builder задом на перёд, буфер переводится в строку и печатается.

Печатается он, как бы не так. Пакет fmt может смешивать строки если в него пишут одновременно несколько горутин. Надо делать синхронизацию. Я решил синхронизироваться через канал. Горутины search готовят строки на печать и помещают их в канал. Читает из канала одна горутина print и печатает их наружу. Канал обеспечивает синхронизацию в стиле CSP. Я пробовал вариант без канала и print, через sync.Mutex. Код проще и, к сожалению, медленнее.

Печать большого объёма требует буферизированного вывода. fmt буфер не поддерживает, что замедляет печать. Пакет bufio решает эту задачу.

Так как всё у нас на горутинах, то требуется дождаться окончания их работы. Для этого есть sync.WaitGroup. Их две: одна для горутин search. Когда группа завершает работу, я закрываю канал и жду окончания работы горутины print.

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
    "strings"
    "sync"
)

type Node struct {
    d    int
    next *Node
}

func toString(list *Node) string {
    var sb strings.Builder

    var toString func(list *Node)
    toString = func(list *Node) {
        if list != nil {
            sb.WriteString(strconv.Itoa(list.d))
            toString(list.next)
        }
    }

    toString(list)
    return sb.String()
}

func search(m, n int) {
    buffer := bufio.NewWriter(os.Stdout)
    defer buffer.Flush()

    stdout := make(chan string)

    var print_wg, search_wg sync.WaitGroup

    print := func(stdout <-chan string) {
        defer print_wg.Done()
        for s := range stdout {
            fmt.Fprintln(buffer, s)
        }
    }

    print_wg.Add(1)
    go print(stdout)

    var search func(m int, prefix *Node)
    search = func(n int, prefix *Node) {
        defer search_wg.Done()
        if n == 0 {
            stdout <- toString(prefix)
        } else {
            for i := 0; i <= m; i++ {
                search_wg.Add(1)
                go search(n-1, &Node{i, prefix})
            }
        }
    }

    search_wg.Add(1)
    go search(n, nil)

    search_wg.Wait()
    close(stdout)

    print_wg.Wait()
}

func main() {
    var m, n int
    fmt.Scan(&m, &n)

    search(m, n)
}

Миллион строк за две с половиной секунды:

$ time echo 9 6 | go run search.go | wc -l
1000000

real  0m2.404s
user  0m6.312s
sys   0m1.832s

Рекурсия без горутин

Вывод буферизирован, убрано всё форматирование – печатаются массивы байт:

package main

import (
    "bufio"
    "fmt"
    "os"
)

func main() {
    var m, n int
    fmt.Scan(&m, &n)

    buffer := bufio.NewWriter(os.Stdout)

    b := make([]byte, n+1)
    b[n] = '\n'

    var search func(i int)
    search = func(i int) {
        if i == n {
            buffer.Write(b)
        } else {
            for d := '0'; d <= '0'+rune(m); d++ {
                b[i] = byte(d)
                search(i + 1)
            }
        }
    }
    search(0)
    buffer.Flush()
}

Быстрее в двадцать раз:

$ time echo 9 6 | go run search.go | wc -l
1000000

real  0m0.114s
user  0m0.128s
sys   0m0.036s

$ time echo 9 8 | go run search.go | wc -l
100000000

real  0m1.668s
user  0m2.160s
sys   0m0.724s

$ time echo 9 9 | go run search.go | wc -l
1000000000

real  0m17.795s
user  0m24.612s
sys   0m7.008s

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