Analysis of the recurrence algorithm T (n) = T (n - 1) + T (n - 2) + c?

Question

I know that this type of equation can be solved by many methods, but I want to use to use the recursive tree method to solve the equation. Can someone show me how to do this using the recursive tree method?

Answer 1

Recursion trees are used to extend the execution of a recursive algorithm. This repetition that you describe basically matches the Fibonacci recursive algorithm, where is this equation:

F(n) = F(n-1) + F(n-2)

It is solved recursively using the following algorithm:

int fib(int x) {
    if (x == 0)
        return 0;

    if (x == 1)
        return 1;

    return fib(x-1)+fib(x-2); //Does this recurrence look familiar?
} 

What creates this tree for input 5:

                    5
                   / \
                  /   \
                 /     \ 
                /       \     
               /         \
              /           \
             /             \
            4               3
           / \             / \
          /   \           /   1
         /     \         2
        3       2       / \
       / \     / \     1   0
      /   \   /   \  
     2     1 1     0
    / \
   /   \
  1     0

, . (5) . , N, 2, O (2 ^ n). , , , .