Shulou(Shulou.com)06/02 Report--

This article mainly explains "how to use Scala language". The content of the explanation is simple and clear, and it is easy to learn and understand. Please follow the editor's train of thought to study and learn "how to use Scala language".

Why is recursion ignored?

In order to answer this question, we must first talk about the programming paradigm. Of all the programming paradigms, object-oriented programming (Object-Oriented Programming) is undoubtedly the winner. Take a look at the online job postings, without exception, candidates will be required to be proficient in object-oriented programming. But in fact, object-oriented programming is not a programming paradigm in a strict sense, which can be divided into imperative programming (Imperative Programming), functional programming (Functional Programming) and logical programming (Logic Programming). Object-oriented programming is only a cross product of the above paradigms, and more of it inherits the genes of imperative programming. Unfortunately, in the long-term teaching process, only imperative programming is emphasized, that is, programmers tell the computer what to do, not what to do. Recursion tells the computer what to do through clever function definitions. Therefore, in the programs that use imperative programming, we have to say that this is the programming method adopted by most programs now, and the probability of recursive mirrors is very small, while in functional programming, we can see recursive methods everywhere. Next, we will use an example to show you how recursion can solve programming problems as a common way.

A set of simple examples

How to sum a set of integers? According to the usual imperative programming, we will use a loop, iterate through each element in the list and add up, and finally give the sum result. Such a program is not difficult to write, and people with a little programming experience can write it in less than a minute. This time we change our thinking, how to use the recursive way to seek peace? For this reason, we might as well simplify the problem a little bit, assuming that the sequence contains N numbers, and if we already know the sum of the subsequent N-1 numbers, then the sum of the whole sequence is the sum of the following N-1 numbers, and so on, we can continue to sum the N-1 numbers in the same way until the number column is empty, obviously, the sum of the empty series is zero. It sounds complicated, but in fact we can sum it up in one sentence: the sum of a sequence is the sum of the number of numbers in the sequence plus the sum of the series made up of subsequent numbers. Now, let's express this idea in Scala.

Listing 1. Sequence summation

/ / xs.head returns the header element in the list, that is, * elements / / xs.tail returns a list of the remaining elements except the header element def sum (xs: List [Int]): Int = if (xs.isEmpty) 0 else xs.head + sum (xs.tail)

As you can see, we use only one-line program to express the above summation method, and this line of program looks simple and easy to understand. Writing as little code as possible is one of the design philosophies of the Scala language. Less code means it is easier to write, easier to read, and less likely to make contemporary code errors. For the same program, the amount of code written in Scala is usually half or more than that of Java.

The above example of summation of a series is not special. It represents a common way of dealing with a list recursively, that is, the operation on a list can be transformed into the same operation on * elements and the rest of the list. For example, we can find the * value in a series in the same way. We assume that we already know the * * values of the remaining series except * elements, then the * values of the whole series are the larger of the * elements and the remaining series * * values. It is important to note that there is no point in finding a * value for an empty sequence, so we need to throw an exception. When the sequence contains only one element, the * value is the body of that element, which is the boundary condition of our recursion. A recursive algorithm must have such a boundary condition, otherwise it will be recursive all the time, forming an endless loop.

Listing 2. Find the value of *

Def max (xs: List [Int]): Int = {if (xs.isEmpty) throw new java.util.NoSuchElementException if (xs.size = = 1) xs.head else if (xs.head > max (xs.tail)) xs.head else max (xs.tail)} v

In the same way, we can also find the minimum value in a series, and as an exercise, the reader can go down and implement it by himself.

Let's look at another example: how to reverse a string? For example, given a string "abcd", it becomes "dcba" after being reversed. Similarly, we can make a bold assumption that the subsequent string has been reversed, then the whole string will be reversed by adding * characters. For a string with only one character, there is no need for inversion, which is the boundary condition of our recursive algorithm. The program is implemented as follows:

Listing 3. Reverse string

Def reverse (xs: String): String = if (xs.length = = 1) xs else reverse (xs.tail) + xs.head

* one example is the classic quick sort, which readers may think is not simple, but we will see that using recursion, coupled with the concise language features of Scala, we only need a few lines of programs to implement the quick sort algorithm. The core idea of the quick sorting algorithm is to select a value in an unordered list and divide the list into two parts according to the value, with the smaller part at the front and the larger part at the back. Each of these two parts is sorted in the same way until they are empty. Obviously, we think that an empty list is a sorted list, which is the boundary condition in this algorithm. For convenience, we select * elements as values that divide the list into two parts. The program is implemented as follows:

Listing 4. Quick sort

Def quickSort (xs: List [Int]): List [Int] = {if (xs.isEmpty) xs else quickSort (xs.filter (x = > xx > xs.head))}

Of course, to make the program more concise, the author uses some of the methods in the list here: add an element to the list, join two lists, and filter a list, and use lambda expressions in it. But all these make the program more in line with the core idea of the algorithm and easier to read.

Tail recursion

As we can see from the above example, programs written using recursion are usually easy to understand, which actually represents the difference between the two programming paradigms. Imperative programming paradigms tend to use loops to tell computers what to do, while functional programming paradigms use recursion to tell computers what to do. Programmers accustomed to the imperative programming paradigm have another worry: isn't recursion an efficiency problem compared to loops? Each recursive call will assign a new function stack, if the recursive nesting is very deep, it is easy to overflow the stack. For example, the following recursive program for calculating factorials:

Listing 5. Recursive factorial

Def factorial (n: Int): Int = if (n = 0) 1 else n * factorial (n-1)

When the factorial of n-1 is called recursively, a new function stack must be allocated because the previous n needs to be saved, so that when n is very large, the function stack will be quickly exhausted. However, tail recursion can help us solve this problem. Tail recursion means that only the recursive function itself is called at the first step of the function call. At this time, the current function stack can be reused because there is no need to remember other variables. The above program only needs to be slightly modified to become a tail recursive program, which is equivalent to the loop in terms of efficiency.

Listing 6. Tail recursion for factorial

Def factorial (n: Int): Int = {@ tailrec def loop (acc: Int, n: Int): Int = if (n = = 0) acc else loop (n * acc, n-1) loop (1, n)}

In the above program, we define a new recursive function inside the factorial function, which either returns the result or calls the recursive function itself in one step, so it is a tail recursive function. The function has an extra variable acc, which is updated every recursive call until the value is returned when the recursive boundary condition is satisfied, which is the calculation result of *. This is a general method to transform a non-tailed recursive function into a tailed recursive function. We can practice and master this method. For tail recursion, the Scala language adds a special comment @ tailrec, which ensures that the program written by the programmer is the correct tail recursion program. If the program is not a tail recursion program due to carelessness, the compiler will report a compilation error to remind the programmer to modify his code.

A series of examination questions

Perhaps some readers still feel unconvinced after reading the above example: although using recursion will make the program simple and easy to understand, I can also do it with loops, only a few more lines of code, and I don't need to know what tail recursion is. the program written is efficient. Let's take a look at the following question: the interesting problem of change. The topic is roughly as follows: suppose a country's currency has a certain denomination, now give a large denomination currency to exchange into small change, ask how many ways of exchange. This question is often used as an interview question by major companies, and I don't know how many students have been baffled. Below, I give the recursive solution of this problem. Readers can try the non-recursive solution of the problem to see how different it will be in terms of the readability of the program and the amount of code. The idea of recursive solution to this problem is very simple: first determine the boundary conditions, if the number of money to be exchanged is 0, then return 1, that is, there is only one method of exchange: unable to exchange. It should be noted here that this problem calculates all the exchange methods, and non-convertibility is also a method. If the type of change is 0 or the amount of money is less than 0, there is no way to exchange it, return 0. We can divide the methods of change into two categories: using all the change that does not include * * coins (change), and using all the change that contains * * coins (change). The sum of the two is all the ways of change. * there are a total of countChange (money, coins.tail) change methods, and the second change method is equivalent to the same exchange for money-conins.head, then this exchange method has countChange (money-coins.head, coins), and the sum of the two is all change methods.

Listing 7. A Recursive solution to the problem of change Exchange

Def countChange (money: Int, coins: List [Int]): Int = {if (money = = 0) 1 else if (coins.size = = 0 | | money < 0) 0 else countChange (money, coins.tail) + countChange (money-coins.head, coins)} Thank you for reading. This is the content of "how to use Scala language". After the study of this article, I believe you have a deeper understanding of how to use Scala language. The specific use situation still needs to be verified by practice. Here is, the editor will push for you more related knowledge points of the article, welcome to follow!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.