Programming Fundamentals
Lecture #9
Functions

Junaid Hassan

Lecturer CS & IT Department UOS MBDIN

junaidte14@gmail.com

Recursion

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
Recursion (Factorial Example)

Fibonacci Series (Recursion Example)

  • 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)
Recursion vs Iteration

  • 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
References

Textbook ch#5