This assignment provides parenthetical, sentence, and expanded definitions of the term “Natural Recursion.” This term is consistently used in a computer science course I currently TA in, and this assignment serves as an opportunity to explain a complicated technical term to an audience just entering a technical field.
Term: Natural Recursion
Situation: Lecture notes of a first-year Computer Science (CPSC 110) course at UBC. CPSC 110 is usually the first technical course for Computer Science majors or students who are interested in the field.
Audience: Students taking CPSC 110, who might be Computer Science majors or someone who is inspired to become one. These students might have limited basic computer science knowledge, but most of them are not very versed in computing terminologies or any technical skills.
Parenthetical Definition:
The result of the natural recursion (a process in which a function calls itself to solve complex problems) can be trusted if and only if we have the correct base case result and the correct recursive case result.
Sentence Definition:
Natural recursion is a recursive process that represents a natural design for functions that calls itself as a subroutine to solve a smaller instance of a complicated problem, and it is commonly used for solving computational and mathematical problems.
Expanded Definition:
In computer science, the solution to a complicated problem often depends on the solutions to smaller instances of that same problem. Natural recursion refers to a self-referential process in which a function calls itself as a subroutine to solve a smaller instance of the same problem, and it is a common technique used for solving problems in computer science and mathematics (Carmen, 2009). Natural recursion is an approach applied to solving recursive problems by using functions that call themselves within their own codes, and it is one of the central ideas of computer science.
The term “recursion” comes from the Latin word recursionem, which means “running backward,” or “return.” The term “natural recursion” is used in computer science to describe a type of recursion that arises in a natural way from the problem itself, and “natural” is used to distinguish it from other types of recursions that are less intuitive or more artificial. This term has been widely adopted in computer science and can be seen in many textbooks and courses on algorithms and programming in general.
A natural recursion function definition consists of 2 parts: 1) one or more base cases that do not have a self-reference in their data definition, and 2) one or more recursive cases where a self-reference is present in the data definition. A base case is the stopping condition for the recursion, it is usually specified as the simplest possible solution to the problem being solved. The function stops calling itself when a base case is reached and returns a value that is used to build up a solution to the problem. The recursive case is defined in terms of the relationship between the current problem and smaller instances of the same problem. The recursive step usually requires 2 steps: 1) breaking down the current problem into smaller sub-problems, and 2) calling the function itself recursively on the sub-problems (Girard, 1987). In other words, the base case is the smallest problem that a solution can be easily computed, while the recursive step is used to break down the problem into smaller sub-problems until reaching the base case.
The operating principle of natural recursion is to solve a problem by breaking it down into simpler sub-problems, and recursively solve the sub-problems until the simplest solution to the problem is found. The key insight behind natural recursion is to identify a relationship between the current problem and smaller instances of the same problem, and then the function calls itself, with smaller instances of the problem as arguments, until the simplest instance of the problem is reached (Goodrich, 2010). At this point, the recursive function returns a solution for the base case, and the recursive calls start to unwind and combine the solutions to the sub-problems to construct a final solution to the original complex problem. The result of the natural recursion will be correct if and only if the base case result, the contribution of the first element in the list, and also the combination of the contribution and the result of the natural recursion are correct.
An example of the natural recursion is calculating the factorial of a number “n”, which is the product of all positive integers less than or equal to that number, and the formula can be written as n! = n * (n-1) * (n-2) * … * 2 * 1. Using the natural recursion, we can define a factorial function as follows: 1) If n is 0 or 1, return 1 (the base case). 2) Otherwise, return n * factorial(n-1) (which is the recursive case). In this case, the function calls itself with a smaller value of “n” until the base case of n=0 or n=1 is reached. At that point, the function returns 1, and the previous recursive calls will unwind and return n * factorial(n-1) until a final result is computed. An image illustrating this is attached below.
References:
Carmen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms. Cambridge, MA: MIT Press.
Girard, J.-Y. (1987). Linear Logic. Theoretical Computer Science, 50(1), 1-102.
Goodrich, M. T., Tamassia, R., & Goldwasser, M. H. (2010). Data Structures and Algorithms in Java. John Wiley & Sons.
Leave a Reply