2.7: Application - Recursion and Induction
- Page ID
In computer programming, there is a technique called recursion that is closely related to induction. In a computer program, a subroutine is a named sequence of instructions for performing a certain task. When that task needs to be performed in a program, the subroutine can be called by name. A typical way to organize a program is to break down a large task into smaller, simpler subtasks by calling subroutines to perform each of the subtasks. A subroutine can perform its task by calling other subroutines to perform subtasks of the overall task. A subroutine can also call itself. That is, in the process of performing some large task, a subroutine can call itself to perform a subtask. This is known as recursion, and a subroutine that does this is said to be a recursive subroutine. Recursion is appropriate when a large task can be broken into subtasks where some or all of the subtasks are smaller, simpler versions of the main task.
Prolog is an example of a programming language that uses recursion to powerful effect. Classical Prolog has no loop construct: loops are defined using recursive subroutines.
Like induction, recursion is often considered to be a ‘hard’ topic by students. Exper- ienced computer scientists, on the other hand, often say that they can’t see what all the fuss is about, since induction and recursion are elegant methods which ‘obviously’ work. In fairness, students have a point, since induction and recursion both manage to pull in- finite rabbits out of very finite hats. But the magic is indeed elegant, and learning the trick is very worthwhile.
In your course Computer Organisation you will be tasked to write a small re- cursive program to compute the factorial in Assembly. You can have a sneak- preview below of of what the pseudocode for such a program might be. In future courses like Algorithms & Data Structures and Algorithm Design you will also be tasked to write and analyse recursive algorithms.