Data Structures Using Java

8

Recursion

Objectives

 An introduction to the concept of recursion

 Examples of recursively defined functions, such as factorials, the Fibonacci

sequence, the “3n + 1 function,” and the Ackermann function

 Use of recursion in program code, including binary divide-and-conquer algo-

rithms

 Recursion for computing permutations and combinations

 Recursion for gaming and search tree computation

 Dealing with memory use in recursion

Key Terms

3n +1problem

Ackermann function

binary search

Collatz problem

context

Fibonacci sequence

heuristic

objective function

recursive

Syracuse problem

Introduction

The concept of recursion is central to computer science. A standard ...