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
0
votes
2answers
497 views

Making a recursive formula for finding amount of ways to spend money on beer

So far, i've only made recursive formulas for finding simple patterns such as fibonacci, however i can't seem to get my head around this. The information available is that there are $n$ different ...
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
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: ...
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
1answer
361 views

Merge sort and quicksort recursion tree depth

1) I need to determine recursion tree depth for strings composed of 10, 100 and 1000 elements when using merge sort. For the 10 elements one/I can do it on a paper, just drawing tree, but what about ...
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
2answers
1k views

How does in-order traversal in Binary search tree works (recursion)

I visit some question but their implementations are slightly different and my doubt is not like theirs. I have this code in Javascript. The code is typical BST implementation with methods to support ...
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 ...
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 ...
-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 ...
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 ...
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
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 ...
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 ...
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
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 ...
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
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 ...
3
votes
1answer
689 views

DP tiling a 2xN tile with L shaped tiles and 2x1 tiles?

https://www.iarcs.org.in/inoi/online-study-material/topics/dp-tiling.php The second question in the above link requires us to fill an 2xN grid with tiles of dimension 2x1 and an L shaped tile. ...
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: ...
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 ...
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
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 ...
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 ...
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 ...
1
vote
1answer
188 views

How to find the Big-O for finding combinations of balanced parentheses?

Given n pairs of parentheses, a function which returns the total number of all combinations well-formed parentheses could be: ...
0
votes
1answer
852 views

Prove Recursive formula (Dynamic programming) N(C,i)

I've been asked to prove the correctness of the following recursive formula. The formula is trying to define, how many ways you can spend your money C on the i amount of beers. I did the following ...
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
2answers
175 views

Pancake Sorting Graph Recursive Definition

I'm having trouble understanding exactly how the graph for Pn (where n = number of pancakes) is defined recursively for n>= 4. I can see obviously that, in the case of n=4, there will be 4 rough ...
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
vote
1answer
111 views

Recursion Time Complexity (Half n' Half)

This is my solution for Leetcode 395, and I'm wondering how I can come up with its time complexity: Input: string $s = s_1,\ldots,s_n$, integer $k$ Go over all symbols $s_1,\ldots,s_n$, one by one ...
-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,...
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 = ...
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
2 3 4 5
9