What is Recurrence?

● The literal meaning of the word Recurrence means something that occurs again and again.
● In programming terms, recurrence is an equation or inequality that describes a function in terms of its value on smaller inputs.

For example, for binary search, we have to break the array into two halves again and again so the recurrence relation for that is :

T(n) = T(n/2) + 1

In this article we are going to solve recurrence relation with the help of the recursive tree method, let’s discuss what is the recursive tree is:
What is the Recursion Tree Method & How does it Work?

• The recursion-tree method converts the recurrence into a tree whose nodes represent the costs incurred at various levels of the recursion.
• This tree is a way of representing the algorithm’s iteration in the shape of a tree, with each node representing the tree’s iteration level.
• We use techniques for summations to solve the recurrence.

How does it work?

• We sum the costs within each level of the tree to obtain a set of per-level costs.
• Then we sum all the per-level costs to determine the total cost of all levels of the recursion.

Types Of Problem We can solve using the Recursion Tree Method:

• Cost Of Root Node will Maximum.
• Cost Of Each Level is Same.
• Cost Of Leaf Node Will be Maximum.

Examples For Every Form:
Cost Of Leaf Level Will be Maximum: T(n) = 2T(n-1) + 1

Step1: Draw a recursion tree according to the questions you want to solve.

Step2: Calculate the cost of each level

Ex2: Cost Same at each level : T(n)= T(n/2)+n
Step 1: Draw recursion tree

Step 2: Find the cost of each node and height of the tree

Time complexity : O(n* log2n).

Ex2: T(n) = T(n/2)
Step 1: Draw Recursion Tree

Step 2: Calculate cost & Height of Tree

Time Complexity: O(log2n).

Special thanks to Aishwary Rudra Chaturvedi for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article