# Questions tagged [recursion]

Questions about objects such as functions, algorithms or data structures that are expressed using "smaller" instances of themselves.

593 questions
Filter by
Sorted by
Tagged with
28 views

### Hwo to solve the recurrence $T(n) = 4T\left(\frac{n}{2}\right) + \frac{n}{\lg n}$ in terms of $\Theta$?

I'm attempting to solve the recurrence relation: $$T(n) = 4T\left(\frac{n}{2}\right) + \frac{n}{\lg n}$$ in terms of its asymptotic behavior ($\Theta$), specifically using the first case of the ...
1 vote
20 views

### How to Solve the Recurrence Relation $T(n) = 8T\left(\frac{n - \sqrt{n}}{4}\right) + n^2$ in terms of $\Theta$?

The provided recurrence relation is as follows: $$T(n) = 8T\left(\frac{n - \sqrt{n}}{4}\right) + n^2$$ The goal is to express the solution in terms of the asymptotic notation $\Theta$. Unfortunately,...
123 views

### Expected runtime of recursive algorithm with optional part

I have a randomized recursive algorithm which expected running time is $T(n)$. In particular, the recursion looks like this: $$T(n) \leq \mathcal cn + R ,$$ where $R$ is a recursive term that depends ...
1 vote
93 views

### Recursive DFS Problem

I have been struggling with this contest problem for awhile now which is found at this link: https://people.eecs.berkeley.edu/~hilfingr/programming-contest/pacific-northwest/2009/b.pdf Short summary ...
79 views

...
112 views

### Making use of one function to recursively find n/3 of another

Given an algorithm M that computes the median of an array A in O(n) time, describe an O(n) algorithm to repeatedly call M in order to find the element of rank n/3 in A. This is a problem I am tasked ...
1 vote
118 views

### Understanding recursion tree for withdrawal formula

$$T(n) = T(n-a) + T(a) + cn$$ Now the solution says that the height of the tree $(h)$ is: $$h = \left \lfloor n/a \right \rfloor$$ And I don't understand why. Maybe I didn't understand the ...
69 views

### Is my mathematical representation of search in binary search tree correct?

You are given the root of a binary search tree (BST) and an integer val. Find the node in the BST that the node's value equals <...
1 vote
85 views

### Diffucuty in understanding code after a recursive call

This is an example algorithm of a recursive insertion sort I'm trying to understand. I've have tried understanding this with the help of print statements (which I've commented). ...
1 vote
132 views

...
1 vote
74 views

### Complexity of recursive function using Master theorem

this code aims to determine whether there exists a contiguous subarray starting from index 0 in the given array A whose elements sum up to the target value S. can we apply Master theorem to find out ...
93 views

### How to Remove Left Recursion from this Grammar?

How to remove left recursion in the following Grammar: S→Bb/a B→Bc/Sd/e Im new to this, below is the way I'm doing it: ...
1 vote
72 views

12k views

### Iteration can replace Recursion?

I've been seeing all over stack Overflow, e.g here, here, here, here, here and some others I don't care to mention, that "any program that uses recursion can be converted to a program using only ...
58 views

### Programs with feedback?

Suppose we have a program like this: ...