Рекурсию будем делать по нажатым кнопкам.
Т.е. на вход нам будет приходить:
1. набор нажатых кнопок: он и порядковый номер дадут понимание о положении в рекурсии
2. порядковый номер кнопки, который обрабатываем, её мы и будем двигать в рекурсии
3. строку, которую будем пополнять. В ней мы будем хранить текущую последовательность.

Базовый случай рекурсии ты правильно подметил: длина комбинации кнопок равна длине строки.
В этом случае печатаем результат и выходим из цикла

А вот рекурсивный -- чуть сложнее.
Надо для всех букв текущей кнопки вызвать рекурсию в цикле по следующей кнопке, добавив в строку букву из текущей итерации цикла