Algorithms Basics: Topic – Recursion


Recursive functions are well known in the domain on algorithms. They are widely used due to their simplicity of code. Here we describe the topic of recursion.

Recursive functions:

Any function that calls itself is called a recursive function!

Yep! It’s just that simple. Let me explain with an example. Below is the code for fibonacci series. Note how fib() takes an input of (n) and returns the n-th term of the series. This function calls itself when n>2. This is a typical example of recursive functions.

def fib(n):
	if(n>0):
		if(n==1):
			return 0
		if(n==2):
			return 1
		else:
			return fib(n-1) + fib(n-2)

Fork the code yourself here!

Properties of recursive functions:

  • Recursive functions have two cases:
    • A base case: where the function terminates.
    • A recursive case: where the function calls itself.
  • Every recursive function must terminate at base case. If not defined, the function goes into infinite loop and hence result in stack overflow.
  • Recursive functions store the function information in stack memory.
  • Every algorithm modeled using recursive function can also be modeled using iterative functions by using stack data structures.
  • Iterative solutions are more efficient than recursive functions due to the overhead of extra function calls and stack memory usage.
  • Recursive functions are used since it is easy to visualize the algorithm using recursive approach.
  • For some problems there are no obvious iterative approach algorithms, and hence recursive functions are preferred.

Examples of recursive algorithms:

  1. Fibonacci Series. Try yourself here!
  2. Factorial of a number. Try yourself here!
  3. Merge Sort.
  4. Quick Sort.
Advertisements