Time Complexity of Counting Change

Question

I have a similar problem to link: coin change algorithm in scala using recursion

The Code is recursive and looks like:

def countChange(money: Int, coins: List[Int]): Int = {
    def count(capacity: Int, changes: List[Int]): Int = {
            if(capacity == 0) 1
            else if(capacity < 0) 0
            else if(changes.isEmpty && capacity >=1 )0
            else count(capacity, changes.tail) + count(capacity - changes.head, changes)
    }
count(money, coins)
}

My Questions is how to analyze the time complexity of this algorithm? Thanks!

Answer 1

This is form of tree recursion which grow exponentially with input. SICP has very nice explanation about this.