ABSTRACT
Recursion is used extensively in combinatorics. Combinatorics, which is a subfield of mathematics that studies counting, and plays an important role in advanced algorithm analysis. This chapter focuses on recursive solutions to computational counting problems. Counting problem, whose goal consists of adding up a certain number of elements, entities, choices and concepts. A common strategy consists of grouping the items to be counted into several disjoint subsets, and adding the number of elements in each one. In terms of recursion, an original problem will be decomposed into several subproblems, and the result will be the sum of the outputs of those smaller problems. The chapter explains that several of the most widely used functions to illustrate recursion are associated with fundamental combinatorial concepts. For instance, the factorial, power, and binomial coefficients are related to permutations, variations (with repetition), and combinations, respectively. In addition, Fibonacci numbers arise in numerous combinatorial problems as well.
