Question

true or false

a)a recursion tree is a data structure that is used to avoid having to make recursive function calls.

b) The recursion tree is often used to create guesses for the substitution method of solving recurrences.

c) the master method can be used to solvve any recurrence.

Answer 1

Recursive functions are the functions which call itself directly or indirectly in a cycle of functional calls. They can be used to solve various problems but are inefficient at runtime.

Answers to your questions.

A. The answer is false. A recursion tree is a method through which u can visualize what's happening in recursion. It diagrams the tree of recursive calls and the amount of work done at each call. No where it indicates that this method avoids making recursive calls. An example of recursion tree is given below.

B. The answer is true. We generally use recursion trees to generate possible guesses at the runtime. These guesses are used by the substitution method to prove them since substitution method requires the input of guesses and then it proves by the concept of mathematical induction.

C. The answer is false. Various types of equations are not solved by the master method due to its certain limitations. For instance the below eqn.

can't be solved by this method since the difference between T(n/2) and n/log(n) is not a polynomial.

Please upvote. It takes a lot of effort to solve this problem.