Рекурсивная генерация списка списков в треугольном формате с учетом высоты и значения

Question

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

В настоящее время я пытаюсь сгенерировать двумерный массив, которыйтеоретически должен напоминать своего рода прямоугольный треугольник в формации NxN с некоторой высотой n и значением, которое будет возвращено в 2D-массив.

В качестве примера, скажем, я называю: my_function(3, 'a');,n = 3 и value = 'a'

Мой результат должен быть таким: [['a'], ['a', 'a'], ['a', 'a', 'a']]

[['a'], 
 ['a', 'a'], 
 ['a', 'a', 'a']]

Где n определяет, сколько списков будет в самом внешнем списке, а такжесколько элементов должно последовательно появляться в этих внутренних списках в порядке возрастания.

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

def my_function(n, value):
    base_val = [value]
    if n == 0:
        return [base_val]
    else:
        return [base_val] + [my_function(n-1, value)]

К сожалению, используя мой приведенный выше пример n = 3и value = 'a', это в настоящее время выводит: [['a'], [['a'], [['a'], [['a']]]]]

Теперь, это не должно быть отформатировано или напечатано так, как я показал выше в буквальном формате прямоугольного треугольника. (это была просто визуализация того, чего я хочу достичь).

Я, конечно, отвечу на любые уточняющие вопросы, которые вам нужны!

Answer 1

return [base_val]

Хорошо, для n == 0 мы получаем [[value]]. Твердое вещество. Э, вроде. Это результат с одной строкой, верно? Итак, наше условие для базового случая должно быть n == 1.

Теперь давайте попробуем рекурсивный случай:

return [base_val] + [my_function(n-1, value)]

У нас было [[value]], и мы хотим закончитьс [[value], [value, value]]. Точно так же, когда у нас есть [[value], [value, value]], мы хотим получить из него [[value], [value, value], [value, value, value]]. И так далее.

План состоит в том, чтобы в настоящий момент мы получили одну строку, а все остальные строки - путем повторения, да?

1. Какие строки мы будемполучить с помощью рекурсии? Ответ: те, что в начинаются , потому что это те, которые все еще выглядят изолированно как треугольник.

2. Следовательно, какую строку мы производим локально? Ответ: один на конце .

3. Следовательно, как мы упорядочиваем результаты? Ответ: нам нужно получить результат от рекурсивного вызова и добавить в его конец строку.

4. Нужно ли нам обернуть результат рекурсивного вызова? Ответ: Нет. Это уже список списков. Мы просто добавим еще один список в его конец.

5. Как создать последний ряд? Ответ: нам нужно повторить value, n раз в списке. Ну, это достаточно просто.

6. Нужно ли нам оборачивать локальный ряд? Ответ: Да, потому что мы хотим добавить его как отдельный элемент к рекурсивному результату, а не объединять все его элементы.

Хорошо, давайте пересмотрим базовый случай. Можем ли правильно обработать n == 0? Да, и это имеет смысл как запрос, поэтому мы должны его обработать. Как выглядит наш треугольник без рядов? Ну, это все еще список строк, но в нем нет строк. Так что это просто []. И мы все еще можем добавить к этому первый ряд и продолжить рекурсивно. Отлично.

Давайте сложим все вместе:

if n == 0:
    return []
else:
    return my_function(n-1, value) + [[value] * n]

Похоже, base_val больше не является полезным. О, хорошо.

Мы можем сжать это немного дальше, используя троичное выражение:

return [] if n == 0 else (my_function(n-1, value) + [[value] * n])

Answer 2

Мне проще всего думать о рекурсивных алгоритмах в терминах базового случая и того, как на этом основываться.

Базовый случай (случай, когда рекурсия не нужна) - это когда n = 1 (или n = 0, но я собираюсь игнорировать этот случай). «Треугольник» 1x1 - это просто список 1x1: [[a]].

Итак, как мы можем основываться на этом? Хорошо, если n = 2, мы можем предположить, что у нас уже есть это базовое значение (из вызова f (1)) из [[a]]. Поэтому нам нужно добавить [a, a] в этот список.

Мы можем обобщить это как:

f(1)     = [[a]]
f(n > 1) = f(n - 1) + [[a] * n]

, или, в Python:

def my_function(n, value):
    if n == 1:
        return [[value]]
    else:
        return my_function(n - 1, value) + [[value] * n]

Answer 3

В то время как другие ответы предлагали другой алгоритм решения вашей проблемы, его можно было бы решить, исправив ваше решение:

Используя вспомогательную функцию, такую ​​как:

def indent(x, lst):
    new_lst = []
    for val in lst:
        new_lst += [x] + val
    return new_lst

Вы можете реализоватьвозвращение в исходную функцию в виде:

return [base_val] + indent(value, [my_function(n-1, value)])

Другие решения более элегантны, поэтому не стесняйтесь их принимать.

---

Вот изображение, объясняющее это решение.

Красная часть - это текущий вызов функции, а зеленая - предыдущий вызов функции.

Как видите, нам также нужнодобавить желтую часть, чтобы завершить треугольник.

---

Это другие решения.

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

Answer 4

У вас есть пара логических ошибок: off-by-1 с n, увеличивая неправильную сторону (критически, неосновная реализация не должна использовать массив базового размера), увеличиваясь массивом неправильного размера,Исправленная версия:

#!/usr/bin/env python3


def my_function(n, value):
    if n <= 0:
        return []
    return my_function(n-1, value) + [[value]*n]


def main():
    print(my_function(3, 'a'))


if __name__ == '__main__':
    main()

Поскольку вы возвращаете mutable, вы можете добиться большей эффективности, используя .append вместо +, что сделает его более неработоспособным. Также обратите внимание, что внутренние изменяемые объекты не копируются (но поскольку рекурсия внутренняя, в данном случае это не имеет значения).

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

Но python - странный язык для использования ненужной рекурсии.