A difference in complexity between recursion and tail recursion

DOI10.1007/S00224-016-9673-5zbMATH Open1380.03038OpenAlexW2310420552MaRDI QIDQ519902FDOQ519902

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

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

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)

Cites Work

• Title not available (Why is that?)
• A simplified proof of \(DDL<DL\)
• Theory of program structures: Schemes, semantics, verification
• An infinite pebble game and applications
• Finite alogorithmic procedures and computation theories.
• A difference in expressive power between flowcharts and recursion schemes
• Algorithmic Procedures
• Title not available (Why is that?)
• Arithmetic complexity
• New Computational Paradigms

Cited In (2)

• Indexical translation of tail-recursive functions
• Title not available (Why is that?)

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)