Introduction to Recursion

Learn basic concepts of recursion.

Introduction

Recursion is a technique where a function calls itself. Such functions are called recursive functions.

Unlike loops, recursive calls do not simply repeat one after another. Instead, each call creates a new layer of work, and the function continues solving smaller versions of the same problem until it reaches a simple case that can be answered directly.

This simple case is called the base case.

Factorial

Let us start with the factorial function.

We know that:

• $0! = 1$
• for $n > 0$, we have $n! = n \cdot (n-1)!$