rekurencja w lisp

0

Dzien dobry czy ktos moglby to zrobic w jezyku lisp ?

Dana jest rekursywna definicja funkcji Fun(x,y), gdzie SUCC(y)= y+1.

Fun(0,y)=y+2,
Fun(x+1,y)= SUCC(Fun(x, SUCC(y)))

Znajdź: Fun(1,4); Fun(3,2);

1

A co juz napisales?

1
stivens napisał(a):

A co juz napisales?

Tak to treść zadania

2

XD

Zapytalem o wklad wlasny. Pokaz co napisales i czego nie rozumiesz - pomozemy

Jak nie zaczales to moze: https://learnxinyminutes.com/docs/racket/

0
stivens napisał(a):

XD

Zapytalem o wklad wlasny. Pokaz co napisales i czego nie rozumiesz - pomozemy

Jak nie zaczales to moze: https://learnxinyminutes.com/docs/racket/

wlasnie cos takiego zrobilem ale oczywiscie nie dziala to

(defun Fun (x y)
(if (= x 0) (+ y 2)
(if (Fun(+ x 1) (incf y))
)))

0

To moze pseudokod

if x == 0:
    return y+2
else:
    return fun(x-1,y+1)+1
4

screenshot-20190825165935.png


sorry Racket to jedyny Lisp w jakim pisalem wiec bedziesz musial sobie przetlumaczyc swojego dialektu :P

2

Proszę, bez większego problemu powinieneś to przetłumaczyć na dowolnego lispa-1:

((λ (func)
    (printf "fun(1, 4) := ~s\n" (func 1 4))
    (printf "fun(3, 2) := ~s\n" (func 3 2)))
 ((λ (succ Y) (Y (λ (f) (λ (x y) (if (= 0 x)
                                     (+ y 2)
                                     (succ (f (- x 1) (succ y))))))))
  (λ (y) (+ y 1))
  (λ (b) ((λ (f) (b (λ (x y) ((f f) x y))))
             (λ (f) (b (λ (x y) ((f f) x y))))))))
0

Po pierwsze oducz się tego "nie działa", konkrety: nie kompiluje się, wywala się czy co? Może zwraca Nil? Niestety nie mam pod ręką kompilatora, ale na pierwszy rzut oka, problemem jest ten drugi if. Operator if przykuje trzy parametry: warunek jesli-tak jeśli-nie. Jeśli ostatni nie jest podany zwróci Nil, jeśli warunek nie jest spełniony. Wobec tego, u ciebie najpierw jest sprawdzany właściwy warunek, jeśli spełniony, zwraca y+2, a jeśli nie... Zamiast po prostu zwrócić wartość, umieszczasz ja jako warunek dla kolejnego ifa bez kolejnych parametrów. To chyba się nie skompiluje... ?

Poza tym x+1 masz we wzorcu funkcji, tak więc w implementacji musisz odwrócić znak :)

Będzie jakoś tak:

(defun Fun (x y)
    (if (= x 0) (+ y 2)
       (+ (Fun (- x 1) (+ y 1)) 1)))

Zmieniłem też brzydkie incf. W tym miejscu jest bezzasadne (niepotrzebny skutek uboczny). Zmiennego stanu używaj tylko jeśli wiesz co robisz. To jest bagno.
Edit: zabrakło jeszcze +1

1 użytkowników online, w tym zalogowanych: 0, gości: 1