Recursion (computer science)

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. 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. — Niklaus Wirth, Algorithms + Data Structures = Programs, 1976

Author: enFelleisen, Findler, Flatt, and Krishnaurthi; enMatthias Felleisen; Niklaus Wirth
Comment: enIn computer science, recursion is a method of solving a computational problem where the solution depends on solutions to smaller instances of the same problem. 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. — Niklaus Wirth, Algorithms + Data Structures = Programs, 1976
Cs1Dates: eny
Date: enMarch 2020
Depiction
Has abstract: enIn computer science, recursion is a method of solving a computational problem where the solution depends on solutions to smaller instances of the same problem. 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. 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, 1976 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) do not define any looping constructs but rely solely on recursion to repeatedly call code. It is proved in computability theory that these recursive-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 while and for. 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 large problems, it is fundamental to use optimization techniques such as tail call optimization.
Hypernym: Method
Is primary topic of: Recursion (computer science)
Label: enRecursion (computer science)
Link from a Wikipage to an external page: books.google.com/books%3Fid=9pY4DwAAQBAJ&pg=PA1; books.google.com/books%3Fid=yCk2mWy9inMC; www.htdp.org/2003-09-26/Book/; archive.org/details/thinkingrecursiv00robe_0
Link from a Wikipage to another Wikipage: Accessor; Ackermann function; Adaptive quadrature; Algorithm; Algorithmic efficiency; Anonymous function; Anonymous recursion; Backus–Naur form; Big O notation; Binary search; Binary search tree; C (programming language); Call stack; Cambridge University Press; Category:Articles with example pseudocode; Category:Computability theory; Category:Programming idioms; Category:Recursion; Category:Subroutines; Category:Theoretical computer science; Clojure; Coinduction; Compiler; Computability theory; Computational problem; Computer program; Computer science; Control flow; Corecursion; CRC Press; Daemon (computer software); Data; Definition; Depth-first search; Divide-and-conquer algorithm; Divide-and-conquer method; Dynamic programming; E (mathematical constant); Euclidean algorithm; Exception handling; Expression (programming); Factorial; File:Recursive1.svg; File:Recursive2.svg; File:RecursiveTree.JPG; File:Tower of Hanoi.jpeg; Filesystem; Fold (higher-order function); For loop; Fractal; Function (computer science); Functional language; Functional languages; Functional programming; Functional programming language; Goto; Greatest common divisor; Haskell (programming language); Heap (programming); Hierarchical and recursive queries in SQL; How to Design Programs; Imperative language; Imperative programming; Infinite loop; Infinite loops; Insertion sort; Instance (computer science); Integers; Interpreter (computing); Iteration; Java (programming language); Kleene–Rosser paradox; Krauss matching wildcards algorithm; Lazy evaluation; Linked list; List (abstract data type); Logic; Lookup table; Loop variant; Macdonald & Co. (Publishers) Ltd.; Malware; Matching wildcards; McCarthy 91 function; Memoization; Memory management; Mergesort; Merge sort; MIT Press; Mutual recursion; Natural number; Natural numbers; Nested function; Newton's method; Niklaus Wirth; Open recursion; Order of magnitude; Parameter; Pass-by-reference; Pathological (mathematics); Perfect binary tree; Preorder traversal; Prime numbers; Primitive recursive function; Process (computing); Process state; Profiling (computer programming); Programmer; Programming language; Pseudocode; Python (programming language); Quicksort; Recurrence relation; Recursion; Recursive data type; Remainder; Rich Salz; Runtime environment; Scheme (programming language); Self reference; Series (mathematics); Short-circuit evaluation; Sierpiński curve; Software testing; Sorted array; Stack (data structure); Stack-based memory allocation; Stack buffer overflow; Stack overflow; Statement (programming); Stream (computer science); Structural induction; Tail call; Tail call elimination; Tail recursion; Tail-recursive; Tak (function); Termination analysis; Threaded binary tree; Tiled merge sort; Time complexity; Timsort; Tree (data structure); Tree traversal; Trivial (mathematics); Turing completeness; While loop; Wildmat; Wiley (publisher); Wrapper function; Μ-recursive function
SameAs: 2Ucr5; Algorisme recursiu; Algorithme récursif; Algoritmo ricorsivo; m.0bf6wn; Q264164; Recursie (informatica); Recursión (ciencias de computación); Recursion (computer science); Recursive algorithm; Recursividade (ciência da computação); Rekursiivinen algoritmi; Rekursiv algoritm; Rekursive Programmierung; Rekursive Programmierung; Rekurze (programování); Rekurzia (informatika); Đệ quy (tin học); Рекурзија (компјутерске науке); Рекурсивлă функци; Рекурсивная функция; Рекурсивті функция; Рекурсія (програмування); Ռեկուրսիա (ինֆորմատիկա); بازگشت (علوم رایانه); عودية (علم الحاسوب); पुनरावृत्ति (कंप्यूटर विज्ञान); 再帰; 递归 (计算机科学); 재귀 (컴퓨터 과학)
SeeAlso: Structural recursion
Source: enAdvanced Functional Programming, 2002; enAlgorithms + Data Structures = Programs, 1976; enHow to Design Programs, 2001
Subject: Category:Articles with example pseudocode; Category:Computability theory; Category:Programming idioms; Category:Recursion; Category:Subroutines; Category:Theoretical computer science
Text: enMany well-known recursive algorithms generate an entirely new piece of data from the given data and recur on it. HtDP (How to Design Programs) refers to this kind as generative recursion. Examples of generative recursion include: gcd, quicksort, binary search, mergesort, Newton's method, fractals, and adaptive integration.; enThe 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.; en[Functions that consume structured data] typically decompose their arguments into their immediate structural components and then process those components. If one of the immediate components belongs to the same class of data as the input, the function is recursive. For that reason, we refer to these functions as RECURSIVE FUNCTIONS.
Thumbnail
WasDerivedFrom: Recursion (computer science)?oldid=1123455633&ns=0
WikiPageLength: 58907
Wikipage page ID: 4044867
Wikipage revision ID: 1123455633
WikiPageUsesTemplate: Template:!; Template:About; Template:Algorithmic paradigms; Template:Anchor; Template:Cite book; Template:Cite journal; Template:CN; Template:Code; Template:Further; Template:How%3F; Template:Main; Template:Math; Template:Mvar; Template:Programming paradigms; Template:Quote; Template:Refbegin; Template:Refend; Template:Reflist; Template:See also; Template:Short description; Template:Sic; Template:Toclimit; Template:Use dmy dates; Template:Visible anchor

Recursion (computer science)

Backlinks

About

Resources

Support

Follow us