上QQ阅读APP看书，第一时间看更新

Recursion

Another special property of main() is that it cannot be called recursively. From the perspective of the OS, the main() function is the entry point of the program, so calling it again would mean starting everything over; therefore, it is prohibited. However, calling a function recursive just because it calls itself is partially correct. For example, the print_number() function calls itself and never stops:

void print_number(int num) {
 std::cout << num << std::endl;
 print_number(num + 1); // recursive call
}

Calling the print_number(1) function will output numbers 1, 2, 3, and so on. This is more like a function that calls itself infinitely rather than a correct recursive function. We should add a couple more properties to make the print_number() function a useful recursive one. First of all, the recursive function must have a base case, a scenario when further function calls stop, which means the recursion stops propagating. We can make such a scenario for the print_number() function if, for example, we want to print numbers up to 100:

void print_number(int num) {
  if (num > 100) return; // base case
  std::cout << num << std::endl;
  print_number(num + 1); // recursive call
}

There is one more property for a function to be recursive: solving smaller problems that will eventually lead to the base case. In the preceding example, we already had it by solving a smaller problem for the function, that is, by printing one number. After printing one number, we move to the next small problem: printing the next number. Finally, we get to the base case and we are done. There isn't any magic in a function calling itself; think of it as a function calling a different function with the same implementation. What's really interesting is how a recursive function affects the program execution overall. Let's take a look at a simple example of calling a function from an other function:

int sum(int n, int m) { return n + m; }
int max(int x, int y) { 
  int res = x > y ? x : y; 
  return res;
}
int calculate(int a, int b) {
  return sum(a, b) + max(a, b);
}

int main() {
  auto result = calculate(11, 22);
  std::cout << result; // outputs 55
}

When a function is called, memory space is allocated for its arguments and local variables. The program starts with the main() function, which in this example simply calls the calculate() function by passing literal values 11 and 22. The control jumps to the calculate() function and the main() function is kind of on hold; it waits until the calculate() function returns to continue its execution. The calculate() function has two arguments, a and b; although we named parameters of the sum(), max(), and calculate() differently, we could use the same names in all the functions. Memory space is allocated for these two arguments. Let's suppose that an int takes 4 bytes of memory, therefore a minimum of 8 bytes are required for the calculate() function to be executed successfully. After allocating 8 bytes, the values 11 and 22 should be copied to the corresponding locations (see the following diagram for details):

The calculate() function calls the functions sum() and max() and passes its argument values to them. Correspondingly, it waits for both functions to be executed sequentially in order to form the value to return to the main(). The sum() and max() functions are not called simultaneously. First, sum() is called, which leads to a copy of the values of variables a and b to the locations allocated for the arguments of sum(), named n and m, which again take eight bytes in total. Take a look at the following diagram to understand this better:

Their sum is calculated and returned. After the function is done and it returns a value, the memory space is freed. This means that variables n and m are not accessible anymore and their locations can be reused.

We don't consider temporary variables at this point. We will revisit this example later to show the hidden details of function execution, including temporary variables and how to avoid them as much as possible.

After sum() has returned a value, the max() function is called. It follows the same logic: memory is allocated to the arguments x and y, and to the res variable. We intentionally store the result of the ternary operator (?:) in the res variable to make the max() function allocate more space for this example. So, 12 bytes are allocated to the max() function in total. At this point, the x main() function is still on hold and waits for calculate(), which in turn, is on hold and waits for the max() function to complete (see the following diagram for details):

When max() is done, the memory allocated to it is freed and its return value is used by calculate() to form a value to return. Similarly, when calculate() returns, the memory is freed and the main() function's local variable result will contain the value returned by calculate().

The main() function then finishes its work and the program exits, that is, the OS frees the memory allocated for the program and can reuse it later for other programs. The described process of allocating and freeing memory (deallocating it) for functions is done using a concept called a stack.

A stack is a data structure adapter, which has its rules to insert and access the data inside of it. In the context of function calls, the stack usually means a memory segment provided to the program that automatically manages itself following the rules of the stack data structure adapter. We will discuss this in more detail later in this chapter.

Going back to recursion, when the function calls itself, memory should be allocated to the newly called function's arguments and local variables (if any). The function calls itself again, which means the stack will continue to grow (to provide space for the new functions). It doesn't matter that we call the same function; from the stack perspective, each new call is a call to a completely different function, so it allocates space for it with a serious look on its face while whistling its favorite song. Take the look at the following diagram:

The first call of the recursive function is on hold and waits for the second call of the same function, which in turn is on hold and waits for the third call to finish and return a value, which is in turn on hold, and so on. If there is a bug in the function or the recursion base is difficult to reach, the stack will sooner or later overgrow, which will lead to a program crash with the reason known as stack overflow.

Though recursion provides more elegant solutions to a problem, try to avoid recursion in your programs and use the iterative approach (loops). In mission-critical system development guidelines such as the navigation system of a Mars rover, using recursion is completely prohibited.

In chapter 1, Building C++ Applications, we mentioned coroutines. Although we will discuss them in detail later in the book, you should note that the main function cannot be a coroutine.