Схема для Python: самый элегантный перевод рекурсивной процедуры?

Question

Я недавно прочитал еще раз прекрасное введение в рекурсию в книге «просто схема» (вот ссылка на соответствующую главу), где вводится эта рекурсивная процедура (в схеме * 1004).* language):

(define (downup wd)
  (if (= (count wd) 1)
      (se wd)
      (se wd (downup (bl wd)) wd)))

> (downup 'toe)
(TOE TO T TO TOE)

> (downup 'banana)
(BANANA BANAN BANA BAN BA B BA BAN BANA BANAN BANANA)

Я пытался перевести эту процедуру на python , которую я использую в своей повседневной работе.Вот результат:

def recursivefun(word):
    if len(word) == 1: 
        return word
    else:
        x = []
        x.append(word)
        x.extend(recursivefun(word[1:]))
        x.append(word)
        return x

print recursivefun("ciao")
# ==> ['ciao', 'iao', 'ao', 'o', 'ao', 'iao', 'ciao']

Итак, мой вопрос: есть ли лучший способ представить эту рекурсивную процедуру в python?Или, может быть, более «элегантный» способ?

Answer 1

Если вы хотите точно представить исходную рекурсивную функцию Scheme:

def downup(word):
    if len(word) <= 1:
        return [word]
    return [word] + downup(s[1:]) + [word]

Обратите внимание, что ваша собственная функция возвращает строку, если длина переданной строки равна 1, и список в противном случае. Это может привести к удивительному поведению. Попробуйте

def recursivefun(word):
    if len(word) == 2:
        return word
    else:
        x = []
        x.append(word)
        x.extend(recursivefun(word[1:]))
        x.append(word)
        return x

print recursivefun("banana")

например, который печатает

['banana', 'anana', 'nana', 'ana', 'n', 'a', 'ana', 'nana', 'anana', 'banana']

, что может отличаться от того, что вы ожидали.

Answer 2

Refactored:

def recursivefun(word):
  if len(word) == 1: 
    return [word]
  else:
    return [word] + recursivefun(word[1:]) + [word]

Имейте в виду, что нам пришлось возвращать [слово] в первой ветви, потому что когда вы объединяете recursivefun () в строке 5, он ожидает список.

Answer 3

Это можно работать со строками вместо списков:

def downup(wd):
    if len(wd) == 1:
        return wd

    return ' '.join([wd, downup(wd[:-1]), wd])

print downup("TOE")
print downup("BANANA")

печать

TOE TO T TO TOE
BANANA BANAN BANA BAN BA B BA BAN BANA BANAN BANANA

Answer 4

И просто для сравнения это в понимании списка:

w ='BANANA'
print('('+' '.join(w[:n] for n in list(range(len(w)+1,1,-1)) + list(range(1,len(w)+1)))+')')

==>

(BANANA BANAN BANA BAN BA B BAN BANA BANAN BANANA)