Register to get access to free programming courses with interactive exercises

Recursions Python: Functions

To understand recursion, one must first understand recursion. Recursion in programming is an opportunity to define a function using its definition.

Mathematics defines it this way, which is why most programming languages adopt this approach. Python is no exception here: usually, you can only use definitions given earlier in the function body. But there is one exception, a function can call itself in its body. It looks like this:

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

https://replit.com/@hexlet/Python-functions-recursion-factorial#main.py

This function calculates the factorial of the number n by multiplying the number by the factorial of the number n - 1.

Recursions as termination conditions

The example demonstrates a condition that terminates the recursion. The first call to this function will cause the program to loop if you remove it in this function that checks that the argument is not negative. The function will continue to call itself again and again.

There is almost always a similar condition in the definitions of recursive functions. It allows the calculation to go along one of two branches:

  • Either recursive, where the function calls itself sometimes multiple times
  • Or terminal, which will terminate the function and return the result

There is a rule — some of the arguments of a recursive function must always decrease.

Decreasing can mean lowering the counter, dropping the head of the list when moving to its tail, or the function calling itself part of the original structure when processing tree-like data structures.

Unfortunately, it is generally only possible to tell that a program will not loop by staring at it and using tests. It is essential to check that the recursion termination condition gets triggered.

Stack overflows

In most programs written in languages that support function calls, this very call goes as follows:

Sign up

Programming courses for beginners and experienced developers. Start training for free

  • 130 courses, 2000+ hours of theory
  • 1000 practical tasks in a browser
  • 360 000 students
By sending this form, you agree to our Personal Policy and Service Conditions

Our graduates work in companies:

<span class="translation_missing" title="translation missing: en.web.courses.lessons.registration.bookmate">Bookmate</span>
<span class="translation_missing" title="translation missing: en.web.courses.lessons.registration.healthsamurai">Healthsamurai</span>
<span class="translation_missing" title="translation missing: en.web.courses.lessons.registration.dualboot">Dualboot</span>
<span class="translation_missing" title="translation missing: en.web.courses.lessons.registration.abbyy">Abbyy</span>
Suggested learning programs
profession
new
Developing web applications with Django
10 months
from scratch
under development
Start at any time

Use Hexlet to the fullest extent!

  • Ask questions about the lesson
  • Test your knowledge in quizzes
  • Practice in your browser
  • Track your progress

Sign up or sign in

By sending this form, you agree to our Personal Policy and Service Conditions
Toto Image

Ask questions if you want to discuss a theory or an exercise. Hexlet Support Team and experienced community members can help find answers and solve a problem.