Recursion

What Is Recursion?

Recursion is a method of function calling in which a function calls itself during execution.

There are problems which are naturally recursively defined. For instance, the factorial of a number $n$ is defined as n times the factorial of $n-1$.

factorial(n) = n * factorial(n-1)

Parts of Recursion

In terms of programming, a recursive function must comprise two parts:

• Base case

  A recursive function must contain a base case. This is a condition for the termination of execution.

• Recursive case

  The function keeps calling itself again and again until the base case is reached.

Example

The following example computes the factorial of a number using recursion:

Note: A factorial is defined only for non-negative integer numbers.