Questions tagged [recursion]

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

Filter by
Sorted by
Tagged with
1
vote
0answers
38 views

How do you write a python\pseudo code that generates all pair permutations?

What would be a good pseudo code or Python 3 code for the following permutations problem? Let us define a n-permutation as a bijective function $\pi: \{0,...,n-1\}\rightarrow \{0,...,n-1\} $ and ...
2
votes
0answers
88 views

How to prove νX. A × X ≅ (μX. 1 + X) -> A?

How can we prove Stream A = νX. A × X is isomorphic to Nat -> A = (μX. 1 + X) -> A ? In programming sense, ...
1
vote
1answer
36 views

How to solve recursion with two separate converges rates

What is the correct way to solve the following recursion: $T(n)=T(\lceil\frac{n}{2}\rceil) + T(n-2)$ Or basically any recursion that has two parts which converge in a different rate. I'm trying to get ...
0
votes
1answer
28 views

Is my recursive algorithm for Equivalent Words correct?

Here is my problem. Problem Given two words and a dictionary, find out whether the words are equivalent. Input: The dictionary, D (a set of words), and two words v and w from the dictionary. Output: A ...
-2
votes
1answer
38 views

How to calculate the minimum price required to buy all the stones?

I have shared the question above. My current algorithm does the calculation in O((n^4)*(2^n)). Can someone please help me out to solve this faster?
0
votes
0answers
41 views

Get the maximum sum of n items below a threshold

Consider a modified Knapsack Problem where: The number of items to be included is fixed. The value of each item is equal to its weight. Therefore, given a set of numbers, a threshold and the number ...
0
votes
1answer
29 views

How do I calculate the time complexity of this memoized algorithm?

The problem is: count all increasing subsequence of s. ...
0
votes
1answer
37 views

MAXSAT using dpll algorithm?

It's possible to return from a dpll algorithm M as maximum for MAX-SAT problem?: I have a sample: https://gist.github.com/davefernig/e670bda722d558817f2ba0e90ebce66f we can modify recurrency to return ...
1
vote
1answer
66 views

Any reason why Turing Machine would prevail on recursion theory?

Nowadays, most introduction books, videos, and comments about theoretical computer science talk about Turing machines but don't discuss recursion theory anymore. These approaches are known to be ...
0
votes
2answers
48 views

Analyzing space complexity of passing data to function by reference

I have some difficulties with understanding the space complexity of the following algorithm. I've solved this problem subsets on leetcode. I understand why solutions' space complexity would be O(N * 2^...
3
votes
1answer
57 views

Recurrence relation for the number of “references” to two mutually recursive function

I was going through the Dynamic Programming section of Introduction to Algorithms (2nd Edition) by Cormen et. al. where I came across the following recurrence relations in the context of assembly line ...
0
votes
1answer
29 views

What is the difference between these two Edit Distance Algorithm

Edit Distance is very well known problem in computer science. Came up with following algorithm after reading through CLRS but it doesn't work. Check the working algorithm below, I couldn't find why ...
1
vote
0answers
38 views

What is sideways recursion

A friend of mine is studying business analytics, currently on the topic for Microsoft DAX, but he is very new to the technological field. He mentioned yesterday, during a conversation, the term "...
0
votes
0answers
46 views

Big $O$ approximation for $T(n)=T(n-i)+T(n-(\frac{n}{m}-i))$

I have the following complexity equation: $T(n)=T(n-i)+T(n-(\frac{n}{m}-i))$ with the base case $T(m)=1$. Is it possible to calculate a big $O$ approximation for such equation? What is the right ...
2
votes
0answers
30 views

trouble solving the recurrence 4T(n/2) + n

I am having trouble figuring out how to solve this recurrence problem... $$ \begin{aligned} &4T(n/2) + n \\ = &4(4T(n/4) + n/4) + n \\ = &16T(n/4) + 2n \\ = &4^kT(n/2^k) + kn \end{...
1
vote
1answer
46 views

Arbitrary depth nested for-loops without recursion

Suppose I have an array of n values I want to apply nested for-loops over to an arbitrary depth m. ...
0
votes
0answers
27 views

Recursive multiplication

I was watching this video: https://www.youtube.com/watch?v=JCbZayFr9RE&list=PLXFMmlk03Dt7Q0xr1PIAriY5623cKiH7V&index=3 Honestly I do get most of it, except one. At 7:14 he starts talking ...
0
votes
0answers
24 views

Question regarding definition of recursive function

According to Wikipedia, and also a very common definition of a recursive function found in several books, "functions that call themselves from within their own code". I agree that this solves the ...
0
votes
1answer
92 views

Can the algorithm be optimized?

I am new to backtracking and recursion. I have seen numerous explanations on how on to find the minimum number of coins needed to make a particular amount. This involves a top down dynamic approach ...
2
votes
0answers
387 views

Facility location on a tree

Question: Given a tree representing a neighbourhood where each node is a house. Assign an antenna to each node such that the whole tree is covered. An antenna of strength 0 can only ...
1
vote
1answer
44 views

How to solve recursion T(n)=T(n/2)+T(n/3)+n?

How to solve recursion $T(n)=T(n/2)+T(n/3)+n$? I do not really know how to approach this kind of recurrence.
4
votes
1answer
47 views

Marginal Probability of Generating a Tree

Fix some finite graph $G = (V, E)$, and some vertex $x$. Suppose I generate a random sub-tree of $G$ of size $N$, containing $x$, as follows: Let $T_0 = \{ x \}$. For $0 < n \leqslant N$ i. Let ...
1
vote
0answers
42 views

Convert tree with recursive relationship to parent-child tree

Background: I have a .yaml file which holds around >3000 elements. The elements are related to each other through a recursive relationship. I want to create a tree view containing those items. A good ...
-1
votes
2answers
60 views

I am unable to understand the logic behind the code (I've added exact queries as comments in the code)

Our local ninja Naruto is learning to make shadow-clones of himself and is facing a dilemma. He only has a limited amount of energy (e) to spare that he must entirely distribute among all of his ...
0
votes
2answers
21 views

Turing Recursive Definition vs General Perception

So what confuses me is that let's consider a function f. According to a definition from a text book it asserts that f is called recursive, if there is a Turing machine that computes it (for all input ...
1
vote
2answers
39 views

Master Theorem applicable here?

Let $T(n):=\begin{cases} \frac{2+\log n}{1+\text{log}n}t(\lfloor\frac{n}{2}\rfloor) + \log ((n!)^{\log n}) & \text{if }n>1 \\ 1 & \text{if }n=1 \end{cases}$ I need to prove that $t(n) \in ...
2
votes
2answers
281 views

What does the phrase “Simple For Loops” mean in computability theory?

I was reading a Wikipedia page on Primitive Recursive Functions but there is a phrase for describing the simple for loops which I really don't understand. Can anyone explain this to me? The Phrase: ...
1
vote
1answer
26 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 ...
0
votes
1answer
32 views

How do I design a DP algorithm to count the minimum amount of continuous palindromic subsequences in sequence?

Taking a sequence, I am looking to calculate the minimum amount of continuous palindromic subsequences to build up such a sequence. I believe the best way is using a recursive DP algorithm. I am ...
2
votes
1answer
32 views

Is this an example of Tail Recursion

As I have read in this answer: What is tail recursion? tail recursion is a special case of recursion where the calling function does no more computation after making a recursive call. Here after the ...
2
votes
2answers
113 views

How to solve recurrence. T(n). = T(n-1) + T(n/2) + n?

I am aware that to get a running time by recursion tree method, we need to draw a tree and find: a) number of levels in tree. Since left side of tree decreases by 1 in size, so it's longest path ...
1
vote
1answer
25 views

Calculating complexity for recursive algorithm with codependent relations

I wrote a program recently which was based on a recursive algorithm, solving for the number of ways to tile a 3xn board with 2x1 dominoes: F(n) = F(n-2) + 2*G(n-1) G(n) = G(n-2) + F(n-1) ...
2
votes
1answer
29 views

Is there an algorithm to find the smallest set of the shortest prefix substrings of a continuous numeric sequence?

Before anything I want to preemptively thank anyone who drops by for their patience, I don't have any formal CS background so I'm probably going to use some of these terms wrong. I have a puzzle: ...
1
vote
1answer
36 views

Using Subset Sum algorithm $O(n)$ times to find the subset

Subset Sum is a well-known dynamic programming problem, which states that given a succession of numbers and a number, the algorithm determines if exists a subset that its sum is equal to the given ...
1
vote
1answer
44 views

Partition the indices of 2d array to minimize sum of sub-matrices

Given an $n\times n$ Matrix $M$, and the indices $[{1,2,3,4,...,n}]$ are divided into several intervals : $[1,x_1],[x_1,x_2],...[x_k,n]$, which further extract several squared sub-matrices along the $...
-1
votes
1answer
67 views

Merging $t$ arrays of size $t$ cannot be done in $O(t^2)$

Dr. John claims that he designed a comparison-based algorithm FastMerge that can merge $t$ arrays of size $t$ at most each in $O(t^2)$ time. In Dr. John’s own words, ”Given $t$ sorted arrays $B_1,B_2,...
1
vote
1answer
38 views

How to generate tree variants of a tree using recursion?

I have a tree T, I need to generate all possible variants of T by permuting all its child nodes(please refer the following figure). how can I generate all variants, T, using recursion? any help is ...
3
votes
2answers
51 views

Enumerate the terms resulting from decomposing a number by repeated divisions by 2

Consider a natural number $n>1$. We express it as $\lfloor \frac n 2 \rfloor + \lceil \frac n 2 \rceil$. We repeat the process for each of the two terms until all terms are 1 or 2. For example $9 = ...
1
vote
3answers
70 views

How many times in this pseudo-code is the function F called?

For this question, I thought function F called twice but it called three times. Are those three functions were called? F(N), F(K) and F(N-1)? How many times in this pseudo-code is the function F ...
0
votes
0answers
23 views

Iterative-substitution method yields different solution for T(n)=3T(n/8)+n than expected by using master theorem

I's like to guess the running time of recurrence $T(n)=3T(n/8)+n$ using iterative-substitution method. Using master theorem, I can verify the running time is $O(n).$ Using subtitution method however, ...
2
votes
1answer
163 views

Min-coin change problem with limited coins

I have been assigned the min-coin change problem for homework. I have to calculate the least number of coins needed to make change for a certain amount of cents in 2 scenarios: we have an infinite ...
1
vote
0answers
43 views

Find the fixed point of a recursive functional?

A functional is a function which takes another function as a parameter. The fixed point of a function is an input such that F(x) = x Given an example functional, <...
-1
votes
1answer
40 views

Recursive set for a string

Given the definition: ...
1
vote
1answer
234 views

Explanation of O(n2^n) time complexity for powerset generation

I'm working on a problem to generate all powersets of a given set. The algorithm itself is relatively straightforward: ...
0
votes
1answer
67 views

Cover interval with minimum sum intervals - DP recursion depth problem

READ ME FIRST: I have just found the official solutions online (have been looking for them for a while, but after posting this I quickly found it), and I'm currently trying to understand it. As I can ...
2
votes
1answer
33 views

Recurrence Relations

I am starting to learn recurrence relations in class and I am having issue with this example: T(N) = 2N - 1 + T(N-1) I am bit confused as to get the base case. I'm sorry if this seems elementary, ...
0
votes
0answers
54 views

How to show that a partial function is recursive?

I try to prove that this function is recursive: $$f(x_1,x_2)= \begin{cases} 2x_1-x_2 & \text{if $x_1 \geqslant \sqrt{x_2}$} \newline \bot & \text{otherwise} \end{cases}$$ I think that I need ...
0
votes
1answer
23 views

Converting a function with single parameter to a function with multiple parameters

I have been solving some algorithm questions recently and a pattern I have observed in some problems is as follows: Given a string or a list, do an aggregation operation on each of its elements. Here ...
1
vote
1answer
84 views

How to show that a $\log_2(x)$ is a recursive function?

I have a problem for the comprehension of how to prove that a function $ \log_2 : \mathbb{N} \rightarrow \mathbb{N}$ defined as: $$\log_2 (x)= \begin{cases} y & \text{if $x=2^y$} \newline \bot &...

1
2 3 4 5
9