Recursion for dummies

Russian Matrioska: The bigger contains itself but smaller.

What is recursion?

Recursion comes from the Latin ‘re’ that means ‘doing something again’, and ‘current that means ‘to run’.

It's something that happens again, something that is repeated, so the value of a function is defined by the application of the same function applied to smaller arguments.

Why use recursive functions?

• Avoid writing the same code many times
• Reduction of time complexity
• More clarity and less time to write the code.

Why NOT use recursive functions?

• It uses more memory.
• Can be slow, depending on the number of recursive executions.

For these reasons, it could be better to use an iterative approach with loops as for, while, and do-while.

https://www.freecodecamp.org/news/how-recursion-works-explained-with-flowcharts-and-a-video-de61f40cb7f9/

Examples

It can be used in mathematical functions as factorial, whose objective is to find the product of all the positive integers less than or equal to a number.

Let’s see how is the operation in natural language, python code, and the execution step by step.

Natural Language

5! = 5 x 4 x 3 x 2 x 1

Python code:

int factorial(n):
    # if the number sended to this function is equivalent to zero
    if (n == 0): 
        # the factorial is zero
        factorial = 1
    # if not
    else:
        # execute the function on the number less one
        # and multiply that for the actual number.
        factorial = n * factorial(n - 1)
    return factorial

Full execution step by step:

We replace the n for the number zero, and start the execution:

A color for each execution of the function factorial.

Now let’s see what’s happening in the memory of the system through the python tutor tool with the same code written in C:

The key of a recursive function is to think in different ways to subdivide a problem, looking for one in which the smaller parts have the same general structure as the original problem.

Finally, we need to create a condition that ends the series of recursive functions to avoid infinite loops.

About me

I am a passionate software developer from Holberton School and a Psychologist from the National University. During all my life I have been developing valuable professional skills as being a good listener, critical thinker, and team player. I have been consistently recognized as a very intelligent and empathic person. Whether on work or academic life I want to create meaningful experiences and inspire my partners. I am consistently dedicated, and curious.

If you want to create a connection with me, follow me on GitHub or Twitter.

I hope you enjoyed this reading, and thank you for your attention.

Made by Natalia Vera Duran.