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

This article mainly explains "Scala tail recursion tracing call and what is the limitation method". The explanation in this article is simple and clear, easy to learn and understand. Please follow the idea of Xiaobian and go deep into it slowly to study and learn "Scala tail recursion tracing call and what is the limitation method" together.

To convert the while loop updating var to a more functional style using val only, you can sometimes use recursion. The following example is a recursive function that approximates a value by constantly improving the guess number:

def approximate(guess: Double): Double = if (isGoodEnough(guess)) guess else approximate(improve(guess))

Such functions, with appropriate implementations of isGoodEnough and improve, are often used in lookup problems. If you want the approximate function to execute faster, you might be tempted to try to speed it up by writing it in a while loop, such as:

def approximateLoop(initialGuess: Double): Double = { var guess = initialGuess while (! isGoodEnough(guess)) guess = improve(guess) guess }

Which of the two approximate versions is better? In terms of simplicity and var avoidance, ***, functional wins. But might the imperative approach be more efficient? In fact, if we measure the execution time, they are almost identical! This may be surprising because recursive calls seem to take longer than simply jumping from the end of a loop to the beginning.

However, in the approximate example above, the Scala compiler can apply an important optimization. Note that recursive calls are the *** one thing the approximate function body performs. Functions like approximate, which call themselves in their *** an action, are called tail recursive. The Scala compiler detects tail recursion and updates the function parameter with the new value, then replaces it with a jump back to the beginning of the function.

Morally you should not be shy about using recursive algorithms to solve your problems. Recursion is often a more elegant and concise scheme than loop-based schemes. If the scheme is tail recursive, there is no runtime overhead.

trailing tail recursive function

Tail recursive functions will not create a new stack frame for each call; all calls will be executed within one frame. This may surprise programmers who check their program's stack trace and fail. For example, this function calls itself several times and throws an exception:

def boom(x: Int): Int = if (x == 0) throw new Exception("boom! ") else boom(x - 1) + 1

This function is not tail recursive because an increment operation is performed after the recursive call. If you execute it, you will get what you expect:

scala> boom(3) java.lang.Exception: boom! at .boom(

:5) at .boom(

:6) at .boom(

:6) at .boom(

:6) at .

(

:6) ...

If you now modify boom so that it becomes tail recursive:

def bang(x: Int): Int = if (x == 0) throw new Exception("bang! ") else bang(x 1)

You will get:

scala> bang(5) java.lang.Exception: bang! at .bang(

:5) at .

(

:6) ...

This time, you only see a stack frame of bang. You might think that bang crashes before it invokes itself, but that's not true. If you think you'll be confused by tail-call optimization when you see stack traces, you can turn it off with a switch:

-g:notailcalls

Pass this parameter to the scala shell or scalac compiler. By defining this option, you get a long stack trace:

scala> bang(5) java.lang.Exception: bang! at .bang(

:5) at .bang(

:5) at .bang(

:5) at .bang(

:5) at .bang(

:5) at .bang(

:5) at .

(

:6) ...

tail call optimization

The compiled code for approximate is essentially the same as the compiled code for approximateLoop. Both functions compile the same thing. Three Java bytecode instructions. If you look at the bytecode generated by the Scala compiler for the tail recursive method approximate, you'll see that although isGoodEnough and improve are both called by the method body, approximate is not. Scala compiler optimizes recursive calls:

public double approximate(double); Code: 0: aload_0 1: astore_3 2: aload_0 3: dload_1 4: invokevirtual #24; //Method isGoodEnough:(D)Z 7: ifeq 12 10: dload_1 11: dreturn 12: aload_0 13: dload_1 14: invokevirtual #27; //Method improve:(D)D 17: dstore_1 18: goto 2

Limitations of Tail Recursion

The use of tail recursion in Scala is limited because the JVM instruction set makes it difficult to implement more advanced forms of tail recursion. Scala only optimizes direct recursion calls to return the same function. If recursion is indirect, as in the example below where two mutually recursive functions recurse, there is no possibility of optimization:

def isEven(x: Int): Boolean = if (x == 0) true else isOdd(x - 1) def isOdd(x: Int): Boolean = if (x == 0) false else isEven(x - 1)

Similarly, if *** a call is a function value, you cannot get tail-call optimization. Consider the following example of recursive code:

val funValue = nestedFun _ def nestedFun(x: Int) { if (x != 0) { println(x); funValue(x - 1) } }

The funValue variable points to a function value that essentially wraps the call to nestedFun. When you apply the value of this function to an argument, it turns to apply nestedFun to the same argument and returns the result. So you might expect the Scala compiler to perform tail-call optimization, but in this case it can't. Thus, tail-call optimization is limited to cases where a method or nested function calls itself within an operation without going to some function value or some other intermediate function.

Thank you for reading, the above is "Scala tail recursion trace call and what is the limited method" of the content, after learning this article, I believe we have a deeper understanding of Scala tail recursion trace call and what is the limited method, the specific use of the situation also needs to be verified by practice. Here is, Xiaobian will push more articles related to knowledge points for everyone, welcome to pay attention!

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.