Revisiting School Days — Recursion & Recursive functions

Recursion is the process of repeating items in a self-similar way. Any function which calls itself is called recursive. A recursive method solves a problem by calling a copy of itself to work on a smaller problem. This is called the recursion step. Recursion is a useful technique borrowed from mathematics. Recursive code is generally shorter & easier to write than iterative code. For example, sort, search & traversal problems often have simple recursive solutions.

Before diving into the sea, we all have to understand 2 statements -

A recursive function performs a task in part by calling itself to perform the subtasks. So, at some point, the function encounters a subtask that it can perform without calling itself.

1. Base Case: This case, where the function doesn’t recur, is called the Base case.
2. Cursive Case: The function calls itself to perform a subtask and is referred to as the Cursive case.

For example, consider the factorial function: n! is the product of all integers between n and 1. The definition of recursive factorial looks like this:

n! = 1, (if n = 0)

n! = n * (n-1)! (If n>0)

In the recursive case, when n is greater than 1, the function calls itself to determine the value of (n –1)! and multiplies that with n. In the base case, when n is 0 or 1, the function simply returns 1.

Recursion Vs. Iteration

The main inspiration comes to my mind before writing this blog is, which way is better? — Iteration or Recursion. From my point of view, the answer to this question depends on what we are trying to solve. A recursive approach mirrors the problem that we are trying to solve. A recursive approach mat makes it simpler to solve a problem but adds overhead for each recursive call.

Recursion

1. Terminates when a base case is reached.
2. Each recursive call requires extra space on the stack frame (memory).
3. If we get infinite recursion, the program may run out of memory and result in a stack overflow.
4. Solutions to some problems are easier to formulate recursively.

Iteration

1. Terminates when a condition is proven to be false.
2. Each iteration does not require any extra space.
3. An infinite loop could loop forever since there is no extra memory being created.
4. Iterative solutions to a problem may not always be as obvious as a recursive solution.

Before compiling the whole discussion there are some points worth mentioning:

1. Recursive algorithms have two types of cases, recursive cases, & base cases.
2. Every recursive function case must terminate at a base case.
3. Generally, iterative solutions are more efficient than recursive solutions
4. A recursive algorithm can be implemented without recursive function calls using a stack, but it’s usually more trouble than it’s worth. That means any problem that can be solved recursively can also be solved iteratively.
5. Some problems are best suited for recursive solutions while others are not.