たとえば「硬貨のみを使って、ある額を支払うときに何通りの組み合わせがあるか」という問題の解きかたが面白い。Haskellだと

foo _ 0 = 1

foo _ s | s < 0 = 0

foo [] _ = 0

foo ca@(c : cs) s = foo ca (s - c) + foo cs s

みたいになる(走らせてないのでバグあるかも)のだけど、ある硬貨のセットによる支払いの組み合わせの総数は、「特定のどれかの硬貨を使った場合の組み合わせの数」と「それを使わない場合の組み合わせの数」を足したものってのが基本的な考えかたになる。で、「使う硬貨の種類が0種類になる」かまたは「支払うべき金額が0になる」ところで計算が終わる。