What is "recursion"

Recursion is what happens when a function invokes itself. Such functions are given the function name recursive.

Certain functional programming languages do not have loop (cycles, or loops), and rely only on recursion to perform an operation repeatedly. Similarly, in languages that have loops it is possible to eliminate recursive functions using loops.

So there are two ways to run a chunk of code repeatedly:

  • For iteration (using loops)
  • For recursion

Recursion may occur not only in code, but also in data structures; arrays or nested objects may contain references to an element already present in the structure.

Examples in some languages

C

void recursiveFunction(int num) {
   if (num < 4)
      recursiveFunction(num + 1);
   printf("%d\n", num);
}

C++

void recursiveFunction(int num) {
   if (num < 4)
      recursiveFunction(num + 1);
   cout<<num;
}

Java

public static int factorial(int N) { 
   if (N == 1) return 1; 
   return N * factorial(N-1); 
}

Haskell

factorial n = if n == 0 then 1 else n * factorial (n - 1)

References