one way to describe repetition within computer program is the use of loopssuch as python' while-loop and for-loop constructs described in section an entirely different way to achieve repetition is through process known as recursion recursion is technique by which function makes one or more calls to itself during executionor by which data structure relies upon smaller instances of the very same type of structure in its representation there are many examples of recursion in art and nature for examplefractal patterns are naturally recursive physical example of recursion used in art is in the russian matryoshka dolls each doll is either made of solid woodor is hollow and contains another matryoshka doll inside it in computingrecursion provides an elegant and powerful alternative for performing repetitive tasks in facta few programming languages ( schemesmalltalkdo not explicitly support looping constructs and instead rely directly on recursion to express repetition most modern programming languages support functional recursion using the identical mechanism that is used to support traditional forms of function calls when one invocation of the function make recursive callthat invocation is suspended until the recursive call completes recursion is an important technique in the study of data structures and algorithms we will use it prominently in several later of this book (most notably and in this we begin with the following four illustrative examples of the use of recursionproviding python implementation for each the factorial function (commonly denoted as !is classic mathematical function that has natural recursive definition an english ruler has recursive pattern that is simple example of fractal structure binary search is among the most important computer algorithms it allows us to efficiently locate desired value in data set with upwards of billions of entries the file system for computer has recursive structure in which directories can be nested arbitrarily deeply within other directories recursive algorithms are widely used to explore and manage these file systems we then describe how to perform formal analysis of the running time of recursive algorithm and we discuss some potential pitfalls when defining recursions in the balance of the we provide many more examples of recursive algorithmsorganized to highlight some common forms of design