Как отсортировать мой список строк с помощью рекурсии? - PullRequest
Новая
       12

Как отсортировать мой список строк с помощью рекурсии?

0 голосов
/ 23 июня 2019

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

Как мне поступить? 

(define (create-list n st)
  (cond [(zero? n) ""]
        [else (string-append "X" (create-list (sub1 n)  st))]))

(define (stair n)
   (cond [(equal? n 0) empty]
              [else (cons (create-list n "x") (stair (- n 1)))]))

;; (stair 4) --> (list "XXXX" "XXX" "XX" "X")

Желаемый результат: (list "X" "XX" "XXX" "XXXX")

Ответы [ 2 ]

1 голос
/ 28 июня 2019

Все списки схем создаются от начала до конца.Сначала вы хотите создать ("XXXX"), затем ("XXX" "XXXX") и т. Д. Всякий раз, когда вы делаете (cons "X" (recursion ....)), тогда (recursion ...) необходимо закончить до cons, тогда как наиболее эффективным является использование аккумулятора.При использовании append каждый шаг пахнет неправильно, поскольку append - это O (n), поэтому, если вы делаете это на каждом шаге, то у вас есть O (n ^ 2).С парой тысяч элементов вы начнете замечать разницу.

Вам не нужен create-list, который создает не список, а строку, поскольку в Scheme есть make-string, который делает то, что вы хотите: 

(make-string 3 #\X) ; ==> "XXX"

Итак, вотлестница: 

(define (stair n)
  (define (xs n)
    (make-string n #\X))
  (let helper ((n n) (acc '()))
    (if (zero? n)
        acc
        (helper (- n 1) 
                (cons (xs n) acc)))))

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

1 голос
/ 23 июня 2019

Заменить 

(cons (create-list n "x") (stair (- n 1)))

с 

(append (stair (- n 1)) (list (create-list n "Q")))

(Обратите внимание, что create-list на самом деле не использует аргумент st.)

...