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 nnn is defined as n times the factorial of n−1
factorial(n) = n * factorial(n1)
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 nonnegative integer numbers.
// main function
fn main(){
// call the function
let n = 4;
let fact = factorial(n);
// print the factorial
println!("factorial({}): {}", n, fact);
}
// define the factorial function
fn factorial(n: i64) > i64 {
if n == 0 { // base case
1
}
else {
n * factorial(n1) // recursive case
}
}
output
factorial(4): 24
# Explanation
main function

The main function is defined from line
2
to line7
.
On line
4
, a call is made to function factorial with an argument passed to the function and the return value is saved in the variable fact. 
On line
6
, the value of the variable fact is printed, i.e., the factorial of the number being passed as an argument.


factorial function
 The factorial function is defined from
line 9
toline 16
.
 The factorial function is defined from

function definition
 The function takes a parameter n of type i64.

function body

The recursive function is made up of two parts.

base case

On line 10, the base case is defined. Since the value of n is decremented in every recursive function call, the function terminates when the value of n becomes equal to 0 on successive recursive calls.


recursive case

On line 14, the recursive case is defined. The value n gets multiplied with factorial(n1) and gets pushed on the memory stack. Since the value of n is decremented in every function call, the function keeps on calling itself repeatedly until the base case is reached. As soon as the base case is reached, factorial(0) is calculated and the value is used in the immediate expression in the memory stack. The
factorial(1)
is calculated from1∗factorial(0)
. factorial(2) is calculated from2∗factorial(1)
This processn∗factorial(n−1)
continues until the last value is freed from the memory stack