Introduction to Computational Thinking: Problem Solving, Algorithms, Data Structures, and More

© The Author(s), under exclusive license to APress Media, LLC, part of Springer Nature 2021

T. MailundIntroduction to Computational Thinkinghttps://doi.org/10.1007/978-1-4842-7077-6_8

8. Recursion

Thomas Mailund¹  

(1)

Aarhus N, Denmark

 

In this chapter, we consider an immensely powerful technique for solving problems: recursion. Recursion involves recognizing that a problem really consists of the same kind of problem, just on a smaller scale. For example, to sort n elements, we can first find the smallest, then sort all the others, and put them after the smallest. This is, in its essence, what selection sort does; we just didn’t explain it in these terms. When we do describe the algorithm like this, the recursive part is that we sort all but the smallest ...