Recursion

Recursion is a method of solving a problem by having a procedure call itself on smaller versions of the same problem until it reaches a simple case that can be answered directly, called the base case. A standard example is the factorial of a number: the factorial of 5 is 5 times the factorial of 4, and so on down to 1. Many algorithms for searching and sorting data are naturally recursive, as are tree-shaped data structures such as the Merkle tree, where each node's hash is built from the hashes of the nodes beneath it. A recursive function without a reachable base case runs until it exhausts memory. In blockchains, "recursive proofs" are zero-knowledge proofs that verify other proofs, allowing many transactions to be compressed into one small proof.