Recursion in Python

Pre-requisite knowledge: Functions in python

You may already be familiar with the term "Recursion." As defined by Google, it refers to "the repeated application of a procedure or a definition." This concept holds true in programming, where it is utilized in functions.

A "Recursive function" refers to any function that invokes itself within its own body continuously until a specified condition is no longer true, at which point the desired task is completed; this process is known as "Recursion."

This article explores the concept of Recursion using Python functions.

To provide a brief overview of functions, we can consider the following example:

#To check if a number is even or odd.
def evenORodd(num):
	if(num% 2 == 0):
		print("num is an even number")
	else:
		print("num is an odd number")
evenORodd(2)

Output:

num is an even number

Understanding:

In this context, the function evenORodd has been created to determine whether the specified number, num, is classified as even or odd. We have established this function and incorporated the necessary logic within it. To ascertain whether the number 2 is even or odd, we invoke the function with 2 as the argument, which will substitute num, allowing the function to execute its logic accordingly.

When do we need to recurse a function?

When faced with a complex task, it is common practice to divide it into smaller, manageable tasks; executing these in succession alleviates the difficulty and reduces the overall complexity. Similarly, when tasked with coding for a complicated issue, we decompose it into smaller, repetitive components.

For a simple example:

A program must be developed to calculate the factorial of a given number. For instance, if the user inputs 6:

6! = 6 5 4 3 2 * 1

If we divide it:

6! = 6 * 5!

5! = 5 * 4!

4! = 4 * 3!

3! = 3 * 2!

2! = 2 * 1!

1! = 1

You can observe the repetition.

Formulating it:

N! = N * (N - 1)!

Thus, we define a function, referred to as factorial for N, that invokes itself with the argument N-1. This process continues until N reaches 1.

Recursion or Iteration

Loops are utilized to execute tasks repeatedly, while functions serve a similar purpose. What distinguishes the two, and how can one determine when to apply each?

The concept is straightforward. When utilizing loops, it is essential to determine the number of iterations required, particularly in the case of a for loop. If the iteration count is known, a for loop is appropriate. Conversely, if the number of iterations is uncertain, one may opt for while and do-while loops, or even Recursion. The choice depends on the specific requirements, and in certain scenarios, Recursion may be employed to obtain return values.

Diving deep into recursion:

Syntax:

def function_name(arguments if any):
		#function body
		function_name(argument) #recursive call of the function

Let us examine the program from the earlier code - the factorial of a number:

#function
def fact(num):
    if num == 1:
	return 1
   else:
           return (num * fact(num-1))
#Body of the program
num = int(input("Enter a number: "))
result = fact(num)
print("The factorial of the given number", num, "is", result)

Output:

Enter a number: 5
The factorial of the given number is 120

Understanding:

Fibonacci series:

The initial two numbers are 0 and 1. By continually summing the preceding two values, we can determine the subsequent number in the sequence. This progression of numbers is referred to as the Fibonacci series.

//To print the Fibonacci series till the given number of times
def fib(n):
	if num <= 1:
		return num
	else:
		return(fib(num-1) + fib(num-2))
num_terms = 10
if num_terms <= 0:
	print("The number of terms cannot be negative!!")
else:
	print("The Fibonacci series up to 10 terms:")
for i in range(num_terms):
	print(fib(i))

Output:

The Fibonacci series up to 10 terms:
0
1
1
2
3
5
8
13
21
34

Understanding:

We are required to generate the Fibonacci sequence up to 10 terms.

According to the loop in the program:

fib (0) = 0

fib (1) = 1

fib (2) = fib (1) + fib (0) = 1 + 0 = 1

fib (3) = fib (2) + fib (1) = 1 + 1 = 2

fib (4) = fib (3) + fib (2) = 2 + 1 = 3

fib (5) = fib (4) + fib (3) = 3 + 2 = 5

fib (6) = fib (5) + fib (4) = 5 + 3 = 8

fib (7) = fib (6) + fib (5) = 8 + 5 = 13

fib (8) = fib (7) + fib (6) = 13 + 8 = 21

fib (9) = fib (8) + fib (7) = 21 + 13 = 34

fib (10) = fib (9) + fib (8) = 34 + 21 = 55

We require a total of 10 digits, which can range exclusively from 0 to 9.

//Program to find certain power of a given number
def pwr(num, power):
	if power == 0:
		return 1
    	else:
		 return num * pwr(num, power - 1)
pwr(2, 6)

Output:

Understanding:

Say, for the same sample input-pwr(2, 6):

2 2 2 2 2 * 2

Breaking it down:

pow(2,6) = 2 * pow(2, 5)

pow(2,5) = 2 * pow(2, 4)

pow(2,4) = 2 * pow(2,3)

pow(2,3) = 2 * pow(2,2)

pow(2,2) = 2 * pow(2,1)

pow(2, 1) = 2

Thus, we invoke the function pwr(num, power) and subsequently call it again with pwr(num, power-1) until the power reduces to 1, at which point pwr(num, 1) equates to num itself.

Tail-Recursion:

A recursive function is referred to as tail-recursive if its final operation involves making a recursive call. In the context of tail recursion, the function solely returns a call to itself, without any additional processing.

Distinction between standard recursion and tail recursion:

Let us take an example:

Below is a program designed to compute the total of the initial "num" natural numbers:

def sum(num):
    if (num === 0):
        return 0
    else:
        return num + sum(num - 1)

What happens here is simply:

sum (5)

5 + sum (4)

5 + (4 + sum (3))

5 + (4 + (3 + sum (2)))

5 + (4 + (3 + (2 + sum (1))))

5 + (4 + (3 + (2 + (1 + sum (0)))))

5 + (4 + (3 + (2 + (1 + 0))))

5 + (4 + (3 + (2 + 1)))

5 + (4 + (3 + 3))

5 + (4 + 6)

5 + 10

The interpreter must retain the values of all variables and function calls until the conclusion of the program. It is essential for it to remember the value of num in order to continue multiplying during the recursive function invocation.

Now, look at this code:

def sum(num, total = 0):
   	 if (num === 0):
        		return total
     	else:
        		return sum(num - 1, total + num)

Mechanism here:

sum(5, 0)

sum(4, 5)

sum(3, 9)

sum(2, 12)

sum(1, 14)

sum(0, 15)

The interpreter does not have to retain the values of any variables that are outside the function calls. It can simply disregard them and focus on the recursive function calls. As illustrated, it solely returns a function call and nothing beyond that.

IT MATTERS BECAUSE:

Tail recursive functions can be optimized for efficient use by the compiler. In contrast, non-tail recursive functions lack the ability to be optimized in this manner by the compiler.

Upon executing recursive code, the compiler typically utilizes a stack to maintain values such as parameter values for each recursive invocation. With each recursive call, new values are pushed onto the stack. This process continues until the function concludes, at which point all values are subsequently popped from the stack.

In a non-tail recursive function, the stack depth increases since it requires the compiler to retain additional values. Conversely, in tail recursion, there is no necessity to maintain the stack frame of the current function call, allowing it to be removed from the stack.

As demonstrated in the preceding example involving natural numbers, we transform non-tail recursive functions into tail recursive functions to achieve optimization from the compiler.

Here is the factorial function converted:

#Non-tail Recursion
def Fact(num):
            if (num == 0):
                        return 1
            return num * Fact(num-1)

It might appear that this is a tail recursive function; however, it is not. The return statement includes an extra multiplication by num alongside the function call. For it to be classified as tail recursion, only the function call should be present in the return statement.

#Tail recursion
def Fact(n, recur_factval = 1):
                if (n == 0):
                           return recur_factval
               return Fact(n - 1, n * recur_factval)

The following code demonstrates a tail-recursive approach to compute the factorial of a specified number.

Advantages and disadvantages of Recursion:

Using Recursion is extremely useful in solving problems in data structures and stacks evolutions. But, at the same time, if the calls are not checked properly, the memory will be wasted a lot, and the computer might even run out of memory.

Recursion comes with its own set of benefits and drawbacks, and its application is determined by the specific requirements of the problem at hand. It serves as a significant and valuable tool in Python programming.