Introduction
The learners are introduced to recursive processes and learn how a method calls itself in order to achieve repetitious behaviour. By using recursive algorithms, the learners will be in a position to solve problems of this nature.
Recursive Algorithm
Recursion is defined as a method of solving problems that involves breaking a problem down into smaller and smaller sub problems until you get to a small enough problem that it can be solved trivially. Simply this is done by the program calling itself to repeat the same steps.
Recursive problems are solved by developing a recursive algorithm. A recursive algorithm is defined as an algorithm which can call itself with smaller (or simpler) input values, and which obtains the result for the current input by applying simple operations to the returned value for the smaller (or simpler) input. Thus if a problem can be solved by utilizing solutions to smaller versions of the same problem, and the smaller versions reduce to easily solvable cases, then it means that one can use a recursive algorithm to solve that problem.
The recursive method comprises the following:
- A base case where the recursion stops and begins to unwind, and
- A recursive step where the method calls itself
A point worth noting is that a recursive algorithm is said to wind up until the base case is reached and then unwinds. During the unwinding process, further statement programs “pending” may be called.
Recursion is a mechanism whereby repetition can be achieved using a method that continues to call itself until some terminating value is reached, i.e. without using some specific repetition construct.
Example \(\PageIndex{1}\)
The factorial function “!”.
Its definition is:
- 0! = 1
- for all n > 0, n! = n x (n - 1)!
Thus, by repeatedly using the definition, we can work out that
6! = 6 x 5!
= 6 x 5 x 4!
= 6 x 5 x 4 x 3!
= 6 x 5 x 4 x 3 x 2!
= 6 x 5 x 4 x 3 x 2 x 1!
= 6 x 5 x 4 x 3 x 2 x 1 x 1
= 720
Again, notice that the definition of “!” includes both a base case (the definition of 0!) and a recursive part.
Laws of Recursion
Recursive algorithms must obey the following laws:
- A recursive algorithm must have a base case.
- A recursive algorithm must change its state and move toward the base case.
- A recursive algorithm must call itself, recursively.
An explanation of the laws is as follows:
First law: the base case allows the algorithm to stop recursing, i.e. a problem small enough to solve directly.
Second law: a change of state occurs moving the algorithm towards the base case. This occurs when a change of state takes place and which is best illustrated when a data modification happens.
Finally, third law: the algorithm must call itself.
Example \(\PageIndex{2}\)
Find the maximum value in a list of numbers.
The solution to the problem would look like the following:
Function find_max(list)
possible_max_1 = first value in list
possible_max_2 = find_max(rest of the list);
if(possible_max_1 > possible_max_2)
answer is possible_max_1
else
answer is possible_max_2
end
end
Example \(\PageIndex{3}\)
Adding three numbers.
The solution will be something like
function result = add_numbers(a, b, c)
if (nargin() == 2)
result = a + b;
else if (nargin() == 3)
result = add_numbers(a+b, c);
else
error(‘oops’);
end
end
Conclusion
This unit introduced the learner to the recursive algorithms. Examples were used to teach the learner how to write recursive algorithms that can solve self repeating functions. The examples used in the teaching of recursion are also not hinged on any computing language and can thus apply across all the languages. Finally the learners were introduced to the laws of recursion.
Assessment
- List the three key features of a recursive algorithm.
- Write an algorithm that can multiply two numbers using recursion.
