When writing algorithm problems, you will certainly encounter recursion. Sometimes you will find recursion difficult to understand. In the “One-stop Learning” of Linux C programming, I saw a detailed breakdown of recursion. Factorial (3) is used as an example to analyze the entire call process.

The call of factorial(3)



In the figure, the solid line arrow represents the call, the dotted line arrow represents the return, and the box on the right represents the change of the storage space of each layer of function calls during the call and return process.

  1. Main () has a local variable, result, represented by a box.

  2. The call to factorial(3) allocates storage space for parameters and local variables, so there is another box below main() to represent the parameters and local variables of factorial(3), where n is initialized to 3.

  3. Factorial (3) again calls factorial(2), again allocates the arguments and local variables of factorial(2), so there is another box under main() and factorial(3). As described in section 4, “Global, Local, and Scope,” the parameters and local variables are allocated each time the function is called, and their storage is freed when the function exits. Factorial (3) and factorial(2) are two different calls. The argument n of factorial(3) and the argument n of factorial(2) each have their own storage unit. Even though we only write the argument n once, we run it with two different arguments. And since factorial(3) has not yet exited when factorial(2) is called, the argument n of both function calls exists, so draw an extra box.

We look at the picture above on the right side of the changing process of the storage space, with the function call layer upon layer, one end of the storage space increase gradually, and then with steady return of function calls, the end of the storage space and gradually shortened, and each access parameters and local variables can only access this side of the storage unit, and can’t access to the internal storage unit, For example, when the storage space of factorial(2) is at the end, only its arguments and local variables can be accessed, but not the arguments and local variables of factorial(3) and main(). The data structure with this nature is called a Stack or Stack, the end that changes as the function calls and returns is called the top of the Stack, and the storage space for each function call’s parameters and local variables (each small box in the figure above) is called a Stack Frame. The operating system sets aside a block of stack space for a program to run. A stack frame is allocated in this stack space when a function is called and released when the function returns.

If you believe that the recursive function you’re writing is correct, and you call it, and then you write the recursive function based on that, then it’s going to be correct, and it’s worth believing that it’s correct.

This is a bit of a weird thing to say, but let’s mathematically prove the factorial function. As I said, the correctness of factorial of n depends on the correctness of factorial of n minus 1, and as long as the latter is correct, and there is no doubt that multiplying the result of the latter by n returns, then our implementation is correct. So to prove the correctness of factorial of n is to prove the correctness of factorial of n minus 1, and by the same token, to prove the correctness of factorial of n minus 2, and so on, and finally: To prove the correctness of factorial 1 is to prove the correctness of factorial 0. The correctness of factorial(0) does not depend on any other function call, it is just a small branch of the program return 1; This 1, which we wrote according to our definition of factorial, must be correct, so the implementation of factorial of 1 is correct, so factorial of 2 is correct, and so on, and finally factorial of n is correct. Mathematical Induction is a Mathematical Induction that you learned in high school. To do this, you need to prove a simple Base Case and a Mathematical Induction. When you write a recursive function, you must remember to write Base Case, otherwise even if the recursion is correct, the whole function will not be correct. A few exercises:

Over ** * n factorial is equal to n times n minus 1 factorial. @param num * @return */ private static int factorial(int num) {if (num == 0) {return 1; } else { return num * factorial(num -1); }} /** * If a is divisible by b, the greatest common divisor is b. (Base Case) * Otherwise, the greatest common divisor is the greatest common divisor of b and a% B. * @param a * @param b * @return */ private static int euclidofgcd(int a, int b) { if (a % b == 0) { return b; } else { return euclidofgcd(b, a % b); }} /** * fib(0)=1 (Base Case) * FIB (1)=1 (Base Case) * FIB (n)=fib(n-1)+ FIB (n-2) * @param n * @return */ private static int fibonacci(int n) { if (n == 0 || n == 1) { return 1; } else { return fibonacci(n - 1) + fibonacci(n - 2); }}Copy the code