Following up on yesterday's post, a slightly more complex example of tail recursion tail recursion is demonstrated: computing the nth Fibonacci number. The first and second values of the Fibonacci number are 0,1 respectively, and the values that follow in order are the sum of the first two numbers. For example: 0,1,1,2,3,5...

 1 def fib(n: Int): Int = {
 2     @annotation.tailrec
 3       def go(cnt: Int, prev: Int, cur: Int): Int = cnt match {
 4         case m if (m < 0 ) => sys.error("Negative Number Not Allowed!")
 5         case 0 => prev
 6         case c => go(cnt-1,cur, prev + cur)
 7       }
 8       go(n,0,1)
 9   }                                               //> fib: (n: Int)Int
10   fib(5)                                          //> res52: Int = 5

First, tail recursion is when the last statement of a recursive function refers to itself independently. In the above example go(cnt-1,cur,prev + cur) is the last standalone statement that does not add any operations. We can try to approximate.

1 fib(5)
2   go(5,0,1)
3   go(4,1,0+1)                                         = go(4,1,1)
4   go(3,(0+1),1+(0+1))                                 = go(3,1,2)
5   go(2,1+(0+1),(0+1)+(1+(0+1)))                       = go(2,2,3)
6   go(1,(0+1)+(1+(0+1)),(1+(0+1))+(0+1)+(1+(0+1)))    = go(1,3,5)
7   go(0,5,8) => 5

Exactly the answer we expected.

Scala functions (functions) are still worth mentioning. Functions can be used as standard objects: they can be used as input parameters or result values to another function. A function that accepts a function as an input parameter or returns another function as a result is called a high order function. The use of anonymous function (anonymous function or lamda function) or function literal is also common in Scala programming. To demonstrate with sample code from the book.

1 def formatResult(name: String, n: Int, f: Int => Int) = {
2   val msg = "The %s of %d is %d."
3   msg.format(n, f(n))
4 }

noteformatResult is a higher-order function， Because it accepts a functionf As an input parameter。 here Int => Int is a class declaration， It's a function of type。 See how higher-order functions and anonymous functions are used：

1 def main(args: Array[String]): Unit = {
2   println(formatResult("absolute value", -42, abs))
3   println(formatResult("factorial", 7, factorial))
4   println(formatResult("increment", 7, (x: Int) => x + 1))
5   println(formatResult("increment2", 7, (x) => x + 1))
6   println(formatResult("increment3", 7, x => x + 1))
7   println(formatResult("increment4", 7, _ + 1))
8   println(formatResult("increment5", 7, x => { val r = x + 1; r }))
9 }

pass in a functionformatResult The input parameters of thef It can be a normal function likefactorial,abs。 The function text is also available， As long as it is of the typeInt => Int That'll do it.。 Various expressions of the above anonymous functions can be found inScala Language Tutorials。

Recommended>>
1、Programmers Who Hate Algorithms 1 Insertion Sort
2、How to gain insight into hidden needs
3、Make full use of idle server resources to build a private network drive
4、AngularDart 40 AdvancedHTTP Client crown of the head
5、Android Learning DialogFragment

已发送

发送中