Direct Vs. Indirect Recursion

This lesson explains two different types of recursion: direct and indirect recursion.

We'll cover the following

Direct Recursion

Direct recursion occurs when a function calls itself.

This results in a one-step recursive call: the function makes a recursive call inside its own function body.

Syntax of Direct Recursion

def function1(p1, p2, ..., pn) :
  # Some code here
  function1(p1, p2, ..., pn)
  # Some code here

Printing Natural Numbers from 11 to nn Using Direct Recursion

Let’s have a look at an example that prints natural numbers from 11 to nn:

Press + to interact
def printNaturalNumbers(lowerRange, upperRange):
  # Base Case
  if lowerRange > upperRange :
    return
    
  print(lowerRange)
  # Recursive Case
  printNaturalNumbers(lowerRange + 1, upperRange);
# Driver Code
n = 5
printNaturalNumbers(1, n)

In the above code snippet, if lowerRange is less than upperRange, we print the lowerRange, increase it and call the function again. But if lowerRange is greater than upperRange, we halt function calls.

The slides below show how function calls are being performed and then how all the functions return.

Indirect Recursion

Indirect recursion (or mutual recursion) occurs when a function calls another function, eventually resulting in the original function being called again.

For example, if function function1() calls another function function2() and function2() eventually calls the original function function1() - this phenomenon results in indirect recursion (or mutual recursion).

Syntax of Indirect Recursion

def function1(p1, p2, ..., pn) :
  # Some code here
  function2(p1, p2, ..., pn)
  # Some code here

def function2(p1, p2, ..., pn) :
  # Some code here
  function1(p1, p2, ..., pn)
  # Some code here

Printing Natural Numbers from 11 to nn Using Indirect Method

Let’s have a look at an example that prints natural numbers from 11 to nn:

Press + to interact
def printNaturalNumbers(lowerRange, upperRange) :
	if lowerRange <= upperRange :
	  print(lowerRange)
	  lowerRange += 1
	  helperFunction(lowerRange, upperRange)
	else :
		return
def helperFunction(lowerRange, upperRange) :
  if lowerRange <= upperRange :
    print(lowerRange)
    lowerRange += 1
    printNaturalNumbers(lowerRange, upperRange)
  else :
      return
# Driver Program 
n = 5
printNaturalNumbers(1, n)

In this code snippet, we have two functions: printNaturalNumbers() and helperFunction(). Both of them check if lowerRange is greater than upperRange. If not, then print lowerRange and call the other function.

This may not look like recursion, because a function is not calling itself. However, if we analyze the code flow, the first function always ends up calling itself indirectly.

printNaturalNumbers()−>helperFunction()−>printNaturalNumbers−>...printNaturalNumbers() -> helperFunction() -> printNaturalNumbers -> ...

Have a look at the code flow:

Now that you have understood the concept of direct and indirect recursion, let’s move on and find out when we should use recursion in the next lesson.