What Is Recursion? link

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(n-1)
  

Parts of Recursion link

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 link

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

Note: A factorial is defined only for non-negative 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(n-1) // recursive case
   }
}
  

output

  
factorial(4): 24
  

Explanation link

main function

• The main function is defined from line 2 to line 7.

  • 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 to line 16.

• 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(n-1) 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 from 1∗factorial(0). factorial(2) is calculated from 2∗factorial(1) This process n∗factorial(n−1)continues until the last value is freed from the memory stack