**Programming Fundamentals**

** Lecture #9**

** Functions**

Junaid Hassan

Lecturer CS & IT Department UOS MBDIN

junaidte14@gmail.com

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.

- 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

- 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

Textbook ch#5