Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > LISP > мини рекурсия

Автор: Lion69 2.10.2009, 17:25

нужно сделать через рекурсию использую базовые ф-ции такую вещь
из (a b c d ) на входе должно получится ((((a)b)c)d) на выходе....
я сделал такое

Код


(defun fak(bla)
    (cond((null  (cdr bla))bla )(t
        (cons (fak(cdr bla)) (cons (car bla)nil))
        )
    )
)

но оно  выдает список наоборот...
> (fak '(5 2 4 86 1 2 ))
((((((2) 1) 86) 4) 2) 5)
мне не нужна прям готовая ф-я.. мне нужна подсказка.....
как делать и самое главно с чего начать...

Автор: Ryukzak 2.10.2009, 20:12

Рекурсия позволяет собирать структуры от внутренних к внешним. Так что придётся либо развернуть список, либо реализовать его хвостовой рекурсией.

Автор: Lion69 2.10.2009, 20:16

как развернуть список я не знаю... это всмысле реверс или как? в таком случае как его сделать в рекурсии...?

Цитата

реализовать его хвостовой рекурсией.

Код


(cons (fak(cdr bla))

я думал это и есть хвостовая рекурчия.......
ЗЫ.. я меньше месяча лисп учу... так что извеняйте за может быть глупые вопросы

Добавлено через 5 минут и 3 секунды
я кстате над этой прогой уже второй день бьюсь... хотел бы уже начать что то еще делать ... но не могу..... дошло до того что аж сюда на форум обратился..... не могу понять что тут делать....

Автор: Void 2.10.2009, 20:35

Стандартный приём функционального программирования — протаскивать через цепочку рекурсивных вызовов значение-аккумулятор.

Код


(defun foo (acc s)
    (if (null s)
        acc
        (foo (list acc (car s)) (cdr s))))

Цитата

> (foo '(a) '(b c d))
((((A) B) C) D)

Как обернуть эту функцию, чтобы список был единственным параметром, думаю, понятно.

Автор: Lion69 2.10.2009, 20:51

Void, извини но не понятно.....как сделать это для одного списка? типа (a b c d)???
и еще мне я не знаю что такое IF.... это типа такая запись терминальной ветви.....?(я ведь говорил что новичок...) если не сложно то помоги... а то что то по истечиние двух дней игр с этой задачей что то вообще соображать перестал...

Автор: Void 2.10.2009, 21:18

Цитата(Lion69 @ 2.10.2009, 22:51

)

как сделать это для одного списка?

Сделать из головы (car) список из одного элемента и передать как первый параметр (аккумулятор), хвост передать как второй.

Код

(defun bar (s)
    (foo (list (car s)) (cdr s)))

Для порядка можно функции сделать вложенными:

Код

(defun quux (lst)
    (labels (
        (inner (acc s)
            (if (null s)
                acc
                (inner (list acc (car s)) (cdr s)))))
        (inner (list (car lst)) (cdr lst))))

Но на данном этапе, наверное, не стоит заморачиваться.

Цитата(Lion69 @ 2.10.2009, 22:51

)

не знаю что такое IF

Условный оператор, однако. (if условие если-истина если-ложь).

Автор: Lion69 3.10.2009, 00:14

Void, спасибо... правда я плохо понимаю как оно дейтвует... все таки я привык к терминальной ветви а за ней должна идти сама рекурсия... ну ладно это такое.... еще раз спасибо....
да... нащет ифа... я просто не понил что этот условний оператор делает... имено в этом примере... а не вообще... не нужно меня причислять к слабоумным...)))

Автор: Void 3.10.2009, 11:54

Цитата(Lion69 @ 3.10.2009, 02:14

)

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

Ну и в чём проблема?

Код

(inner (acc s)
    (if (null s)
        acc  ;;; терминальная ветвь — просто возвращаем значение acc
        (inner (list acc (car s)) (cdr s))))) ;;; рекурсивный вызов

Цитата(Lion69 @ 3.10.2009, 02:14

)

да... нащет ифа... я просто не понил что этот условний оператор делает... имено в этом примере... а не вообще... не нужно меня причислять к слабоумным...)))

Ну извиняюсь, вопрос

Цитата(Lion69 @ 2.10.2009, 22:51

)

я не знаю что такое IF

неоднозначных толкований вроде не допускает, так что я ответил на него smile

Автор: Lion69 3.10.2009, 12:06

Автор: _sg 25.4.2014, 10:00

как вариант:

Код


(defun annex (w)
  (reduce #'list (cons (list (car w)) (cdr w))))
 
> (annex '(a b c d e))
(((((A) B) C) D) E)