Object-Oriented Design and Data Structures

Recursion is the definition of something in terms of itself. This sounds circular, but with care, recursive definitions can be a highly effective way to express both algorithms and data structures. Recursion allows us to solve a problem by using solutions to “smaller” versions of the same problem. The nth Fibonacci number is the sum of the previous two Fibonacci numbers. This is a recursive definition of a function f(n): To make this definition make sense, we need a base case that stops the recursion definition from expanding indefinitely: Since the recursive definition is always in terms of smaller values of 𝑛 , any given 𝑓 ( 𝑛 ) where 𝑛 ≥ 0 expands into smaller and smaller arguments until the base case is reached. For example: This recursive definition not only makes sense mathematically, it can be implemented in a direct way as Java code: This is very concise code, but not very efficient, as we'll see. An efficient algorithm for exponentiation known as “squaring and multipl

Object-Oriented Design and Data Structures Object-Oriented Design and Data Structures This space unintentionally left blank...loading To provide feedback or corrections, please use the GitHub repository .

related reading

• Foundations Of Data Structures And Algorithms | Pier Paolo Ippolitopierpaolo28.github.io
• How Not to Teach Recursionparentheticallyspeaking.org
• CSC 151 - Recursion over Numberseikmeier.sites.grinnell.edu
• how I think when I think about programming - alice mazalicemaz.com
• Reading 14: Recursionweb.mit.edu
• Reading 11: Recursive Data Typesweb.mit.edu
• adventures in uncertainty: An Introduction to Recursion Schemesblog.sumtypeofway.com
• The Design Recipefelleisen.org
• Structure and Interpretation of Computer Programsmitp-content-server.mit.edu
• Object-Oriented Design and Data Structuresandrewcmyers.github.io
• Reading 17: Recursive Data Typesweb.mit.edu
• Reading 17: Recursive Data Typesweb.mit.edu