Я пытаюсь понять рекурсию в Схеме, и мне трудно выполнить пробный прогон, например, простую задачу с числами Фибоначчи.
Может ли кто-нибудь разбить шаги, на которых происходят дополнения, для меня?
(define (fib n)
(if (<= n 2)
1
(+ (fib (- n 1)) (fib (- n 2)))))
Если вы используете Racket, как указано в ваших тегах, у вас есть встроенный степпер.
Введите программу в DrRacket и нажмите Step в правом верхнем меню:
Затем откроется шаговое окно. Нажимайте Step снова и снова, и вы сможете пройтись по выполнению программы.
Если вы хотите, чтобы количество шагов было немного более управляемым, выберите число меньше 10 для отслеживания выполнения.
В псевдокоде fib(n) = n <= 2 -> 1 ; else -> fib(n-1) + fib(n-2) => (1 1 2 3 5 ...).
Например, fib(5) сокращается как:
fib(5)
fib(4) + fib(3)
(fib(3) + fib(2)) + fib(3)
((fib(2) + fib(1)) + fib(2)) + fib(3)
((1 + 1) + fib(2)) + fib(3)
(2 + fib(2)) + fib(3)
(2 + 1) + fib(3)
3 + fib(3)
3 + (fib(2) + fib(1))
3 + (1 + 1)
3 + 2
5
Это код, который печатает члены последовательности Фибоначчи от 1 до n каждый в новой строке. Важно отметить, что он использует две очень простые вспомогательные функции. Надеюсь это поможет.
;Prints to the screen all the member up to the nth member in the fibonaci sequence (define (fibo n)
(let ((i 1))
(if (= n 1)
(display 1)
(fiboHelp i n))))
;Helper function that presents Fibonaci sequence from bottom index i until upper index n
(define (fiboHelp i n)
(if (= i n)
(display(fiboMember i))
(begin
(display (fiboMember i))
(newline)
(fiboHelp (+ i 1)n))))
;Returns the nth member of the Fibonaci sequence
(define (fiboMember n)
(if (<= n 2)
(+ 1 0)
(+ (fiboMember(- n 1))(fiboMember(- n 2)))))
