Recursion In Programming

Recursion, in programming, is an algorithm for solving problems that depend on smaller versions of the problem. To solve a large problem, we would first solve a smaller version of the problem and then combine it with something to solve the original problem. We would keep solving smaller versions of the problem until we reach the base case which is the smallest version of the problem. Then we would work backwards combining the outputs and finally solving the original problem. In most programming languages recursion is done by allowing functions to call themselves from inside the function.

When writing a recursive function, it is important that we define the correct base case so that our program will eventually terminate. Not having the correct base case, or not having a base case at all, will allow our program to keep making recursive calls, and it will never know to stop. It is also important that we only make recursive calls on smaller and smaller inputs. If our inputs do not decrease, our recursive program will never reach the base case, and therefore will never terminate.

An example of recursion in Python is the factorial(n) function:

def factorial(n):

    if n == 0:

         return 1

    else:

         return n * factorial(n-1)

This function returns n!, assuming that n is an integer. This function first calls the function factorial(n-1) and then multiplies it by n. Because the same function is called again, we will keep solving smaller problems until we get to the base case, which in this case is n = 0.

When designing a recursive algorithm, it is important to decide what the base case is, and how the problem can be constructed from smaller versions of itself. In the factorial example, we know that the smallest integer for which a factorial is defined, is 0. Then we notice that n! is constructed by multiplying n by (n-1)!. Combining these two things we can easily write a python function to implement factorial.

We can make recursive programs to define linked lists, binary trees, and Fibonacci numbers, to name a few examples. We can also use recursion to implement binary search: an effective and useful search algorithm.