Recursion is a process for solving problems by subdividing a larger problem into smaller cases of the problem itself and then solving the smaller, more trivial parts. Recursion is a powerful programming and problem-solving tool. It can be used with a wide range of problems from basic traditional iterations to more advanced backtracking problems.

Recursive Functions

A function can call any other function, even itself. A function that calls itself is called as a recursive function. It looks like a virtual loop or repetition used in a fashion similar to a while loop.

Consider the simple problem of printing the integer values from 1 to n in reverse order. The iterative solution for this problem is rather simple when using a loop construct. But it can also be solved recursively, that is, using a recursive function. Suppose, we have implemented the following recursive function:

def printRev( n ):
 if n > 0 :
   print( n )
   printReverse( n-1 )

and we call the function with an argument of 4:

printRev( 5 )

The current flow of program is stopped and control is transferred to the printRev() function with a value of 4 being assigned to the argument n. The code inside printRev() begins execution from the first statement. Since 5 is greater than 0, the code of the if statement is run.

Properties of Recursion

All recursive solutions must satisfy three rules or properties:

1. A recursive solution must contain a base case.
2. A recursive solution must contain a recursive case.
3. A recursive solution must make progress toward the base case.

A recursive solution subdivides a problem into smaller versions of itself. For a problem to be subdivided, it typically must consist of a data set or a term that can be divided into smaller sets or a smaller term. This subdivision is handled by the recursive case when the function calls itself. In the printRev() function, the recursive case is performed for all values of n > 0.

Factorials

The factorial of a positive integer n can be used to calculate the number of permutations of n elements. The function is defined as:

n! = n * (n - 1) * (n - 2) * …. * 1

with the special case of 0! = 1. This problem can be solved easily using an iterative implementation that loops through the individual values [1...n] and computes a product of those values. But it can also be solved with a recursive solution and provides a simple example of recursion. Consider the factorial function on different integer values:

0! = 1
1! = 1
2! = 2 * 1
3! = 3 * 2 * 1
4! = 4 * 3 * 2 * 1
5! = 5 * 4 * 3 * 2 * 1

Now, let’s try to put this in a code sample:

# Compute n!
def fact( n ):
assert n >= θ, "Factorial not defined for negative values."
if n < 2 :
  return 1
else :
  return n x fact(n− 1)

The Run Time Stack

Each time a function is called, an activation record is automatically created in order to maintain information related to the function. One piece of information is the return address. This is the location of the next instruction to be executed when the function terminates. Thus, when a function returns, the address is obtained from the activation record and the flow execution can return to where it left off before the function was called.

The activation records also include storage space for the allocation of local variables. Remember, a variable created within a function is local to that function and is said to have local scope. Local variables are created when a function begins execution and are destroyed when the function terminates. The lifetime of a local variable is the duration of the function in which it was created.

Print a Singly Linked List in reverse order

Print the contents of a singly linked list in reverse order.

def printListBF( head ):
   # Count the number of nodes in the list.
  numNodes = θ
  curNode = head
  while curNode is not None :
   curNode = curNode.next
   numNodes += 1
  # Iterate over the linked list multiple times. The first iteration
  # prints the last item, the second iteration prints the next to last
  # item, and so on.
for i in range( numNodes ):
  # The temporary pointer starts from the first node each time
  curNode = head

  # Iterate one less time for iteration of the outer loop.
for j in range( numNodes − 1 ):
   curNode = curNode.next

  # Print the data in the node referenced by curNode.
print( curNode.data )

To provide a more efficient solution to the problem, a stack structure can be used to push the data values onto the stack, one at a time, as we traverse through the linked list. Then, the items can be popped and printed resulting in the reverse order listing. The resulting stack after the iteration over the list and before the items are popped. Assuming the use of the linked list version of the stack, printListStack() has a runtime of O(n), the proof of which is left as an exercise.

Using a stack to print a linked list in reverse order.

# Print the contents of a linked list in reverse order using a stack.
from lliststack import Stack
def printListStack( head ):
  # Create a stack to store the items.
 s = Stack()
  # Iterate through the list and push each item onto the stack.
 curNode = head
 while curNode is not None :
   s.push( curNode.data )
   curNode = curNode.next

 # Repeatedly pop the items from the stack and print them until the
 # stack is empty.
while not s.isEmpty() :
  item = s.pop()
  print item

A recursive solution for this problem is also possible. To design the solution, we use the divide and conquer strategy.

Limitations of recursions

Every time a function calls itself it stores some memory. Thus, a recursive function could hold much more memory than a traditional function. Python stops the function calls after a depth of 1000 calls. If you run this example:

#!/usr/bin/env python
def factorial(n):
   if n == 1:
       return 1
   else:
       return n * factorial(n-1)

print factorial(3000)

 You will get the error:

RuntimeError: maximum recursion depth exceeded

In other programming languages, your program could simply crash. You can resolve this by modifying the number of recursion calls such as:

#!/usr/bin/env python
import sys
sys.setrecursionlimit(5000)

def factorial(n):
   if n == 1:
       return 1
   else:
       return n * factorial(n-1)

print factorial(3000)

But keep in mind there is still a limit to the input for the factorial function. For this reason you should use recursion wisely. As you learned now for the factorial problem, a recursive function is not the best solution.  For other problems such as traversing a directory however, recursion may be a good solution.