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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.