Jak zrozumieć ten kod rekurencyjny?

Znalazłem ten kod w podręczniku An Introduction to Programming in Emacs Lispdemonstrującym rekurencję za pomocą condfunkcji, aby dowiedzieć się o liczbie kamyków na podstawie wprowadzonej liczby wierszy, tj. Jeśli rzędy = 2, to kamyki powinny mieć 3, jeśli 4 rzędy, to powinno być 10 kamyków tam.

(defun triangle-using-cond (number)
  (cond ((<= number 0) 0)
        ((= number 1) 1)
        ((> number 1)
         (+ number (triangle-using-cond (1- number))))))

ocenić do 10 po przekazaniu argumentu 4:

(triangle-using-cond 4)

Podręcznik nie wyjaśnił jasno, co dzieje się na każdym etapie tego przykładowego kodu, a ja nie mogłem zrozumieć, jak działa rekurencja. Czy możesz mi pomóc krok po kroku zrozumieć mechanikę, co dzieje się w każdej instancji?

Korzystanie z „debugowania printf”

Możesz pozwolić Emacsowi pomóc w zrozumieniu, modyfikując definicję funkcji:

(defun triangle-using-cond (number)
  (message (format "called with %d" number))
  (cond ((<= number 0) 0)
        ((= number 1) 1)
        ((> number 1)
         (+ number (triangle-using-cond (1- number))))))

Po prostu dodaj (message ...)gdzieś, aby wydrukować ślad do *Messages*bufora.

Korzystanie z Edebug

Umieść punkt w dowolnym miejscu definicji funkcji i wciśnij, C-u C-M-xaby ją „instrumentować”. Następnie oceń funkcję, np. Umieszczając punkt po (triangle-using-cond 3)i naciskając C-x C-e.

Jesteś teraz w trybie Edebug. Naciśnij spację, aby przejść przez funkcję. Wartości pośrednie każdego wyrażenia są pokazane w obszarze echa. Aby wyjść z trybu Edebug, wystarczy nacisnąć q. Aby usunąć oprzyrządowanie, umieść punkt w dowolnym miejscu definicji i naciśnij, C-M-xaby ponownie ocenić definicję.

Korzystanie ze standardowego debugera Emacs

M-x debug-on-entry triangle-using-cond, po triangle-using-conduruchomieniu zostanie umieszczony w debuggerze Emacsa (buforze *Backtrace*).

Przejdź przez ewaluację, używając d(lub cpomiń wszelkie nieciekawe oceny).

Aby zobaczyć stan pośredni (wartości zmiennych itp.), Możesz użyć w edowolnym momencie. Zostaniesz poproszony o wprowadzenie sexp w celu oceny, a wynik oceny zostanie wydrukowany.

Podczas korzystania z debugera trzymaj kopię kodu źródłowego widoczną w innej ramce, abyś mógł śledzić, co się dzieje.

Możesz także wstawić jawne wywołania, aby wprowadzić debugger (mniej lub bardziej punkty przerwania) w dowolnych miejscach w kodzie źródłowym. Wstawiasz (debug)lub (debug nil SOME-SEXP-TO-EVALUATE). W tym drugim przypadku, po wprowadzeniu debuggera SOME-SEXP-TO-EVALUATEjest oceniany i wynik jest drukowany. (Pamiętaj, że możesz wstawić taki kod do kodu źródłowego i użyć go C-M-xdo oceny, a następnie cofnąć - nie musisz zapisywać edytowanego pliku).

Aby Using Debuggeruzyskać więcej informacji, zobacz instrukcję Elisp, węzeł .

Rekurencja jako pętla

W każdym razie pomyśl o rekurencji jako o pętli. Zdefiniowano dwa przypadki zakończenia: (<= number 0)i (= number 1). W takich przypadkach funkcja zwraca liczbę prostą.

W przypadku rekurencyjnym funkcja zwraca sumę tej liczby i wynik funkcji za pomocą number - 1. Ostatecznie funkcja zostanie wywołana z 1liczbą lub liczbą mniejszą lub równą zero.

Wynik przypadku rekurencyjnego jest zatem następujący:

(+ number (+ (1- number) (+ (1- (1- number)) ... 1)

Weźmy na przykład (triangle-using-cond 4). Skumulujmy końcowe wyrażenie:

• w pierwszej iteracji numberjest 4, więc (> number 1)gałąź jest śledzona. Zaczynamy budować wyrażenie (+ 4 ...i wywołujemy funkcję za pomocą (1- 4), tj (triangle-using-cond 3).

• teraz numberjest 3, a wynik jest (+ 3 (triangle-using-cond 2)). Łączne wyrażenie wyniku to (+ 4 (+ 3 (triangle-using-cond 2))).

• numberjest 2teraz, więc wyrażenie jest(+ 4 (+ 3 (+ 2 (triangle-using-cond 1))))

• numberjest 1teraz i bierzemy (= number 1)gałąź, co powoduje nudę 1. Całe wyrażenie brzmi (+ 4 (+ 3 (+ 2 1))). Ocenia, że od wewnątrz na zewnątrz i masz: (+ 4 (+ 3 3)), (+ 4 6)lub po prostu 10.

Model zastępowania aplikacji procedury z SICP może objaśnić algorytm tak, aby rozumiał taki kod.

Napisałem również kod, aby to ułatwić. robi to lispy-flattenz pakietu lispy . Oto wynik zastosowania lispy-flattendo (triangle-using-cond 4):

(cond ((<= 4 0)
       0)
      ((= 4 1)
       1)
      ((> 4 1)
       (+ 4 (triangle-using-cond (1- 4)))))

Możesz uprościć powyższe wyrażenie do:

(+ 4 (triangle-using-cond 3))

Następnie spłaszcz jeszcze raz:

(+ 4 (cond ((<= 3 0)
            0)
           ((= 3 1)
            1)
           ((> 3 1)
            (+ 3 (triangle-using-cond (1- 3))))))

Wynik końcowy:

(+ 4 (+ 3 (+ 2 1)))

Nie jest to specyficzne dla Emacsa / Elisp, ale jeśli masz doświadczenie matematyczne, rekurencja jest jak indukcja matematyczna . (Lub jeśli nie: to kiedy uczysz się indukcji, jest to jak rekurencja!)

Zacznijmy od definicji:

(defun triangle-using-cond (number)
  (cond ((<= number 0) 0)
        ((= number 1) 1)
        ((> number 1)
         (+ number (triangle-using-cond (1- number))))))

Kiedy numberjest 4, żaden z dwóch pierwszych warunków nie jest uwzględniany, więc jest on oceniany zgodnie z trzecim warunkiem:
(triangle-using-cond 4)jest oceniany jako
(+ number (triangle-using-cond (1- number))), a mianowicie jako
(+ 4 (triangle-using-cond 3)).

Podobnie
(triangle-using-cond 3)jest oceniany jako
(+ 3 (triangle-using-cond 2)).

Podobnie (triangle-using-cond 2)jest oceniany jako
(+ 2 (triangle-using-cond 1)).

Ale dla (triangle-using-cond 1)drugiego warunku obowiązuje i jest on oceniany jako 1.

Porada dla każdego, kto uczy się rekurencji: staraj się unikać

powszechny błąd początkującego, polegający na próbowaniu myślenia o tym, co dzieje się podczas wezwania rekurencyjnego, zamiast ufaniu, że zadzwoni rekurencyjne (czasami nazywany rekurencyjnym skokiem wiary).

Jeśli próbujesz przekonać się, czy (triangle-using-cond 4)zwróci prawidłową odpowiedź, po prostu załóż, że (triangle-using-cond 3)zwróci właściwą odpowiedź, i sprawdź, czy w takim przypadku będzie poprawna. Oczywiście musisz również zweryfikować skrzynkę podstawową.

Kroki obliczeniowe dla Twojego przykładu wyglądałyby następująco:

(4 +               ;; step 1
   (3 +            ;; step 2
      (2 +         ;; step 3
         (1))))    ;; step 4
=> 10

Warunek 0 w rzeczywistości nigdy nie jest spełniony, ponieważ 1 jako wejście już kończy rekurencję.

Myślę, że jest to dość łatwe, nie potrzebujesz emacs lisp pod tym, to tylko matematyka w szkole podstawowej.

f (0) = 0

f (1) = 1

f (n) = f (n-1) + n, gdy n> 1

więc f (5) = 5 + f (4) = 5 + 4 + f (3) = 5 + 4 + 3 + 2 + 1 + 0

Teraz to oczywiste.