Last Updated:

Recursion in Python

Each program must perform some action and return the result. And what if to achieve the desired result you need to repeat the same action many times. How, using the python programming language, to force a computer to repeat a certain algorithm of actions? There is a solution – recursion.

Recursion is a function that calls itself a certain number of times. In some ways, recursion is similar to cycles, but there are a number of differences in it. After each iteration, the arguments in the recursive function may change or the function itself may be interrupted with a certain result. Can a loop do that? With great difficulty. In addition, recursion is performed in a separate function, and not in the body of the main code, which makes the program more structured.

Function arguments in Python

Here's an example of a recursive function for finding a factorial:

def factorial(n):

if n == 0:

return 1

else:

return n * factorial(n — 1) # 5 * 4 * 3 * 2 * 1 = 120

print(factorial(5)) # 120

 

What in this function is responsible for recursiveness? Notice the fifth line. The return operation calls the active function again, but with a different argument. This happens until n is equal to 0. After the condition n == 0 is triggered, which takes the program out of the function.

 

Why do we need conditions here at all, if it is enough just to prescribe return n * factorial(n - 1). The conditions act as a switch to complete the function. If they are not, then the function will get stuck in an infinite loop, and the program will give a recursion error.

Summary: Arguments in recursion are constantly changing. They are specified both in the body of the main code and in the return operation.

When to use recursion

On the Internet, disputes often arise about the choice between recursion and cycle. In any case, both options are suitable if you need to execute a certain piece of code several times. However, recursion has a number of advantages:

  1. In python, you cannot loop a program through a recursive function. A stack overflow will occur, and the program will throw an error. Next, we'll look at how to work around this error.
  2. The recursive function is more flexible. With the help of conditions and arguments, you can customize it in your own way.
  3. In some cases, recursion is faster than a cycle.
  4. Recursion is a function, and therefore can be called many times.

This is just a partial list of the benefits of recursion. The following are examples of problems that can be solved using recursion:

  1. Output numbers in a specific sequence
  2. Search for a factorial
  3. Sorting methods
  4. Sum of all digits
  5. Checking a Prime Number
  6. Find multipliers

In fact, the potential for recursion is much higher, and simple tasks for practice have been proposed above.

Increase the maximum depth of recursion

Python is a very thoughtful language. It will not allow the recursive function to be "accidentally" looped. What for? First, the looped function is infinite. The program won't even close. It's just hanging. Secondly, recursion goes beyond the stack, and this is one of the vulnerabilities that hackers abuse.

But sometimes it is still necessary to expand the boundaries of the depth of recursion. For example, when the result of a function goes out of the stack. To implement, we'll need to specify the following code snippet:

import sys

sys.getrecursionlimit() # learn recursion depth limitations

sys.setrecursionlimit(n) # change constraints to value n

But do not abuse this method, otherwise it can lead to unoptimized operation of the program.

Tree research with recursion

The following is a representation of the recursive factorial search function.

Recursion in Python

It is better to start reading from the bottom. Initially, the returned result (hereinafter 'n') is 1, but then another iteration is performed, in which n is multiplied by the next, in ascending order, number. That is, until we get to argument 5. Perhaps now you find it difficult to give this material. However, such trees allow you to manually analyze the progress of the program to identify the error.

Recipe for creating a function in Python

A function in python is created once, and can be called infinitely many times. The def keyword tells the interpreter that the function name and the function itself will go further. Example of a call:

deffuncName (args1, args2, args3):

#some code

return result

answer = funcName (args1, args2, args3)

However, there are times when it is not known how many arguments will be passed to the function. In this case, you must specify the * character before the last argument.

deffuncName (args1, args2, *args3)

Then all subsequent elements will be passed to the list with the name of the third argument. if some required arguments are not always passed to the function you can make them a default value

Example:

def Person (name, city = “New-York”):

print(“Hi,”, name, “you are from”, city)

Person(“Jake”, “London”) # Hi, Jake you are from London

Person(“Mia”) # Hi, Mia you are from New-York

With recursive functions, it's the same. Only a function call to return is added. The main thing is not to forget to add a condition under which the program will exit the function.

How and when recursion occurs

We analyzed the recursion from the programmer's point of view. But how does this happen in the python interpreter itself? When we work with a function, we allocate a separate memory space for it. The in-memory address of the function is placed in a special buffer called the stack. If you need to describe the stack, you can imagine a glass.

You pour water into it, which lies in a layer on the very bottom. After that, you add a little dense oil that lies on top of the water. This happens several times and in the end you have a glass with different layers. To pour water out of it, you will need to pour the top layer, then the next. That is, until you get to the water. In the stack, everything is exactly the same. The very first function is at the very bottom and ends with the most recent function, and the most extreme function ends with the first.

Stack overflow is the process where the glass runs out and the liquid is poured outside the walls. This is dangerous both for the program itself and for the user's data. We hope that this article has helped you in learning programming!