# Questions tagged [recursion]

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

374 questions
Filter by
Sorted by
Tagged with
22 views

### Egg dropping problem binomial coefficient recursive solution

I have a question about the binomial coefficient solution to the generalization of the egg dropping problem (n eggs, k floors) In the binomial coefficient solution we construct a function $f(x,n)$, ...
18 views

### File Systems (Operating Systems)

The figure below depicts the structure of a simple inode-based file system. Each rectangle represents a disk block of some fixed block size. In respect to this diagram, I am asked: (a): Does this ...
23 views

49 views

### Is there purely recursive functions? [duplicate]

Is there any problem that can be only solved with recursion, and not with iteration? (haven't been able to find anything online). If there isn't any, is there a reason why? Thanks in advance!
40 views

### Computability: Proving a predicate is not recursively enumerable

Let P(p) <=> for each x, comp(p,x) is defined. Can anyone explain to me how to prove that P is not RE (recursively enumerable) ?
48 views

### Multiple choices for a single case in the recursive formula of a Dynamic Programming algorithm

I am developing a Dynamic Programming algorithm for a problem in scheduling. In the recursive formula, I have three cases: (1) $t_{i-1} = int$ (2) $t_{i-1} = app \quad \& \quad r(j) \leq p$ and (...
64 views

### Recursive definition for the length of a string?

I found a couple of answers online but I don't quite understand why the answer is right: The length of a string is: If a string has no characters, then its length is 0. Otherwise, the length of the ...
82 views

### Write the Brute Force Recursive Code to generate the longest substring containing k distinct vowels

Given a string s we have to find the length of the longest substring of s which contain exactly K distinct vowels. This is the problem statment given on geeksforgeeks Input : s = “artyebui”, k = 2 ...
89 views

### Avoiding “side effects” in recursive functions

I am writing a function to find the intersection between two sets. The non-functional requirements of the assignment include avoiding "side effects". ...
I was wondering how do I solve this, I've been trying any possible way to but I've failed: \begin{align*} T(n) &= T(n-1) +3n^2 - 2n +1 ,& n \ge 1 \\ T(0) &=2 &\\ \end{align*}
Typically, median of medians algorithm is written with groups of size $5$ or $7$ to ensure worst-case linear performance. The argument against groups of size $k=3$ is typically that we get a ...