Primary
Recursion ○｜Definition｜1st｜20251119205401-00-⌔
Recursion (computer science) - Wikipedia
Recursion (computer science)
Snowflake pattern made using recursion
Honeycomb pattern made using recursion
Tree fractal created using the Logo programming language
Recursive drawing of a Sierpiński Triangle through turtle graphics
Examples made using recursion
In computer science, recursion is a method of solving a computational problem where the solution depends on solutions to smaller instances of the same problem.12 Recursion solves such recursive problems by using functions that call themselves from within their own code. The approach can be applied to many types of problems, and recursion is one of the central ideas of computer science.3
The power of recursion evidently lies in the possibility of defining an infinite set of objects by a finite statement. In the same manner, an infinite number of computations can be described by a finite recursive program, even if this program contains no explicit repetitions.
— Niklaus Wirth, Algorithms + Data Structures = Programs, 19764
Most computer programming languages support recursion by allowing a function to call itself from within its own code. Some functional programming languages (for instance, Clojure)5 do not define any built-in looping constructs, and instead rely solely on recursion. It is proved in computability theory that these recursion-only languages are Turing complete; this means that they are as powerful (they can be used to solve the same problems) as imperative languages based on control structures such as
whileandfor.Repeatedly calling a function from within itself may cause the call stack to have a size equal to the sum of the input sizes of all involved calls. It follows that, for problems that can be solved easily by iteration, recursion is generally less efficient, and, for certain problems, algorithmic or compiler-optimization techniques such as tail call optimization may improve computational performance over a naive recursive implementation.
Printed 2026-06-28.
(echo:: @ ᯤ)
Link to original Footnotes
Graham, Ronald; Knuth, Donald; Patashnik, Oren (1990). “1: Recurrent Problems”. Concrete Mathematics. Addison-Wesley. ISBN 0-201-55802-5. ↩
Kuhail, Mohammad A.; Negreiros, Joao; Seffah, Ahmed (2021). “Teaching Recursive Thinking using Unplugged Activities”. World Transactions on Engineering and Technology Education. 19 (2): 169–175. ↩
Epp, Susanna (1995). Discrete Mathematics with Applications (2nd ed.). PWS Publishing Company. p. 427. ISBN 978-0-53494446-9. ↩
Wirth, Niklaus (1976). Algorithms + Data Structures = Programs. Prentice-Hall. p. 126. ISBN 978-0-13022418-7. ↩
“Functional Programming | Clojure for the Brave and True”. www.braveclojure.com. Retrieved 2020-10-21. ↩
Secondary
• • •