A difference in complexity between recursion and tail recursion

DOI10.1007/S00224-016-9673-5MaRDI QIDQ519902zbMATH OpenOpenAlexFDO

Authors Siddharth Bhaskar

Publication date 31 March 2017

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00224-016-9673-5

zbMATH Keywords

complexitylower boundsarithmeticabstract recursion theorytail recursion

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Abstract and axiomatic computability and recursion theory (03D75)

Recommendations

• Recursion versus tail recursion over \(\overline{\mathbb{F}}_p\)
• scientific article; zbMATH DE number 785053
• Tailoring recursion for complexity
• Ordinal complexity of recursive definitions
• Primitive recursion in the abstract

Cites work

• scientific article; zbMATH DE number 3622921 (Why is no real title available?)
• scientific article; zbMATH DE number 3390247 (Why is no real title available?)
• A difference in expressive power between flowcharts and recursion schemes
• A simplified proof of \(DDL<DL\)
• Algorithmic Procedures
• An infinite pebble game and applications
• Arithmetic complexity
• Finite alogorithmic procedures and computation theories.
• New Computational Paradigms
• Theory of program structures: Schemes, semantics, verification

Cited in

(3)

• scientific article; zbMATH DE number 1615259 (Why is no real title available?)
• Recursion versus tail recursion over \(\overline{\mathbb{F}}_p\)
• Indexical translation of tail-recursive functions

This page was built for publication: A difference in complexity between recursion and tail recursion

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q519902)