Today, we’re going to talk about recursive functions. Why recursion? Actually from the movie titles “Kongbu Cruise ship” and “Inception” came to mind.

Recursion is what

I’m sure you’ve written about recursive functions, and I’m sure you’ve written about them in school, and I’m sure the first example is Fibonacci numbers. Such as:

int Fibonacci(n) {
	if (n < 2) return n;
	return Fibonacci(n - 1) + Fibonacci(n - 2);
}
Copy the code

A recursive function is simply a function that “recursively” calls itself. When you write a recursive function, you need to pay attention to the end condition of the recursive function. Recursive functions can indeed simplify the implementation of many algorithms, such as the common binary tree traversal. However, when writing recursive functions, the most common problem is the so-called stack overflow.

Why is there a “stack overflow”? Because the process of function call, all with the help of “stack” this storage structure to store some state at run time, such as the variable copy in the process of function call, the address of function call and so on. The “stack” tends to have limited storage space, and when its storage space is exceeded, the famous exception/error “StackOverflowError” is thrown.

Let’s take a simple addition example, for example:

int sum(int n) {
    if (n <= 1) return n;
    return n + sum(n- 1);
}
Copy the code
std: :cout << sum(100) < <std: :endl;
std: :cout << sum(1000000) < <std: :endl;
Copy the code

A simple answer: after compilation and operation, correct answers can be obtained for relatively small numbers. When the numbers are enlarged, a “segmentation fault” directly occurs.

(python27.Those who qualify can go onto university.) ➜ hexo.tanglei.name git:(master) eligible./a.out5050
[1]    78159 segmentation fault  ./a.out
Copy the code

What is tail recursion?

I first learned about this concept from an interview many years ago, when an interviewer asked me, “Do you know what tail recursion is?” I thought it was “fake” recursion, is it fake recursion?? At the beginning, I was also confused. You can tell from the “tail” if the function recursively calls itself at the tail. The above example, written as a tail recursion, becomes the following:

int tailsum(int n, int sum) {
    if (n == 0) return sum;
    return tailsum(n- 1, sum+n);
}
Copy the code

You can try the result and add the calculation from 1 to 1000000, which is still a segmentation fault. Why is that? Because of this method, there are still many layers of nested function calls in the middle, there are still pushing, pushing, etc., taking up storage space (but can save some space than the previous method).

Tail recursive optimization

When you optimize the compiler options, the miracle happens and you get the correct result. As shown in the figure:

The reason is because the compiler helps with tail recursion optimization, so you can open up assembly code to see it (C++ is not shown here). I’ll use Scala, a familiar JVM based language, to illustrate the optimization process. Scala itself provides an annotation to help the compiler enforce tailrec to see if tailrec is possible.

object TailRecObject {

   def tailSum(n: Int, sum: Int) :Int = {
        if (n == 0) return sum;
        return tailSum(n- 1, n+sum);
    }

   def main(args: Array[String]) {
      println(tailSum(100.0))
      println(tailSum(1000000.0))}}Copy the code

The result is shown below. By default, Scalac does tail-recursive optimization and calculates the result correctly. When the tail-recursive optimization is removed with the -g:notailcalls compilation parameter, Is what happened to the Exception in the thread “is the main” Java. Lang. StackOverflowError.

Let’s look at the differences in the generated bytecode.

As you can see above, tail-recursion is optimized to become a loop (similar to the previous C++).

Okay, tail recursion so that’s it. Personally, I wish we knew there was a point called “tail recursion”. Sometimes we write recursion for convenience and readability, but if it is really for performance, we can implement it iteratively, independent of the compiler implementation. Of course, for things like Scala, it’s a good idea to have some syntactic sugar to help with verification and validation. But the ability to recurse and iterate would be better if we had it. What do you want to talk about next time? Welcome to leave a message. Old rules, if there is help (to the other people around you to help also ah, a little help also will not see here, ha ha, mo to white piao), writing an article is really not easy, hope pro more help “see”, forwarding share support.

Good recommendation

  • A floating point number produced by cross-platform bug | you unexpected results.
  • RSA algorithm and a “sidetrack” attack.
  • Shock!!! Ali’s programmers were no more than stumped by a simple SQL query.
  • After 7 rounds of interviews with Google, they still couldn’t escape the fate of being suspended.

This article was first published in Tangleithu. Please pay attention to it and get technical dry goods in time.