====================== Functional recursion ====================== “Recursion” is a programming technique whereby the algorithm to solve a problem is decomposed into a *base case* where the result is simple, and a *general case* where the result is a computation that reuses the computation for a simpler case. The technique is closely related to the *principle of induction* in mathematics. Actually, the little-known but very effective trick to learn to use recursion is to first ignore all aspects related to programming and concentrate on the mathematical notion of induction as a first step. .. contents:: Inductive definitions in maths ============================== An *inductive definition* in maths is the definition of some object or concept :math:A(n), depending on a non-negative integer parameter :math:n, according to the following scheme: a) the value of a finite number of base cases, at least one (eg. :math:A(0)) is given; and b) a rule is given for obtaining the value of :math:A(n) from :math:n and fixed number of values in :math:A(0)...A(n-1). Some typical inductive definitions: ============= ===================== ================================ Function Base case(s) General case ============= ===================== ================================ :math:n! :math:0! = 1 :math:n! = n \times (n-1)! :math:x^n :math:x^0 = 1 :math:x^n = x \times x^{n-1} Fibonacci :math:F(0)=F(1)=1 :math:F(n) = F(n-1) + F(n-2) ============= ===================== ================================ For the purpose of this course, you need to learn how to write all inductive definitions in maths according to the same fixed format: - on the first line, the function name, the domain of its parameter(s) and its image set; - on the second and following lines, the base cases, expressed using the function name; - on the last line, the general case, expressed using the function name. For example: :math:\left\{\begin{array}{rcl} \text{fact}: \mathbb{N} & \mapsto & \mathbb{N}^* \\ \text{fact}(0) & = & 1 \\ \text{fact}(n) & = & n \times \text{fact}(n-1) \\ \end{array}\right. (Now how we use “fact(n)” instead of “n!” here.) :math:\left\{\begin{array}{rcl} \text{pow}: \mathbb{R}\times\mathbb{N} & \mapsto & \mathbb{R} \\ \text{pow}(x, 0) & = & 1 \\ \text{pow}(x, n) & = & x \times \text{pow}(x, n-1) \\ \end{array}\right. (Note how we use “pow(x,n)” instead of “:math:x^n” here.) :math:\left\{\begin{array}{rcl} \text{fib}: \mathbb{N} & \mapsto & \mathbb{N}^* \\ \text{fib}(0) & = & 1 \\ \text{fib}(1) & = & 1 \\ \text{fib}(n) & = & \text{fib}(n-1) + \text{fib}(n-2) \\ \end{array}\right. Finding your own inductive definition ===================================== The idea to use inductive definition should come to mind automatically as soon as you are faced with a description of what a function does based on some examples using an ellipsis “...”. Consider for example the following description: “Implement a function sine(x,n) which approximates the trigonometric function of the same name using its Taylor series with n terms, that is: sine(x,n) = x - x^3/3! + x^5/5! - x^7/7! + ... with n terms, with n at least 1.” This description uses the ellipsis “...” so it invites an inductive definition. Once you have this idea, you can achive an inductive definition as follows: 1. recognize in the description example which are the results for the *most simple form(s)* of the function, and write this down. This becomes the base case. 2. *reformulate the function at a step n using the result at step n-1, n and/or the other parameters.* Then write this down. This becomes the general case. 3. Write down the resulting definition using the canonical format described above. In the example above, the most general form is when n = 1: :math:\text{sine}(x, 1) = x Then at a given term n: :math:\text{sine}(x, n) = \text{sine}(x, n-1) + (-1)^n\frac{x^{(2n-1)}}{(2n-1)!} So we can then write using the canonical format: :math:\left\{\begin{array}{rcl} \text{sine}: \mathbb{R}\times\mathbb{N} & \mapsto & \mathbb{R} \\ \text{sine}(x, 1) & = & x \\ \text{sine}(x, n) & = & \text{sine}(x, n-1) + (-1)^n\frac{x^{(2n-1)}}{(2n-1)!} \\ \end{array}\right. Likewise, consider the following description: “Implement a function :math:p(n) which for any :math:n\geq 1 is equal to the following:: p(1) = 1 p(2) = 1 * 2 * 1 p(3) = 1 * 2 * 1 * 3 * 1 * 2 * 1 p(4) = 1 * 2 * 1 * 3 * 1 * 2 * 1 * 4 * 1 * 2 * 1 * 3 * 1 * 2 * 1 ... As a first step we need to recognize the most simple case, this is given for p(1). Then we need to recognize how p(n) is expressed from p(n-1). For this we can look how p(2) is made from p(1):: p(2) = p(1) * 2 * p(1) Then how p(3) is made from p(2):: p(3) = p(2) * 3 * p(2) by trying out the first few terms, we recognize the pattern and we can generalize:: p(n) = p(n-1) * n * p(n-1) From this we can express the full mathematical definition: :math:\left\{ \begin{array}{rcl} p: \mathbb{N}^* & \mapsto & \mathbb{N}^* \\ p(1) &=& 1 \\ p(n) &= & p(n-1) \times n \times p(n-1) \\ \end{array}\right. From mathematical definition to recursive function ================================================== Once you have obtained a mathematical inductive definition, it is possible to transcribe the definition directly into a programming language, to obtain a *recursive function*. To do this, proceed as follows: 1. use the name of the function in the first line of the mathematical definition. 2. define the argument and return types using the domain and image sets of the mathematical definition. 3. inside the function body, use a if construct to detect the base cases. For each base case, use return to set the corresponding value. 4. in the else branch that does not correspond to the base case, write the general case. Do not hesitate to transcribe the mathematical definition without changes. It is OK that the function name appears in your transcription. For example, consider the mathematical definition earlier: :math:\left\{\begin{array}{rcl} \text{fact}: \mathbb{N} & \mapsto & \mathbb{N}^* \\ \text{fact}(0) & = & 1 \\ \text{fact}(n) & = & n \times \text{fact}(n-1) \\ \end{array}\right. We take the name of the function, its domain and image and we transcribe: .. code:: java int fact(int n) { Then we use a if construct for the base case: .. code:: java if (n == 0) return 1; Then we finish with the general case: .. code:: java else return n * fact(n-1); } This gives us the following recursive function: .. code:: java int fact(int n) { if (n == 0) return 1; else return n * fact(n-1); } Likewise for the following definition: :math:\left\{ \begin{array}{rcl} p: \mathbb{N}^* & \mapsto & \mathbb{N}^* \\ p(1) &=& 1 \\ p(n) &= & p(n-1) \times n \times p(n-1) \\ \end{array}\right. The resulting code is: .. code:: java int p(int n) { if (n == 1) return 1; else return p(n-1) * n * p(n-1); } Likewise, for the following: :math:\left\{\begin{array}{rcl} \text{sine}: \mathbb{R}\times\mathbb{N} & \mapsto & \mathbb{R} \\ \text{sine}(x, 1) & = & x \\ \text{sine}(x, n) & = & \text{sine}(x, n-1) + (-1)^n\frac{x^{(2n-1)}}{(2n-1)!} \\ \end{array}\right. The resulting code is: .. code:: java double sine(double x, int n) { if (n == 1) return x; else return sine(x, n-1) + sign(n) * pow(x, 2*n-1) / fact(2*n-1); } // Here we need some helper functions because // Java does not have a native operator for // exponentiation: int sign(n) { if (n % 2 == 0) return 1; else return -1; } // Notice how pow() is itself a recursive function. double pow(double x, int n) { if (n == 0) return 1; else return x * pow(n-1); } Important concepts ================== - *inductive definition* in maths; - standard format (presentation) for inductive definitions; - *base case* and *general case*; - process to recognize an inductive definition; - process to translate an inductive definition in math into a recursive function in Java; Further reading =============== - Think Java, sections 4.8 & 4.9 (pp. 44-46) - Introduction to Programming, section 9.1 (pp. 423-435) - Absolute Java, chapter 11 (pp. 648-687) ---- Copyright and licensing ======================= Copyright © 2014, Raphael ‘kena’ Poss. Permission is granted to distribute, reuse and modify this document according to the terms of the Creative Commons Attribution-ShareAlike 4.0 International License. To view a copy of this license, visit http://creativecommons.org/licenses/by-sa/4.0/ _.