Java tail recursion

A preface,

The tail call

wikipedia

In computer science, a tail call is a situation in which the last action of a function returns the result of a call to a function, i.e. the return value of the last new call is directly returned by the result of the current function. At this point, the tail-call location is called the tail-call location. An important and special case of tail calls is called tail recursion. With proper processing, the efficiency of tail-recursive functions can be greatly optimized. Tail-calls can in principle be optimized for performance (called “tail-call elimination”) by simplifying the structure of the function call stack, but whether tail-call optimization is feasible depends on how well the runtime supports such optimizations.

Tail recursion

Wikipedia:

When a function calls itself (or a function that calls itself, and so on) at the end, this is called tail recursion. Tail recursion is also a special case of recursion. Tail-recursion is a special tail-call that calls its own recursive function directly at the tail. Optimization of tail recursion is also a major reason to focus on tail calls. Tail calls are not necessarily recursive calls, but tail recursion is particularly useful and easy to implement.

Tail recursion has two more features on the basis of ordinary tail calls:

The function itself is called at the tail;
Calculations can be optimized to take up only Stack Space.

Now let’s look at tail recursion in a common language. Question: Find n factorial?

Tail recursion in Java

recursive

methods

	/** ** *@param n n
	 * @returnFactorial * /
	public static BigInteger factorialRecursion(final BigInteger n) {
		if (n.compareTo(BigInteger.ZERO) < 0) {
			throw new IllegalArgumentException();
		}
		if (n.compareTo(BigInteger.ONE) == 0) {
			return BigInteger.ONE;
		} else {
			returnfactorialRecursion(n.subtract(BigInteger.ONE)).multiply(n); }}Copy the code

Test n = 10W

   @Test
   void factorialTailRecursion(a) {
   	Examination.start();
   	BigInteger result = JRecursion.factorialTailRecursion(BigInteger.ONE, BigInteger.valueOf(10000000L));
   	System.out.println("Calculation result :" + result);
   	Examination.end();
   }

Copy the code

run

java.lang.StackOverflowError
	at com.robbendev.blog.recursion.JRecursion.factorialTailRecursion(JRecursion.java:35)
	at com.robbendev.blog.recursion.JRecursion.factorialTailRecursion(JRecursion.java:38)
	at com.robbendev.blog.recursion.JRecursion.factorialTailRecursion(JRecursion.java:38)
	at com.robbendev.blog.recursion.JRecursion.factorialTailRecursion(JRecursion.java:38)
	at com.robbendev.blog.recursion.JRecursion.factorialTailRecursion(JRecursion.java:38)
  
Copy the code

Not surprisingly, stack overflow, look at the tail recursion below.

Tail recursion

Tail recursive method

private int factorialTtailRecursion(final int result, final int n) {
        if (n == 1) {
                return result;
        } else {
                return factorialTtailRecursion(result * n,  n - 1); }}Copy the code

test

case n = 10w

java.lang.StackOverflowError
	at com.robbendev.blog.recursion.JRecursion.factorialTailRecursion(JRecursion.java:35)
	at com.robbendev.blog.recursion.JRecursion.factorialTailRecursion(JRecursion.java:38)
	at com.robbendev.blog.recursion.JRecursion.factorialTailRecursion(JRecursion.java:38)
	at com.robbendev.blog.recursion.JRecursion.factorialTailRecursion(JRecursion.java:38)
	at com.robbendev.blog.recursion.JRecursion.factorialTailRecursion(JRecursion.java:38)
  
Copy the code

Did you find it or did it overflow? Because tail recursion is just like telling the compiler to optimize, but compiler optimization not optimizing is another matter. The Java compiler does not support tail-recursive optimization, so the overflow is still an overflow.

Why doesn’t Java support it? Some online research suggests:

Change the stack trace, making it more difficult to debug the program. I think one of the main goals of Java is to allow programmers to easily debug their code, and stack tracing is critical to doing that.
In a highly object-oriented programming environment. Since iterations can be used instead, the language committee must decide that adding tail recursion is not worth it

At the Jdk programming language level, the Jvm can use goto to jump to the top of a method call with new parameter values. And there is no need to move stack frames or cause security conflicts (Scala,Kotlin support). However, the usage scenario is very strict, so let’s see what Kotlin does, and let’s see what Else Java can do.

Stream lazy loading + simulation

A quick look at the web shows that tail recursion can be implemented by simulating lazy loading of stack +Stream.

Use a functional interface to simulate stack frames

@FunctionalInterface
public interface TailRecursion<T> {
	/** * is used to connect recursive stack frames, lazy evaluation **@returnNext recursive stack frame */
	TailRecursion<T> apply(a);

	/** * Determine whether the current recursion ends **@returnThe default is false, since normal recursion is not finished */
	default boolean isFinished(a) {
		return false;
	}

	/** * gets the recursive result, can only be called at the end of the recursion, this is the default exception, by overwriting the utility class to get the value **@returnThe final result of the recursion */
	default T getResult(a) {
		throw new Error("Recursion not finished, call get result exception!");
	}

	/** * Perform a series of recursions as early as possible. Since there is only one stack frame, use findFirst to get the final stack frame, and then call getResult to get the final recursive value **@returnEvaluate early to get the final recursive result */
	default T invoke(a) {
		return Stream.iterate(this, TailRecursion::apply) .filter(TailRecursion::isFinished) .findFirst() .get() .getResult(); }}Copy the code

The last call to the optimization utility class

public class TailInvoke {
   /** * unified structure method to get the next recursion of the current recursion **@paramNextFrame next recursion *@param <T>       T
    * @returnThe next recursion is */
   public static <T> TailRecursion<T> call(final TailRecursion<T> nextFrame) {
   	return nextFrame;
   }

   /** * Ends the current recursion, overrides the corresponding default method value, changes the completion state to true, sets the final return result, sets the illegal recursive call **@paramValue Indicates the final recursive value *@param <T>   T
    * @returnA tail recursion of the isFinished state true, which is externally initiated by an early evaluation by calling the interface's Invoke method. * /
   public static <T> TailRecursion<T> done(T value) {
   	return new TailRecursion<T>() {
   		@Override
   		public TailRecursion<T> apply(a) {
   			throw new Error("Recursion has ended, illegal call to apply method");
   		}

   		@Override
   		public boolean isFinished(a) {
   			return true;
   		}

   		@Override
   		public T getResult(a) {
   			returnvalue; }}; }}Copy the code

Use the tail call utility class to find the factorial method

	/** * factorial calculation -- use the tail recursive interface to do **@paramFactorial The result of the current recursive stack *@paramNumber The value to be computed for the next recursion *@returnA tail-recursive interface that invokes an early evaluation to get the result */
	public static TailRecursion<BigInteger> factorialTailRecursion1(final BigInteger factorial, final BigInteger number) {
		if (number.equals(BigInteger.ONE))
			return TailInvoke.done(factorial);
		else
			return TailInvoke.call(() -> factorialTailRecursion1(factorial.multiply(number), number.subtract(BigInteger.ONE)));
	}
Copy the code

test

	@Test
   void factorialTailRecursion1(a) {
   	Examination.start();
   	BigInteger result = JRecursion.factorialTailRecursion1(BigInteger.ONE, BigInteger.valueOf(100000L)).invoke();
   	System.out.println("Calculation result :" + result);
   	Examination.end();
   }
Copy the code

No overflow, test passed.

Calculation results:282422940796034787429342157802453551847749492609122485057891808654297795090106301787255177141383116361071361173736196295 147499618312391802272607340909383242200555696886678403803773794449612683801478751119669063860449261445381113700901607668 66405407..// omit n lines--------------- Your code execution time is:3823.95Ms, memory consumption:668.82M + ! ---------------Copy the code

Third, the tail recursion in kotlin

4.1 the recursive

Recursive factorial

    /** ** *@param n n
     * @returnFactorial * /
    fun factorialRecursion(n: BigInteger): Int {
        require(n >= BigInteger.ZERO)
        return if (n.compareTo(BigInteger.ONE) == 0) {
            1
        } else {
            factorialRecursion(n.subtract(BigInteger.ONE).multiply(n))
        }
    }
Copy the code

Test n = 10 w

Overflow.

Tail recursion

code

    / tail recursive writing * * * * *@param result res
     * @param n      n
     * @return res
     */
    tailrec fun factorialTailRecursion(result: BigInteger, n: BigInteger): BigInteger? {
        return if (n == BigInteger.ONE) {
            result
        } else {
            factorialTailRecursion(result.multiply(n), n.subtract(BigInteger.ONE))
        }
    }
Copy the code

The tailrec keyword indicates that this function needs to be optimized by the compiler if it conforms to the form of tail-recursive calls.

test

Calculation results:282422940796034787429342157802453551847749492609122485057891808654297795090106301787255177141383116361071361173736196295 147499618312391802272607340909383242200555696886678403803773794449612683801478751119669063860449261445381113700901607668 664054071705659522612980419583567789090475415128711408369242515352930962606722710387442460886354543639829317477617755326 2185112647485586491818--------------- Your code execution time is:4225.34Ms, memory consumption:39.42M + ! ---------------Copy the code

Why isn’t Java working? Kotlin is working. Java can also be good, look at the test method bytecode.

  public final tailrecFib2(III)I
    // annotable parameter count: 3 (visible)
    // annotable parameter count: 3 (invisible)
   L0
    LINENUMBER 41 L0
    ILOAD 3
    IFNE L1
   L2
    LINENUMBER 42 L2
    ILOAD 1
    IRETURN
   L1
    LINENUMBER 44 L1
    ILOAD 2
    ILOAD 1
    ILOAD 2
    IADD
    ILOAD 3
    ICONST_1
    ISUB
    ISTORE 3
    ISTORE 2
    ISTORE 1
    GOTO L0
   L3
   L4
    LOCALVARIABLE this Lcom/robbendev/blog/recursion/KRecursion; L0 L4 0
    LOCALVARIABLE a I L0 L4 1
    LOCALVARIABLE b I L0 L4 2
    LOCALVARIABLE n I L0 L4 3
    MAXSTACK = 4
    MAXLOCALS = 4
Copy the code

The key code is GOTO LO and you can see that when you compile it’s going to GOTO L0, just like we said before. It’s still in the same method, so there’s no stack overflow.

4. Tail recursion in JavaScript

Tail recursion is already supported in ES6 JS, but only in strict mode. In normal mode, there are two variables inside a function that trace the call stack of the function.

Arguments: Returns the arguments to the function when it is called.
Caller: Returns the function that calls the current function.

Similar to Java, you can’t just change the stack to use the information on it.

recursive

function factorialRecursion(n) {
    if (n === 1) {
        return 1;
    } else {
        return n * factorialRecursion(n);
    }
}
factorialRecursion(100000); / / overflow
Copy the code

Tail recursion

Es6 strict schema supports tail recursion

"use strict";

function factorialTailRecursion(result, n) {
    if (n === 1) {
        return result;
    } else {
        return factorialTailRecursion(result * n, n - 1);
    }
}

factorialTailRecursion(100000); // It is running properly
Copy the code

It doesn’t really matter, though, because browsers don’t support much and don’t run code in strict mode for compatibility.

Trampoline function

function trampoline(f) {  
  while (f && f instanceof Function) {
    f = f()
  }
  return f
}

function f(n, a = 0, b = 1) {  
  if (n > 0) {
    [a, b] = [b, a + b]
    return f.bind(null, n - 1, a, b)
  } else {
    return a
  }
}


trampoline(100000); // It is running properly
Copy the code

Five, the summary

I recursively take 10w factorial	Java	Js	Kotlin
recursive	StackOverFlow	StackOverFlow	StackOverFlow
Tail recursion	StackOverFlow	Strict mode pass	through
other	Simulation stack frame + lazy loading	Trampoline function through	/

Vi. Reference materials

www.cnblogs.com/invoker-/p/… Zh.wikipedia.org/wiki/%E5%B0…

Give a thumbs up for those of you who think you have gained something. Clap brick or contact me [email protected]

A preface,

The tail call

Tail recursion

Tail recursion in Java

recursive

methods

Test n = 10W

Tail recursion

Tail recursive method

test

Stream lazy loading + simulation

Use a functional interface to simulate stack frames

The last call to the optimization utility class

Use the tail call utility class to find the factorial method

test

Third, the tail recursion in kotlin

4.1 the recursive

Recursive factorial

Test n = 10 w

Tail recursion

code

test

4. Tail recursion in JavaScript

recursive

Tail recursion

Trampoline function

Five, the summary

Vi. Reference materials

Related Posts

2020 Interview ali Bytedance, suddenly found that 90% of the JVM interview questions asked, I have seen in this

10 minutes introduction to Nginx basic features

JVM Series 8 (GC Turning Tuning)