Изучай Haskell ради Добра! Рекурсия | Participants
|
- Statistics
- Participants
- Translate into Russian
- Translation result
- Translated in draft, editing and proof-reading required. Completed: 8%.
If you do not want to register an account, you can sign in with OpenID.
Learn You a Haskell for Great Good! | ||
Recursion | ||
Hello recursion! | ||
We mention recursion briefly in the previous chapter. In this chapter, we'll take a closer look at recursion, why it's important to Haskell and how we can work out very concise and elegant solutions to problems by thinking recursively. | В предыдущей главе мы кратко затронули рекурсию. В этой главе мы изучим ее более подробно, узнаем почему она так важна для Хаскеля, и как мы можем создавать лаконичные и элегантные решения, думая рекурсивно. | |
If you still don't know what recursion is, read this sentence. Haha! Just kidding! Recursion is actually a way of defining functions in which the function is applied inside its own definition. Definitions in mathematics are often given recursively. For instance, the fibonacci sequence is defined recursively. First, we define the first two fibonacci numbers non-recursively. We say that F(0) = 0 and F(1) = 1, meaning that the 0th and 1st fibonacci numbers are 0 and 1, respectively. Then we say that for any other natural number, that fibonacci number is the sum of the previous two fibonacci numbers. So F(n) = F(n-1) + F(n-2). That way, F(3) is F(2) + F(1), which is (F(1) + F(0)) + F(1). Because we've now come down to only non-recursively defined fibonacci numbers, we can safely say that F(3) is 2. Having an element or two in a recursion definition defined non-recursively (like F(0) and F(1) here) is also called the edge condition and is important if you want your recursive function to terminate. If we hadn't defined F(0) and F(1) non recursively, you'd never get a solution any number because you'd reach 0 and then you'd go into negative numbers. All of a sudden, you'd be saying that F(-2000) is F(-2001) + F(-2002) and there still wouldn't be an end in sight! | Если вы все еще не знаете, что такое рекурсия, прочтите это предложение еще раз. Шучу! На самом деле, рекурсия - это способ определять функции таким образом, что функция применяется в собственном определении. Многие понятия в математике даются рекурсивно. Например, последовательность Фибоначчи. Мы определяем первые два числа Фибоначчи нерекурсивно. Положим F(0) = 0 и F(1) = 1, это означает что нулевое и первое число из ряда Фибоначчи - это ноль и единица. Затем мы определим, что для любого натурального числа, число Фибоначчи - это сумма двух предыдущих чисел Фибоначчи. Таким образом, F(n) = F(n-1) + F(n-2). Получается, что F(3) это F(2) + F(1), что в свою очередь дает (F(1) + F(0)) + F(1). Так как мы достигли чисел Фибоначчи, заданных нерекурсивно, мы можем точно сказать, что F(3) равно двум. Если в определении рекурсии у нас есть один или несколько элементов, задаваемых нерекурсивно (F(0) и F(1) в нашем случае), это называется граничными условиями. Граничные условия очень важны, если вы хотите чтобы ваша функция рано или поздно вычислилась. Если бы мы не определили F(0) и F(1) нерекурсивно, мы бы не получили результата, т.к. мы бы достигли нуля и продолжили вычисления с отрицательными числами. В некоторый момент, например, мы бы вычисляли F(-2000) как F(-2001) + F(-2002), и так продолжалось бы бесконечно! | |
Recursion is important to Haskell because unlike imperative languages, you do computations in Haskell by declaring what something is instead of declaring how you get it. That's why there are no while loops or for loops in Haskell and instead we many times have to use recursion to declare what something is. | Рекурсия важна для Хаскеля, потому что в отличие от императивных языков, вы выполняете вычисления в Хаскеле, описывая некоторое понятие, а не указывая как его получить. Вот почему в языке нет циклов while и for, вместо этого мы зачастую должны использовать рекурсию, чтобы описать, что собой представляет та или иная сущность. | |
Maximum awesome | ||
The maximum function takes a list of things that can be ordered (e.g. instances of the Ord typeclass) and returns the biggest of them. Think about how you'd implement that in an imperative fashion. You'd probably set up a variable to hold the maximum value so far and then you'd loop through the elements of a list and if an element is bigger than then the current maximum value, you'd replace it with that element. The maximum value that remains at the end is the result. Whew! That's quite a lot of words to describe such a simple algorithm! | Функция maximum принимает список упорядочиваемых элементов (т.е. экземпляров класса типов Ord) и возвращает максимальный элемент. Подумайте, как бы вы реализовали эту функцию в императивном стиле. Вероятно, вы бы завели переменную для хранения текущего значения максимального элемента и затем в цикле вы бы проверяли элементы списка. Если элемент больше чем текущее максимальное значение, вы бы замещали его новым значением. То, что осталось в переменной после завершения цикла и есть максимальный элемент. Ух! Довольно много слов потребовалось, чтобы описать такой простой алгоритм! |
© Miran Lipovača. License: creative commons attribution noncommercial blah blah blah ... license
— А нельзя ли назвать граничные условия - базовым случаем? — artobstrel95
Кстати, в учебнике Рогановой всюду "базовый случай" — artobstrel95
More 3 comments
— Чего ж нельзя, можно и не так назвать. Но не стоит. — asinitsyn
— Предлагаю "условия окончания", окончание - смысл edge, в данном случае. — lazil
— Граничные условия - прижившийся термин, кроме того это буквально "edge conditions" — asinitsyn
— Сейчас клево ) — lazil