With the user-defined function, we can write recursive programs. Let’s look at the factorial operation, it is a good example.

We know, n!=(n-1)!*n. That is, if we already know (n-1)!, we can use multiplication to calculate n!; However, special treatment is required when n=0, because (n-1)! is meaningless at this time, and we can not calculate 0! by (0-1)! .

Let’s write a user-defined function to calculate factorial with this idea.

	A	B	C
1	func factorial(n)	if n==0	return 1
2		return factorial(n-1)*n
3	=factorial(0))	=factorial(1)	=factorial(10)

In user-defined function factorial, it calls itself. This method of writing function code is called recursion.

Let’s analyze the execution process of this function. If the parameter is 0, then the condition of B1 holds, continue to execute C1, return 1, the function ends, no problem. By the way, when a user-defined function is executed to the return statement, it will be executed and returned, regardless of whether there are statements after it.

If the parameter n is 1 and the condition does not hold when it is executed to B1, the cell B2 will be executed. At this time, n-1, that is, 1-1=0, will be used as the parameter to call the function first. After entering the function again, paramener n will become 0, and the n equal to 1 will be temporarily stored. Now that the condition of B1 is established again, it returns 1, and then returns to cell B2 before the call. The n stored just now is restored to 1, so it calculates 1*1=1, and returns. There is no problem.

If the parameter n is 2, it will also be executed to cell B2. At this time, n-1=2-1=1 will be passed into this function as the parameter, and n equal to 2 will be temporarily stored. From the above analysis, we know that it will return 1, and then restore the value of n to 2. When the parameter is 2, the function will return 1*2=2, which is correct.

……

As long as the factorial of n-1 can be calculated correctly, the factorial of the current parameter n can be calculated correctly.

Recursion is a bit like the mathematical induction we learned in high school. If we want to prove the proposition related to n, we need only prove these two steps:

1) The proposition is true when n = 0;

2) If n-1 is true, then n is also true.

Recursion is also similar. If we want to do a calculation related to n, the direct calculation may be troublesome. So long as we do these two steps:

1) We can do the calculation when n = 0;

2)If the (n-1)-related calculation has been worked out, we can do the n-related calculation.

We’ve just used the above method to calculate the factorial.

Let’s try the n-th term of the Fibonacci sequence that we have done before. Its rule is as follows:

1)F(1)=F(2)=1

2)F(n)=F(n-1)+F(n-2)

The code written recursively is also very simple:

	A	B	C
1	func fibonacci(n)	if n<=2	return 1
2		return fibonacci(n-1)+fibonacci (n -2)
3	=fibonacci(1)	=fibonacci(3)	=fibonacci(10)

When this code recurses to n, it depends on the two results of n-1 and n-2, and there are two initial cases(n=1 and n=2) to deal with specially.

When writing recursive code, we must pay attention to judging the initial situation. If we forget this judgment, recursion will become an endless loop and never return, and this endless loop will easily lead to memory overflow. This is because every time the recursion enters the function body again, the current variable value will be temporarily stored for recovery when it returns. If the recursion does not return, the space occupied by these variables will soon exceed the memory of the computer.

Careful readers can also analyze that it is not cost-effective to use recursive method to calculate factorial and Fibonacci sequence. The computation amount and memory of these two recursive codes are much larger than the previous loop method. Recursion is used here only as a teaching example, because the logic is relatively simple and it is easy to understand the principle of recursion.

Let’s do another example that is difficult to do without recursion, calculating the full permutation of n.

The full permutation of n means that the n numbers 1, 2,…, n are lined up and all the different arrangements are listed. If n=3, there are 6 types: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]. If n=4 , there are 24 types, and the number of full permutation is n!.

It’s not easy to list the n! types of permutations directly. It’s easier to use recursion.

1)When n = 1, there is only one type, i.e. [1]

2)If we already have the full permutation of n-1, suppose it is a sequence p (it should be a two-layer sequence, and each member is a permutation). Now we just need to arrange n before its first, second,…, and (n-1)-th positions and append it to the last for each member of p to get n new permutations, then collect all the new permutations (n new permutations for each member of p).

Write the code in this way:

	A	B	C
1	func permuataion(n)	if n==1	return [[1]]
2		=permutation(n-1)	=[]
3		for B2	=n.(B3.to(#-1)|n|B3.to(#,))
4			>C2=C2|C3
5		return C2
6	=permutation(4)		=A6.len()

When A1 is 1, directly return the result [[1]], and pay attention to return it as a two-layer sequence. When A1>1, first prepare C2 to be an empty sequence to store the results, recursively call this function to calculate the full permutation of A1-1, and then loop it. For each member, generate A1-1 new permutations in C3 to arrange A1 before the first, second,…, (A1-1)-th positions and append it to the last to get A1 new permutations, and then concatenate these new permutations after C2. At the end of the loop, C2 stores the full sorting of A1 and returns it.

Let’s change the problem again, calculating the m-permutation of n, that is, select m different numbers from 1,2,…, n to arrange. There are two parameters in this case, and the situation is a little more complicated than just now. Similar to the Fibonacci sequence, we need to call the recursive function twice.

1)When m = 1, there are n types, namely [[1],…, [n]];

2)When n>m, after we already have the (m-1)-permutation of n-1 and the m-permutation of n-1, which are recorded by p and q respectively, then as long as n is inserted into each member of p by the positions mentioned earlier, new m permutations can be obtained (each p member corresponds to m new permutations, which all contain n), and then merging them with q (which do not have n), thus getting m-permutation of n.

3) When n = m, just deal with p in step 2, which is equivalent to the full permutation.

	A	B	C
1	func permutation(n,m)
2		if m==1	return n.([~])
3		=permutation(n-1,m-1)	=[]
4		for B3	>C3=C3|m.(B4.to(#-1)|n|B4.to(#,))
5		if n>m	>C3=C3|permutation(n-1,m)
6		return C3
7	=permutation(5,3)		=A7.len()

This section of code is a little complicated, but the difficulty is not the writing of the code itself, but to come up with this calculation method, that is, how to solve the problem mathematically. Let’s recall what we said at the end of the loop chapter. Programming language can’t help us find a solution to a problem, it can only help us realize the solution that we have already thought of.

In order to see the process clearly, we wrote the steps separately. After we are proficient, the code can be more compact.

	A	B	C
1	func permutation(n,m)
2		if m==1	return n.([~])
3		=permutation(n-1,m-1)	=B3.(m.(B3.~.to(#-1)|n|B3.~.to(#,)))
4		return C3.conj()|if(n>m,permutation(n-1,m),[])
5	=permutation(5,3)		=A5.len()

The relatively complicated is C3, which is a two-layer loop function. The expression uses the inner # and the outer ~, resulting in a multi-layer sequence. B3 itself will return a two-layer sequence (each member is a permutation). C3 will expand each member permutation in B3 into a sequence composed of B1 permutations, so as to get a three-layer sequence (each member’s member is a permutation). The conj()function in B4 is used in a multi-layer sequence, concatenates the member sequences, and it is equivalent to performing | operation among all members. C3.conj() is a sequence composed of B1*B3.len() permutations, and the expression to the right of | is easy to understand.

But it’s really hard to understand. Sometimes it’s not a bad thing to write longer code.

---

SPL Programming - Preface
SPL Programming - 6.1 [Reuse] User-Defined Functions
SPL Programming - 6.3 [Reuse] Reusable script