Я не понимаю заданную функцию haskell пары Фибоначчи (кортежи) - PullRequest
Новая
       15

Я не понимаю заданную функцию haskell пары Фибоначчи (кортежи)

2 голосов
/ 17 мая 2011

Рекурсия - это то, что я всегда боролся с пониманием.Я надеюсь, что смогу получить некоторую помощь здесь о том, как работает эта функция.Это работает, но я хочу знать, как: 

fibStep :: (Int,Int) -> (Int,Int)
fibStep    (u,  v)    = (v,  u+v)

fibPair :: Int -> (Int,Int)
fibPair n
    | n==0      = (0,1)
    | otherwise = fibStep (fibPair (n-1))

Ответы [ 2 ]

3 голосов
/ 17 мая 2011

Как правило, когда вы делаете рекурсию, попробуйте работать в обратном направлении и с небольшими значениями, например, если мы передаем fibPair с n = 0, он немедленно возвращает (0,1).

Тогда, если n = 1, мы получим,

fibPair 1 = fibStep (fibPair 0) = fibStep (0, 1) = (1,1)

Тогда при n = 2 мы получим, 

fibPair 2 = fibStep (fibPair 1) = fibStep (1,1) = (1,2)

Итак, как мы видим, он дает вам n-ю пару последовательности Фибоначчи, подняв ее с (0, 1).

Если вы все еще не совсем понимаете это, попробуйте развернуть fibPair 2 полностью (т.е. развернуть fibStep (fibPair 1))

2 голосов
/ 17 мая 2011

Рекурсия работает очень похоже на цикл. С циклом у вас есть условие остановки, и то же самое верно для рекурсии, за исключением того, что это называется базовым случаем. В этом примере Фибоначчи базовый случай равен n==0, который возвращает кортеж (0,1) - и, конечно, это представляет первое число Фибоначчи.

После того, как вы установили базовый вариант, теперь вам нужно вычислить рекурсивный шаг - в этом примере это fibStep (fibPair (n-1)). Это эквивалентно блоку кода для цикла или тому, какой шаг повторяется на каждой итерации, пока не будет достигнут базовый случай. Естественно, очень важно убедиться, что вы всегда сходитесь к своему базовому случаю, иначе рекурсия никогда не закончится - и в этом примере рекурсивный шаг действительно сходится к базовому случаю, потому что для каждого последовательного шага значение n уменьшается на единицу, то есть мы должны в конечном итоге достичь случая, когда n==0 (при условии, что n изначально положительно).

Давайте посмотрим на оценку fibPair 3. Каждая последующая строка является расширением предыдущего с использованием определений, приведенных в примере. 

fibPair 3 **note: n is not 0 so we use the recursive step
fibStep (fibPair (3-1))
fibStep (fibPair 2) **note: n is not 0 use recursive step again
fibStep (fibStep (fibPair (2-1)))
fibStep (fibStep (fibPair 1)) **note: n is not 0 use recursive step again
fibStep (fibStep (fibStep (fibPair (1-1))))
fibStep (fibStep (fibStep (fibPair 0))) **note: n equals 0 so base case is used
                                        ** recursion has now ended
fibStep (fibStep (fibStep (0,1))) **note: now fibStep begins evaluation
fibStep (fibStep (1, 1))
fibStep (1, 2)
(2, 3)

Важно, что вам должно быть удобно с английским объяснением того, что происходит. fibStep принимает кортеж (fib number x, fib number x+1) и возвращает следующий кортеж в последовательности, а именно (fib number x+1, fib number x+2). fibPair действует как цикл по fibStep, заставляя fibStep вызываться n раз для одного и того же кортежа, что означает, что кортеж (fib number x, fib number x+1) будет иметь вид (fib number x+n, fib number x+n+1).

Надеюсь, это поможет немного прояснить ситуацию. Рекурсия действительно просто еще один способ написать цикл; он имеет все те же элементы, но написан немного по-другому. Для некоторых проблем использование рекурсии приводит к гораздо более простой логике, или коду, или к обоим. Как только вы освоитесь с рекурсией, это станет очень полезным инструментом для вашего будущего программирования.

...