In computer science, recursion is a method of solving a problem where the solution depends on solutions to smaller instances of the same problem. Such problems can generally be solved by iteration, but this needs to identify and index the smaller instances at programming time. 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

Property Value
dbo:abstract
• In computer science, recursion is a method of solving a problem where the solution depends on solutions to smaller instances of the same problem. Such problems can generally be solved by iteration, but this needs to identify and index the smaller instances at programming time. 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 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. (en)
dbo:thumbnail
dbo:wikiPageID
• 4044867 (xsd:integer)
dbo:wikiPageLength
• 58641 (xsd:integer)
dbo:wikiPageRevisionID
• 984715960 (xsd:integer)
dbp:author
• dbr:Niklaus_Wirth
• Matthias Felleisen (en)
• Felleisen, Findler, Flatt, and Krishnaurthi (en)
dbp:cs1Dates
• y (en)
dbp:date
• March 2020 (en)
dbp:source
• Advanced Functional Programming, 2002 (en)
• Algorithms + Data Structures = Programs, 1976 (en)
• How to Design Programs, 2001 (en)
dbp:text
• [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. (en)
• Many 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. (en)
• 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. (en)
dbp:url
dbp:wikiPageUsesTemplate
dct:subject
rdf:type
rdfs:comment
• In computer science, recursion is a method of solving a problem where the solution depends on solutions to smaller instances of the same problem. Such problems can generally be solved by iteration, but this needs to identify and index the smaller instances at programming time. 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 (en)
rdfs:label
• Recursion (computer science) (en)
rdfs:seeAlso
owl:sameAs
prov:wasDerivedFrom
foaf:depiction
foaf:isPrimaryTopicOf
is dbo:wikiPageDisambiguates of
is dbo:wikiPageRedirects of