44 total
By the end of this topic, you should be able to:
Recursion is a programming method where a function or procedure calls itself.
This may sound strange at first, but it is really just a way of solving a big problem by turning it into a smaller version of the same problem.
A recursive solution keeps breaking the problem into smaller parts until it reaches a point where it can stop.
A simple way to think about it is this:
So, recursion is useful when a problem can be described in terms of smaller versions of itself.
A correct recursive algorithm must have three important features.
A recursive function or procedure must include a statement where it calls itself again.
Without this, it is not recursion.
A base case is the stopping condition.
This is the part where the function can give an answer directly without making another recursive call.
The base case is very important because it prevents the recursion from continuing forever.
Each recursive call must make the problem smaller, simpler, or closer to the stopping condition.
If the problem does not move towards the base case, the function may never stop.
So, a good recursive algorithm must:
If any of these are missing, the recursion will fail.
Recursive algorithms are usually explained using two parts.
The base case is the simplest version of the problem.
It is the case where no more recursive calls are needed.
For example, in the factorial function:
This is the stopping point.
The general case is the part where the function calls itself with a smaller version of the problem.
For factorial:
This means the function solves the problem by using the answer to a smaller factorial.
The general case must always move closer to the base case.
Sign in to view full notes