Questions tagged [recursion]
Questions about objects such as functions, algorithms or data structures that are expressed using "smaller" instances of themselves.
561
questions
1
vote
1
answer
119
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 ...
- 131
3
votes
0
answers
466
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 ...
- 31
1
vote
1
answer
230
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.
- 11
4
votes
1
answer
57
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 ...
- 143
1
vote
0
answers
563
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 ...
- 11
-1
votes
2
answers
65
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
0
votes
2
answers
51
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 ...
- 17
1
vote
2
answers
71
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 ...
- 113
3
votes
2
answers
309
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:
...
- 200
1
vote
2
answers
91
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 ...
- 153
0
votes
1
answer
84
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 ...
- 103
2
votes
1
answer
112
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
2
answers
3k
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 ...
- 123
1
vote
1
answer
50
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)
...
- 13
2
votes
1
answer
56
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: ...
- 23
1
vote
1
answer
70
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 ...
- 123
0
votes
1
answer
47
views
1
vote
1
answer
205
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 $...
- 13
-1
votes
1
answer
70
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,...
- 17
1
vote
1
answer
98
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 ...
- 21
3
votes
2
answers
60
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 = ...
0
votes
3
answers
526
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 ...
- 9
0
votes
0
answers
105
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, ...
- 177
2
votes
1
answer
2k
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 ...
- 123
1
vote
0
answers
165
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,
<...
- 11
-1
votes
1
answer
49
views
2
votes
2
answers
3k
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:
...
- 123
0
votes
1
answer
517
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 ...
- 101
2
votes
1
answer
54
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, ...
- 21
0
votes
0
answers
68
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
1
answer
53
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 ...
- 3
1
vote
1
answer
204
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 &...
2
votes
2
answers
1k
views
Minimum no. of coin flips (switch) needed so that all coins face the same side (Heads or Tails)
Consider this, I have n coins and I have placed them in a random order (1st coin is Head, 2nd is Tails etc.). You do not know the order. You can flip one coin at a time and then I tell you if all the ...
- 35
3
votes
1
answer
3k
views
Count total number of k length paths in a tree
This is a question from a competitive programming competition.
Given a tree with n nodes and a number k, find the total number of paths of length k in that tree.
I know for a fact that a solution can ...
4
votes
2
answers
673
views
Thought process to solve tree based Dynamic Programming problems
I am having a very hard time understanding tree based DP problems. I am fairly comfortable with array based DP problems but I cannot come up with the correct thought process for tree based problems ...
- 227
1
vote
0
answers
24
views
How to compute the general term formula for the number of full binary tree heaps that can be formed with distinct elements?
The number of possible heaps that are full binary trees of height $h$ and can be formed with ($n = 2^h - 1$) distinct elements can be computed by recursion:
$$ a_h = {2^h - 2 \choose 2^{h - 1} - 1} a_{...
- 145
2
votes
1
answer
664
views
Pseudo code of recursive method of printing all permutations of $n$ given integers
I really don't understand this pseudo code. The function prints all permutations of $n$ given integers, assuming that all numbers are different.
Is there a way to explain this code more easily as I ...
- 343
6
votes
1
answer
448
views
Struggling to understand the thought process required to come up with some recurrences for Dynamic Programming problems
I was doing a few dynamic programming problems and I am struggling to understand the thought process required to come up with recurrences.
The first problem I solved was longest palindromic substring ...
- 227
3
votes
1
answer
142
views
Find a threshold such that one function is always bigger than the other
Given the recursively defined function $c$:
$$c(m,n)=\begin{cases}0&\text{for }m=0\\
n^2+n+1&\text{for }m = 1\text{ and }n\ge 0\\
c(m-1, 1)&\text{for }m>1\text{ and }n=0\\
c(m-1,c(m,n-...
- 183
2
votes
1
answer
89
views
Deriving recursive definition from function specification
Given this function specification, where name xs is bound to a list, # denotes its cardinality and ...
- 125
1
vote
0
answers
153
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)$, ...
- 143
1
vote
0
answers
48
views
Finding the closed form of this recurrence
We have the following recurrence $T$:
$$
T(n,k) = \left\{
\begin{array}{ll}
\alpha n^2 + \beta n + \delta & \quad \text{if }\; n \le k \\
T(\lceil n / 2 \rceil, k)...
- 11
1
vote
0
answers
45
views
Hanoi towers recursive expression for EVERY algorithm
What the recursive algorithm for moving $n$ disks says, is:
If $n > 1$, move $n-1$ discs from A to B.
Move the $n$th disk from A to C.
If $n > 1$, move $n-1$ discs from B to C.
Let $T_n$ be ...
- 143
0
votes
1
answer
26
views
Recursive Call Inside Argument List (C++) [closed]
So, my professor asked me to implement recursion in different ways to compute $a^n$ (a and n being integers) and rank them according to their space efficiency. Now, here is one of the methods I came ...
- 11
0
votes
0
answers
261
views
Can every problem that uses recursion be solved using iteration? [duplicate]
We all know iterations and recursions are a powerful thing in programming. But this doubt always troubles me whenever I write an iteration or recursion. Can every recursive problem solved using ...
- 123
-4
votes
1
answer
99
views
How to find the substitutions that convert the starting sequence into the final sequence? CCC19J5
Here is Canadian Computing Competition 2019 Junior problem 5 on dmoj.ca. You can also see the original problem at cemc.uwaterloo.ca as well.
A substitution rule describes how to take a sequence of ...
- 43
1
vote
1
answer
51
views
Removing recursion from a function with multiple params
I am given the following function as a brain teaser:
...
- 121
2
votes
0
answers
320
views
Least constraining value heuristic in Sudoku [closed]
I was trying to implement Least Constraining Value Heuristic in Sudoku but wasn't getting the idea on how to do it. Can someone share their idea for the same ?
- 21
1
vote
0
answers
227
views
How to prove a recursive's function Big-Theta without using repeated substitution, master theorem, or having the closed form?
I have a function defined: $V(j, k)$ where $j, k \in \mathbb{N}$ and $t > 0 \in \mathbb{N}$ and $1 \leq q \leq j - 1$. Note $\mathbb{N}$ includes $0$.
$V(j, k) = \begin{cases} tj & k \leq 2 \\...
- 111
1
vote
2
answers
56
views
How can I show h(n) = O( √ n)?
Is there any way to make recursion tree that satisfies the height
$h(n) = h(n−\sqrt{n}) + 1$ to show $h(n) = O(\sqrt{n})$?
- 97