Recursion

Recursion is a concept in programming wherein a function calls itself.

function recurse(parameter) {
  if (parameter==something) {
    return value;
  } else {
    parameter = something new;
    return recurse(parameter);
  }
}

As an example, consider factorials:

function factorial(number) {
  if (number < 2) {
    return 1;
  } else {
    return number*factorial(number-1);
  }
}

If you call factorial(4);, it will compute the number by calling itself with decreasing numbers until it hits 1:

factorial(4);
4*factorial(3);
4*3*factorial(2);
4*3*2*factorial(1);
4*3*2*1;

There is also an iterative way of solving this, of course:

function iterativeFactorial(number) {
  result = number;
  while (number>0) {
    number = number-1;
    result = result * number;
  }
  return result;
}

In general, all recursion can be written iteratively, though frequently recursion is the more concise way of writing a function.

Understanding more complex recursive functions can be tricky, and inexperienced programmers easily create infinite loops with recursion, as it adds a layer of abstraction to where precisely a function terminates.

Nonetheless, it's frequently considered the more readable option when picking between 'recursion' and 'iteration'.

Note that recursion comes with the downside of additional overhead, since function calls are stacked into memory. In the factorial example, factorial(4) adds 'factorial' to the function stack four times, whereas iterativeFactorial(4) adds 'iterativeFactorial' only once.