Lecturer CS & IT Department UOS MBDIN
A recursive function is a function that calls itself either directly or indirectly through another function
Recursive problem-solving approaches have a number of elements in common.
A recursive function is called to solve a problem.
The function actually knows how to solve only the simplest case(s), or so-called base case(s)
- If the function is called with a more complex problem, the function divides the problem into two conceptual pieces: a piece that the function knows how to do and a piece that it does not know how to do.
- To make recursion feasible, the latter piece must resemble the original problem, but be a slightly simpler or slightly smaller version.
Recursion (Factorial Example)
- Because this new problem looks like the original problem, the function launches (calls) a fresh copy of itself to go to work on the smaller problem—this is referred to as a recursive call and is also called the recursion step
- In order for the recursion to terminate, each time the function calls itself with a slightly simpler version of the original problem, this sequence of smaller problems must eventually converge on the base case
Fibonacci Series (Recursion Example)
Recursion vs Iteration
- The Fibonacci series
- 0, 1, 1, 2, 3, 5, 8, 13, 21, …
- The Fibonacci series begins with 0 and 1 and has the property that each subsequent Fibonacci number is the sum of the previous two Fibonacci numbers.
- The Fibonacci series may be defined recursively as follows:
- fibonacci(0) = 0
fibonacci(1) = 1
fibonacci(n) = fibonacci(n – 1) + fibonacci(n – 2)
- Both iteration and recursion are based on a control structure: Iteration uses a repetition structure; recursion uses a selection structure.
- Both iteration and recursion involve repetition: Iteration explicitly uses a repetition structure; recursion achieves repetition through repeated function calls
- Iteration and recursion each involve a termination test: Iteration terminates when the loop-continuation condition fails; recursion terminates when a base case is recognized.
- Iteration keeps modifying a counter until the counter assumes a value that makes the loop-continuation condition fail; recursion keeps producing simpler versions of the original problem until the base case is reached
- Recursion has many negatives.
- It repeatedly invokes the mechanism, and consequently the overhead, of function calls.
- This can be expensive in both processor time and memory space.
- Each recursive call causes another copy of the function (actually only the function’s variables) to be created; this can consume considerable memory
- Iteration normally occurs within a function, so the overhead of repeated function calls and extra
memory assignment is omitted. So why choose recursion?
- Any problem that can be solved recursively can also be solved iteratively (nonrecursively).
- A recursive approach is normally chosen in preference to an iterative approach when the recursive approach more naturally mirrors the problem and results in a program that is easier to understand and debug.
- Another reason to choose a recursive solution is that an iterative solution may not be apparent