This assignment provides parenthetical, sentence, and expanded definitions of the term “Natural Recursion.” This term is constantly 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 fundamental technique in computer science and mathematics for solving complex problems by using solutions to smaller instances of the same problem.
Expanded Definition:
Natural recursion is a fundamental technique in computer science and mathematics for solving complex problems by using solutions to smaller instances of the same problem. It involves defining a function that calls itself within its own code. This approach is widely adopted in computer science textbooks and courses on algorithms and programming (Kruth, 1997).
The term “recursion” derives from the Latin word “recursio,” meaning “running backward” or “return.” In computer science, the term “natural recursion” refers to a type of recursion that arises naturally from the problem at hand, and “natural” is used to distinguish it from other types of recursion that are less intuitive or more artificial (Bjornsson, 2017). This term has become widely adopted in computer science and is commonly used in textbooks and courses on algorithms and programming.
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. The base case specifies the simplest possible solution to the problem being solved and serves as the stopping condition for the recursion (Cormen et al., 2009). The recursive case breaks down the current problem into smaller sub-problems and calls the function recursively on the sub-problems (Sedgewick & Wayne, 2011).
The operating principle of natural recursion is to solve a problem by breaking it down into simpler sub-problems, and recursively solving the sub-problems until the simplest solution is found. This is achieved by identifying the relationship between the current problem and smaller instances of the same problem and using that relationship to call the function recursively with smaller instances of the problem as its arguments (Cormen et al., 2009).
For example, the natural recursion can be applied to calculate the factorial of a number “n”, which is defined as the product of all positive integers less than or equal to “n”. The factorial function can be defined with a base case of return 1 if “n” is 0 or 1, and a recursive case returning n * factorial(n – 1). The function calls itself with a smaller value of “n” until the base case is reached, and then returns the final result by unwinding the previous recursive calls (Cormen et al., 2009). An image illustrating this is attached below.
Figure 1. Recursion visualization (StudyAlgorithms, n.d.).
References:
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to algorithms (3rd ed.). MIT Press.
Knuth, D. E. (1997). The art of computer programming: Fundamental algorithms (Vol. 1, 3rd ed.). Addison-Wesley.
Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.). Addison-Wesley.
Bjornsson, Y. (2017). Natural recursion. In C. H. Dagli, P. Enslow, & M. Shaffer (Eds.), Computer Sciences (pp. 122-123). Salem Press.
StudyAlgorithms. (n.d.). Recursion and memory visualization. StudyAlgorithms. https://studyalgorithms.com/theory/recursion-and-memory-vizualization/
Leave a Reply