Topic 5

Lesson 5. Recursive Functions

Objective: involves a hierarchical acquisition of skills, from understanding basic operations to the ability to construct and analyze complex functions. At the lowest level, Knowing/Remembering, the student must define the concepts of a recursive function and a computable function, list the four basic operations used to construct primitive-recursive functions (substitution, superposition, primitive recursion, minimization operation), and name the mathematician who undermined the belief in the universality of algorithmic methods (Kurt Gödel). The next level, Understanding, requires the student to explain the essence of the operations of superposition and primitive recursion, interpret the implications of Gödel's theorems for algorithm theory, and formulate the distinction between primitive-recursive and general-recursive functions. The Applying level  requires the student to demonstrate practical application of knowledge, including applying the primitive recursion operation to construct (e.g., a two-place) addition function f(x, y) = x+y based on basic functions, and solving a problem to determine the value of a function (e.g., f(x, 2)) through the sequential application of the operation h. The fourth level, Analyzing, requires the student to compare the hierarchy of computable functions, distinguish the primitive recursion operation from the minimization operation (which is used to construct general recursive functions), and analyze why not all computable functions are primitive-recursive. At the fifth level, Evaluating, the student must justify the importance of the minimization operation for expanding the class of computable functions, criticize the limitations of primitive-recursive functions in solving some classes of problems, and also evaluate the importance of the theory of recursive functions as one of the three main approaches to rigorous algorithm definition. At the highest level, Creating, the student must design (plan) his own composite recursive function, using the operations of superposition and primitive recursion, to model the computational process, and also design a formal description of the computable function that depends on an arbitrary number of arguments.