Написание рекуррентных отношений / перечисление EBS
В наборе задач моего курса по структуре данных я столкнулся с вопросом, что я не уверен, как действовать в варианте b. Может кто-нибудь помочь мне найти путь, чтобы решить б?
Набор чрезвычайно скучных строк (EBS) строится с использованием символов a и b с помощью рекурсивной процедуры ниже:
ОСНОВА: Строка А является EBS
ВВЕДЕНИЕ: Если X является EBS, то и сцепленные строки Xb и Xaa. Например, ab и aaa - это две EBS, которые могут быть сгенерированы из базовой строки a с использованием шага индукции один раз.
а) Перечислите все EBS длины 4.
б) Напишите рекурсию для E(n), количество EBS длины n. Пожалуйста, будьте очень осторожны с основанием (ями).
НЕ пытайтесь точно решить повторение, но изложите его в терминах другой функции, о которой вы уже должны знать.