Introduction to Recursive Programming

CHAPTER 4

Linear Recursion I: Basic Algorithms

Do the difficult things while they are easy and do the great things while they are small. A journey of a thousand miles must begin with a single step.

—Lao Tzu

RECURSIVE methods can be categorized according to the number of times they invoke themselves in the recursive cases. This chapter examines methods that not only call themselves just once, but also process the output of the recursive call before producing or returning their own result. This common type of recursion is known as linear recursion, where the single recursive call is not the last operation carried out by the method. This chapter will present numerous problems and respective linear-recursive solutions that we will design by ...