Recursive function in python

by Alex
Recursive function in python

Recursion is not very easy to understand when you first get to know it, but without understanding it in development it will be hard. In this material we will look at:

  • A recursive function to find the factorial.
  • How recursive functions work in code.
  • Do recursive functions really perform better than iterative functions?

Recursive functions

A recursive function is one that calls itself. As a simple example, consider the following code:

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

By calling the recursive function here and passing an integer to it, you get the factorial of that number (n!).

Briefly about factorials

The factorial of a number is the number multiplied by every preceding number up to 1. For example, the factorial of the number 7: 7! = 7*6*5*4*3*2*1 = 5040 You can output the factorial of a number using the function:

num = 3
print(f "The factorial {num} is {factorial_recursive(num)}")

This function will output: “Factorial 3 is 6”. Consider this recursive function again:

def factorial_recursive(n):
...

Similar to a regular function, the name of the recursive function is given after def, and the parameter n is given in parentheses:

factorial_recursive(n):
if n == 1:
return n
else:
return n*factorial_recursive(n-1)

Due to the conditional construct, the variable n will return only if its value is 1. This is also called a termination condition. The recursion stops when the condition is satisfied.

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

In the code above a fragment of the recursion itself is highlighted. The else block of the conditional construction returns the product of n and the value of the same function with the parameter n-1. This is the recursion. In our example it works like this:

3 * (3-1) * ((3-1)-1) # since 3-1-1 is 1, the recursion has stopped

Details of how a recursive function works

To get an even better idea of how this works, let’s break down the process of executing a function with parameter 3 into steps. To do this, below we will present each instance with real numbers. This will help you “trace” what happens when you call a function with a value of 3 as an argument:

# First call
factorial_recursive(3):
if 3 == 1:
return 3
else:
return 3*factorial_recursive(3-1)
# second call
factorial_recursive(2):
if 2 == 1:
return 2
else:
return 2*factorial_recursive(2-1)
# third call
factorial_recursive(1):
if 1 == 1:
return 1
else:
return 1*factorial_recursive(1-1)

The recursive function does not know the answer for the expression 3*factorial_recursive(3-1), so it adds another call to the stack.

How recursion works

/\ factorial_recursive(1) - last call
|| factorial_recursive(2) - second call
|| factorial_recursive(3) - first call

Above shows how the stack is generated. It happens thanks to the LIFO (last in, first out) process. As you remember, the first function calls do not know the answer, so they are added to the stack. But as soon as a call factorial_recursive(1), for which there is an answer, is added to the stack, the stack begins to “unfold” in reverse order, performing all calculations with real values. In the process, each of the layers is dropped out in the process.

  • factorial_recursive(1) ends, sends 1 to
  • factorial_recursive(2) and drops off the stack.
  • factorial_recursive(2) terminates, sends 2*1 to
  • factorial_recursive(3) and drops off the stack. Finally, the else instruction here completes, returns 3 * 2 = 6, and the last layer falls off the stack.

Recursion in Python has a limit of 3000 layers.

>>> import sys
>>> sys.getrecursionlimit()
3000

Recursive or iterative?

What are the advantages of recursive functions? Is it possible to get the same result with iterative ones? When is it better to use one and when is it better to use the other? It is important to consider temporal and spatial complexity. Recursive functions take more memory space than iterative ones because of constantly adding new layers to the stack in memory. However, their performance is much better. Recursion can be slow if implemented incorrectly However, recursion may be slow if implemented incorrectly. This will cause calculations to occur more often than needed. Writing iterative functions often requires more code. For example, here is an example of a function for calculating a factorial, but with an iterative approach. It doesn’t look that elegant, does it?

factorial_iterative(num):
factorial = 1
if num < 0:
print("The factorial is not computed for negative numbers")
else:
for i in range (1, num + 1):
factorial = factorial*i
print(f "The factorial {num} is {factorial}")

Related Posts

LEAVE A COMMENT