In computer science, two important mathematical concepts are encountered, namely recursion and mathematical induction. They have different applications, but both rely on the same approach to the problem: relate the problem to a smaller problem, or a simpler one. The main use of recursion in programming is to solve a problem by calling a function again with a smaller input, whereas the main use of mathematical induction is to prove, for a set of cases, that a statement is true for the entire set.
Knowing the relationship between these concepts enables computer science students to appreciate why recursive programs work, how algorithms can be analyzed and how complex structures can be systematically dealt with. Recursive thinking can be used in a variety of computing contexts, such as calculating factorials, generating sequences, searching trees, and processing graphs.
Recursion in Computer Science
Recursion is a method of solving a problem in which the function calls itself to solve smaller subsets of the original problem. A recursive solution breaks the problem up into smaller steps and then solves each one of them, also in a recursive manner. A recursive function must have a stopping condition, called the base case, and a recursive case that brings the problem closer to the stopping condition. If there is no base case, a recursive function might continue to call itself indefinitely, which might lead to a program running out of memory. This is not just a function that calls itself, but a well-designed method that includes repetition (reduction), problem reduction and a well-defined stopping point.
Base Cases and Recursive Cases
A well written recursive function generally has two necessary parts: a recursive case and a base case. The base case is the most basic version of the problem that the answer can be derived directly without making any further recursive call. The recursive case, on the other hand, is used to specify what happens to the problem at hand when it is reduced to a smaller version. For example, if n is a positive integer, the factorial of n is defined as the product of all positive integers from 1 to n, and 0! = 1.
A recursive implementation is exactly this definition. The function breaks the problem down as follows: It calculates 5! as 4! multiplied by 5, then 4! multiplied by 4, then 4! multiplied by 3, and so on, until it reaches the base case. When the recursive calls return, the results are added together.
Recursion: What It Can Do and How It Works
The big upside to recursion is that it’s a way to formulate a complex problem in terms of a simpler form of the same problem. This is very handy if the problem has a hierarchical or repetitive structure. A computer file system can have folders within folders in a recursive manner, for instance. In the same way, data structures are trees, which can contain trees as subtrees and divide-and-conquer algorithms break up a large problem into smaller subproblems repeatedly. These structures can be matched with a recursive function, and thus the algorithm will be easier, conceptually, to understand.
But it is not always a better idea to use recursion than iteration. The programmer should take into account memory usage; recursive programs may need more memory as the smaller calls might be waiting on the call stack until the larger call is completed.
Common Recursive Algorithms
Recursion is often used in many popular computer science algorithms with problems that are naturally recursive. Examples are binary search, merge sort, quicksort, depth first search, tree traversal and mathematical sequence algorithms. For example, in binary search, a sorted collection of elements is repeatedly split into half the size until the target value is found or all of the elements have been split. Merge sort also breaks down an array into smaller subarrays, sorts them recursively, and then merges them.
Preorder, inorder, and postorder traversal are recursive algorithms that visit nodes and (sub)trees. These examples illustrate common recursive algorithms in general, in which the same basic approach is applied to reduce a problem without altering the structure of the problem.
Sequence: List of Elements in a Specific Order.
A sequence is an ordered list of elements. Another example of the connection between recursion and computer science are mathematical sequences. A sequence can be defined recursively by providing one or more starting terms and a recursive rule that specifies how to get the later terms from the previous ones. For example, the Fibonacci sequence. It is started with two initial terms, often written as F(0) = 0 and F(1) = 1, and the following terms are generated by adding together the two previous terms. Thus, the recursive rule can be written as F(n) = F(n − 1) + F(n − 2). The following recursive program could be written directly after this mathematical definition, computing the two numbers that came before it before computing the current number. This is convenient because the correspondence between mathematical notation and program design is clear, but this simple version of recursive Fibonacci will make many unnecessary mathematical calculations and so can be inefficient with large inputs.
Think Recursively Beyond Mathematical Formulas
Recursive thinking is not limited to equations such as factorials and Fibonacci numbers. It can be used on any problem with smaller problems that are similar to the original problem. Consider searching through a binary tree. The algorithm can run for each node, processing the node and then recursing on the left and right subtree. This is also applicable if you have nested folders, expressions to evaluate as trees or hierarchical organizational data.
In each instance, the whole building does not need to be viewed as one giant entity. Rather, it manages one piece, while passing the rest of the work on to smaller structures. This is helpful thinking because it will motivate the programmer to ask himself the important question: “If the problem were smaller, could the same method work?”
Maths Induction
Mathematical induction is a method of proof that is employed to show that a statement is valid for all integers within a given range of integers, typically starting from a certain integer. It is particularly suitable for natural numbers, sentences, sequences, sums, inequalities and properties of algorithms. Usually there are two main parts to a proof by induction: the base case and the inductive step.
In the BaseCase it is demonstrated that the statement is true for the first value. In the inductive step, the proof is given that if the statement holds for a general value then it must hold for the following value. This process sets up a string of logical implications, making sure that if the first case is true, then the latter case is true, and so on.
The Base Case in Induction.
The base case in mathematical induction is similar to the base case in a recursive function. If a statement P(n) is suspected to be true for all integers n ≥ 1, then write a proof. In an induction proof, the first step is to show P(1). This does not constitute evidence in and of itself but is a starting point for the logical chain.
For instance, it is known that the sum of the first n positive integers is equal to n(n + 1)/2. For n = 1, the left side is 1 and the right side is 1(2)/2, which is also 1. Hence, for the first value the statement is true. This is the basis from which the next step will show that the formula is valid for the next value as well.
The Inductive Step
An induction proof consists of two parts: the base case and the inductive step. First, the proof assumes that the statement is true for some arbitrary integer k. This is an assumption made: induction hypothesis. Next, it is assumed that the statement is true for k + 1 and the proof is then repeated to show that it must be true for k + 2. Suppose that the sum of the first k positive integers is k (k + 1) / 2 (for the sum formula). If the statement is assumed true for k, then add k + 1 to both sides of the assumed statement to prove the statement true for k + 1.
The expression obtained can be rearranged as (k + 1)(k + 2)/2, which is the desired formula for the sum of the first k + 1 positive integers. The formula is true for the base case, and each case follows logically from the previous one, so the formula is true for all positive numbers.
Relationship between Recursion and Induction
Recursion and Induction are related in some special way. It becomes particularly clear that recursion is similar to mathematical induction when looking at what each deals with in a series of similar cases. Recursive functions start with a base case and apply a recursive rule to break down a problem into smaller and smaller components until it reaches the base case. The principle of mathematical induction starts with a first case and a rule of induction to prove cases after the first case. In both cases the base case serves as a foundation and the repeated relationship is used to link simple cases with complex cases. For this reason, induction is often employed in the proof of recursive algorithms. When an algorithm gives the right answer for its smallest legal input and can be proved to give the right answer for a larger input if it gives the right answer for a smaller input, the algorithm can be proved correct for the whole legal range of the input.
Proving a Recursive Algorithm Correct
Now suppose that a recursive algorithm works on a set of objects by solving a smaller instance of the same problem and then building up the answer based on the results of the smaller problem. Using mathematical induction can be helpful to ensure that the algorithm is correct. Firstly, the base case of the algorithm needs to be analyzed and demonstrated to return the correct result. Now suppose that the recursive call correctly solves the smaller problem. This is the induction hypothesis.
The proof then shows that the current step is correct for computing the correct result for the larger problem by using the correct smaller result. This method is especially convenient in the cases of sorting algorithms, searching procedures, operations in trees, and mathematical calculations using recursion. The proof not only demonstrates that the algorithm works for a handful of examples, it also demonstrates that it has a logical explanation for all valid inputs for which the algorithm is supposed to work.
Data Structures: Recursion
When dealing with data structures that usually consist of smaller data structures of the same type, recursive thinking is particularly significant. Trees make for a good example, since each subtree is a tree, too. A binary tree is made up of nodes, each node may have a left and a right subtree. A recursive traversal algorithm can then visit a node and then recursively call itself for its smaller subtrees. For instance, an inorder traversal traverses the left subtree, then the current node, and finally the right subtree.
The process is repeated until the missing child is found which constitutes the stopping condition. Tree operations are a good application of recursion because of this structure. Other hierarchical data structures such as file systems, expression trees, decision trees, and others, can be treated similarly, with each part of the structure having smaller components.
Divide-and-Conquer and Recursion
Another important algorithmic strategy that is closely related to recursion is divide-and-conquer. The main concept is to break up a large problem into smaller problems, solve each of these subproblems, and finally put the solutions of these subproblems together to get the final solution. This is illustrated in merge sort. The array is segmented and the smaller segments are sorted until the remaining segments are either of size 1 or easy to be sorted. Then the algorithm merges these smaller sorted chunks together in an orderly fashion until the entire list is sorted.
The recursive division can be done naturally since the same sorting process can be used for each smaller piece. The algorithm could then be formally connected to a mathematical proof of correctness with mathematical induction, by reasoning about whether it performs the correct sorting on arrays of different sizes.
Recursion, Induction and Algorithm Correctness
Computer scientists require more than just algorithms that appear to be correct for a handful of sample inputs. When an algorithm is applied to a system that can have serious consequences if the algorithm is incorrect, there should be a logical basis for the correctness of the algorithm. One approach to demonstrating correctness for algorithms specified recursively or as functions of the size of the input is through the use of mathematical induction.
For instance, to prove that an algorithm is correct for one element in an input. The proof can then assume that it works for an input of size k and prove that the algorithm also works for an input of size k + 1. This step follows the manner the algorithm was solved (smaller then bigger cases). As a result, induction is seen as a useful mathematical technique to convert the intuitive belief in the correctness of an algorithm into a formal proof of correctness.
Advantages and Disadvantages of Recursive Problem Solving
There are a few key benefits to recursive problem solving. It can help to make algorithms easier to express when the problem is naturally recursive, particularly when dealing with trees, divide-and-conquer procedures, nested structures and mathematical definitions. Recursive code can also minimize the explicit control logic needed since the programming language’s call stack handles many of the details of repeated function calls. However, recursion will have its drawbacks. Every recursive call could need more memory and a poorly written recur call can lead to too many calls or not get to the base case.
There are also other recursive algorithms that are inefficient in that they also do the same calculations over and over, like the recursive Fibonacci calculation. In this case, memoization, dynamic programming, iteration or other more efficient algorithmic approaches can speed things up. Thus, a good programmer will not only know how to program using recursion, but also identify when to program using a recursive approach.
Conclusion
In computer science there are two complementary approaches to the problems: recursion and mathematical induction. Recursion provides a way for a program to solve a large problem by decomposing it into smaller problems of the same type, and induction provides a way for mathematicians and computer scientists to prove that a statement or algorithm is true for all values in a range. Both heavily depend on the notion of a base case and a relation between a case and another. This close relationship is the reason induction is so helpful in proving recursive algorithms correct.
Recursive thinking is used throughout computer science, whether in calculating factorials, mathematical sequences, sorting, tree traversal, search, or divide-and-conquer. By learning to identify recursive structures, and to reason formally about them in an inductive manner, students can tackle computational problems in a more systematic way, and they can get a better grip on not just how an algorithm works, but why.
