flâneur

Object-Oriented Design and Data Structures

andrewcmyers.github.io · 3,846 words · saved by 1 readers

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

Recursion 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. Examples Let's start by looking at some simple examples of using recursion to solve problems. Recursively computing Fibonacci numbers 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…

related reading