# Questions tagged [recursion]

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

515 questions
Filter by
Sorted by
Tagged with
35 views

### form sub-array from an array

I have an array A = (0,1,0,1,1,2,0,1) where A[i] = (1.....n). I need to find intervals of array index which contain all three numbers {0,1,2} i.e the above array can have many sub-arrays. If we ...
30 views

### How can we get upper bound in terms of Big Oh notation using Master theorem?

The recursion is: T(n) = 5T(n/2) + O(n) I solved for the time complexity using Master theorem and found Θ(n^2). but, the question has asked to find the upper bound ...
39 views

### How does primitive recursion handle mutual recursion?

My intuition is that you can't call a function that has not yet been defined, although I have yet to find a source confirming this. Is this true? Thanks, friends :)
33 views

### Solving $T(n) = T(0.01n) + T(0.99n) + cn$ [duplicate]

How to solve the below relation? $$T(n) = T(0.01n) + T(0.99n) + cn$$ This will not be a balanced tree. For $k$ levels I have something like $\bigl(\frac{1}{100} + \frac{99}{100}\bigr)^k \cdot cn$. I ...
17 views

### understanding or recurrence relations in code

I have a piece of code as below ...
23 views

### Recursive Bijections Between Countably Infinite Sets

The textbook I am currently studying (Introduction to Kolmogorov Complexity and Its Applications by Li and Vitanyi) uses the term 'recursive bijection'. In this context I believe that recursive refers ...
59 views

### Is top-down dynamic programming always recursive?

I think top-down dynamic programming is mostly recursive (at least when we use memoization). For instance, solving the rod-cutting problem by this algorithm: ...
60 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 ...
44 views

### Are recursion and a stack equivalent in terms of inplementing DFS?

It is well known that DFS can be implemented either with recursion or a stack, and that both approaches are equivalent, but how far can we take that statement? Consider the following LeetCode problem: ...
50 views

### is there a theory consider on infinitely many recursion?

of course there is a theory that how many recursive calling the same system to solve problems, this theory is "recursion theory", If i know correctly. and recursion theory is computability ...
41 views

### How to convert any recursive solution to a Dynamic programming table? Is there any tricks/tips to follow?

I've been able to form a recurrence relation with memoization in a recursive approach for most problems but the online coding rounds exceed the time limit or stack overflow occurs in all these ...
26 views

### Recursive Prefix-Sums K times

I have been wondering about the following question for quite some time: You are given an array $x$. Define f(x) as the prefix sums of this array. For example, f([1,0,1]) = [1,1,2] and f(f([1,0,1])) = [...
52 views

### Tic-Tac-Toe in PSPACE

Why is a game like Tic-Tac-Toe in PSPACE? For example for a nxn grid you have nxn! possible game tree paths (duplicates and illegal moves aside), then don't you need (n^2)! memory slots?
35 views

### What are the fixed-points of the Y combinator?

Since the Y combinator itself is a function (albeit a higher-order one), I was wondering what the fixed-points of Y itself are.
71 views

### Multiplying two integers by dividing each into 3 parts

Integer Multiplication: $x$ and $y$ are two n-bit integers, where $n=3^k$ for some $k>0$. We break $x$ into three parts $a$, $b$, $c$, each with $n/3$ bits; and $y$ into three parts $d$, $e$, $f$, ...
656 views

### Is there a better way to optimize my algorithm for maximizing order volume?

I'm trying to find an efficient algorithm to solve the following ... During the day, a supermarket will receive calls from customers who want to place orders. The supermarket manager knows in advance ...
40 views

### Question on Erickson 'momselect' algorithm

In the Erickson Algorithms textbook (file:///C:/Users/G068078/OneDrive%20-%20Kaiser%20Permanente/Algorithms_Technique_and_Theory_CS_388G/Undergraduate_CS331/Algorithms-JeffE.pdf) it has pseudocode for ...
85 views

### Recursion analysis using Master Theorem

I have the following algorithm: ...
39 views

### Calculate the number of "count inversions" of sub arrays

Recently, I encountered the following problem: Given an array $A$ of length $n$ $(0\le n\le 2^{17})$. Let $f(l, r, x)$ denotes the number of occurrences of $x$ in the subarray $a[l\ldots r]$. Find ...
52 views

### Total work done at a recursion tree level

In the proof of Master theorem in Dasgupta's Algorithms the author says that the total work done at a recursion tree level is $$a^k \times O\left(\frac{n}{b^k}\right)^d$$ where $a$ is the branching ...
43 views

### Solve $\sum_{i=0}^{\log_3 n-1}i\times 3^i$

I want to find the answer for $$\sum_{i=0}^{\log_3 n-1}i\times 3^i$$ Can you please explain? I this a geometric series?
36 views

### How to prove that this language is not recursive enumerable?

I need to prove that the following language is not recursively enumerable, while its compliment is recursive enumerable: $L := \{w \in \{0,1\}^* |$ TM $M$ with $w = \langle$ M $\rangle$ does not ...
11 views

### Heuristics to transform a recursively enumerable set into a diophantine set

The class of recursively enumerable sets is equal to the class of Diophantine sets. Given a recursive function, is there a way to produce a diophantine equation such that the trace of calls to the ...
37 views

### Are the definitions of loop in CS and in programming (standard/common) identical?

Are the definitions of loop in CS and in programming (standard/common) identical? If not, what is the main difference / what are the main differences?
238 views

### Why is there no "traditional"-mathy way to describe the general algorithm and give a more math-friendly definition of algorithm?

Why is there no algebraic definition of algorithm besides recursive functions? If I'm wrong, what is the matheist definition of algorithm that you've ever seen in a paper and can you provide a link? ...
28 views

### Recursive approach of longest common subsequence

I tried to solve Longest common subsequence problem using recursion, however as I later discovered, my thinking approach was wrong. I took 2 strings say s1 and s2 with lengths l1 and l2, s1="...
39 views

### How to perform AND on binary "recursive repeating sequences"?

Suppose, we have a two binary sequences, encoded as "recursive repeating sequences" (I don't know exactly how to name them). Each sequence can contain other sequences and has number related ...
21 views

30 views

### Back Substitution Method for solving recursive equation

Does back substitution method work for any recursive equation? If not is there any generalized form for recursive equation?