Questions tagged [recursion]
Questions about objects such as functions, algorithms or data structures that are expressed using "smaller" instances of themselves.
579
questions
2
votes
1
answer
718
views
Running time of greedy scheduling algorithm
Here is an algorithm to output a subset of activities S such that no activities in S overlap and profit(S) is maximum.
Define $p[i]$ to be the largest index $j$ such that $a_j$ does not overlap $a_i$....
- 223
1
vote
2
answers
11k
views
Converting recursive algorithm to DP
As a follow-up to this question
, I've found a recursive algorithm that solves the given problem, but it runs too slow to pass all given tests.
...
- 260
2
votes
1
answer
475
views
Computing the minimal flexible distance of two vectors using dynamic programming
I can't figure out a recurrence equation for a dynamic programming assignment. Formally, we aim
to minimize the total sum of distances between matched points with the following constraints:
Every ...
- 21
0
votes
0
answers
73
views
4
votes
2
answers
538
views
Number of different binary search trees storing n distinct keys?
How many different binary search trees are possible that store the values 1,2,...,n ?
So far I found a recursive formula for the number (by case distinction what's at the root):
$ T(n) = 2T(n-1) + \...
- 143
0
votes
0
answers
34
views
Given the following code, array A and 2 indexes, find out by using substitution technique the $\Theta$
While setting left=0, right=n-1 and A an array of n numbers, find out the running time complexity in terms of $\Theta$. Firstly find out the recurrence and then evaluate it by using the substitution ...
- 141
13
votes
1
answer
4k
views
Is this a generic way to convert any recursive procedure to tail-recursion?
It seems that I've found a generic way to convert any recursive procedure to tail-recursion:
Define a helper sub-procedure with an extra "result" parameter.
Apply what would be applied to the ...
- 1,081
2
votes
1
answer
4k
views
What is the time complexity of binary sum (recursion) [duplicate]
Currently, I'm reading Data Structures and Algorithms in Java, 6 edition by Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser link, particularly a chapter about recursions.
There is an ...
- 21
1
vote
1
answer
2k
views
What is a recursion for Huffman encoding?
If I had to write the Huffman encoding as a recursion in terms of the cost $C_{ij}$, given weights/frequencies $W = [w_1,\ldots,w_n]$, how would I do it? (where this is creating a minimum cost tree, $...
- 219
3
votes
2
answers
1k
views
General method behind converting recursive inorder, preorder and postorder traversals of a binary tree to a non-recursive one?
I am reading both recursive and non-recursive using stack methods to implement inorder, preorder and postorder traversal of a binary tree at https://en.wikipedia.org/wiki/Tree_traversal#Depth-...
- 4,825
0
votes
1
answer
1k
views
What is the time complexity (upper bound) for this simple recursive function? [duplicate]
So I have function that I have written to return the maximum value between index i and index x of a given array using recursion as follows:
...
- 137
3
votes
0
answers
52
views
Termination of deterministic term rewriting
Consider a simple language:
$$t ::= plus ~ t ~ t ~ | ~ gen ~ t ~ | ~ except ~ N ~ t ~ | ~ N$$
with N constructors plus, gen and except, N being the natural numbers, and $G = \{t_n\}$ a finite, ...
- 610
1
vote
1
answer
323
views
Why is this problem listed as "Dynamic Programming"
I found a problem in the dynamic programming section of hackerrank but its not clear why dynamic programming should be used to solve it. The problem is as follows:
Nikita just came up with a new ...
- 171
0
votes
1
answer
776
views
Algorithm to build a "hand" calculation for riichi mahjong game
I would like to discuss an algorithm to build a "hand" calculation for riichi mahjong game.
I will simplify terms to focus on the algorithm and not on the game specific terms.
Let's imagine that we ...
- 103
0
votes
1
answer
736
views
Solution to the recurrence T(n) = 2T(n − 3) [duplicate]
We were asked the following question in our exam:
Solve or bound the recurrence T(n) = 2T(n − 3) for n>3 provided ...
- 101
6
votes
1
answer
20k
views
Can Breadth-First Search be Implemented Recursively without Data Structures?
I'm in a data structures course, but our current unit discusses recursion and not data structures, and I need to implement breadth-first recursion for the purpose of finding the shortest path through ...
5
votes
1
answer
1k
views
Algorithm to find maximum number of floors you can check with N eggs and D maximum drops
Question: You are given access to a multistory building. You have N eggs and are allowed D maximum drops from their window.
Rules: If a egg is dropped from window of floor F and it breaks, it will ...
- 390
2
votes
0
answers
52
views
Structural induction in non-local program transformation
Assume a functional language and a specialization operation (pulling out sub-expressions):
let f x y = (h 23 x) + (g 42 y)
becomes
...
- 610
1
vote
2
answers
39
views
Any option other recursive search possible to go from one 2d point to another point with fixed set of possible moves?
Problem: Given (a,b) and (c,d), find if you can you reach from (a,b) to (c,d) if we can only have the following moves
(a, b) to either (a+b,b) or to (a,a+b).
Example (1,4) to (5,9) is possible ...
- 390
0
votes
0
answers
9
views
Need Help solving Recurrence Problem [duplicate]
I have this practice problem that I was given.
I am trying to solve a specific recurrence equation
T(n) = 4 when n <= 2
T(n) = 3T(n/3) + 5 when n > 2
...
- 1
2
votes
1
answer
137
views
What kinds of problems are modeled by a recursive definition of a set of strings?
Given this definition:
The set $\Sigma^*$ of strings over the alphabet $\Sigma$ is defined recursively by:
BASIS STEP: $\lambda \in \Sigma^*$ (where $\lambda$ is the empty string)
RECURSIVE ...
- 495
1
vote
2
answers
2k
views
How to connect the math of recurrence relations to daily programming concepts
What exactly are we doing from a CS perspective when we solve a recurrence relation and find a resulting formula for a sequence given a set of initial conditions? I just went through the "linear ...
- 495
1
vote
2
answers
413
views
What is the relationship between tail recursion with other recursions?
I'm rather confused by the recursion theory.
From the link, the recursion theory was formed by Dedekind, Gödel and some other famous mathematicians. There are the following types of recursion. But ...
- 11
4
votes
1
answer
66
views
How to handle an undefined case with µ-recursive functions?
How to construct my proof and generally what should I aim to get when showing a function is $\mu$-recursive? Should I transform it in some of the basic functions using the given operators?
For ...
- 309
-1
votes
1
answer
132
views
How to show that certain summations are primitive recursive?
If we have a function $g\colon \mathbb{N}^{k+1} \to \mathbb{N}$ which is primitive-recursive. How to show that the function $f\colon \mathbb{N}^{k+1} \to \mathbb{N}$ with
$$f(x_1, \dots, x_k , x_{k+...
- 175
2
votes
2
answers
219
views
Efficient algorithm for getting from 1 to n with 3 specific operations
The question:
Given those 3 valid operations over numbers and an integer $n$:
add $1$ to the number
multiply the number by $2$
multiply the number by $3$
describe an efficient ...
- 722
0
votes
0
answers
87
views
Figure out recursive function for this problem
I'm trying to solve this problem whole day. The result should be dynamic programming algorithm but the first thing I need is to find out recurrent function.
There is N students (N is even) in class. ...
- 329
1
vote
1
answer
802
views
Side effect and recursion
My algorithm professor said a recursive function should not have side-effects since it's a methodological error because recursion is "pure".
Anyway I don't understand why, even because I find side-...
- 113
2
votes
1
answer
1k
views
How does recursion works when there are 2 or more consecutive recursive calls?
I was learning about recursion and i came across the following pseudo code for quicksort.
...
3
votes
0
answers
50
views
Axiomatisation in the presence of recursion
I read Klaus Havelund's thesis on the Fork Calculus:
http://havelund.com/Publications/thesis.ps
He develops the Fork calculus for reasoning about concurrent functional programs, the motivation being ...
- 359
0
votes
0
answers
29
views
T(n)=T(n-2)+T(n-3)+T(n-4)+2 is O(log n)? [duplicate]
how can i prove that T(n)=T(n-2)+T(n-3)+T(n-4)+2 is O(logn)?
or T(n)=T(n-1)+T(n-3)+1 the same..
when T(0)=1 T(1)=2 T(2)=3 T(3)=5 T(4)=8 etc`..
it's a Q about AVL-2 tree,the same rules of AVL tree ...
0
votes
1
answer
80
views
Converting a algorithm to a runtime function
I need to find an upper limit for the runtime of $f(n)$.
...
- 143
2
votes
1
answer
178
views
What Exactly is "Improvement" in Seed AI?
From LessWrongWiki, a seed AI
[I]mproves itself by recursively rewriting its own source code without human intervention.
Some would even say this could bring about an Intelligence Explosion. Many ...
- 323
20
votes
3
answers
18k
views
Why are loops faster than recursion?
In practice I understand that any recursion can be written as a loop (and vice versa(?)) and if we measure with actual computers we find that loops are faster than recursion for the same problem. But ...
- 1,006
6
votes
2
answers
1k
views
What is the formal justification for the correctness of the second formulation of rod cutting DP solution
CLRS on section 15.1 3rd edition has a good discussion of the rod cutting problem. I will add a description at the end of the question for reference.
Define $r_j$ to be the optimal way to cut a rod ...
- 2,960
3
votes
2
answers
15k
views
How is the complexity of recursive algorithms calculated and do they admit better complexity than non-recursive algorithms?
How are asymptotical time complexities calculated for recursive algorithms?
Recursive algorithms call themselves and therefore take up more space compared to non-recursive algorithms. But are they ...
- 129
2
votes
1
answer
329
views
Trying to understand this Dynamic Programming solution
The problem is as follows.
Minimize the sum of absolute differences between a matching of $n$ values from two sets, $A=\{a_1,a_2,\cdots, a_n\}$ and the set $B=\{b_1, b_2,\cdots, b_m \}$, with $n\leq ...
- 23
5
votes
2
answers
2k
views
Why does the recurrence equation for QuickSort consider all the elements in the array?
I have been taught that QuickSort has the following recurrence equation in the best case:
$T(n) = \begin{cases} c & \text{if } n=1 \\ 2\ T(\frac{n}{2}) + c \...
- 215
7
votes
2
answers
27k
views
How to calculate the mergesort time complexity?
Recently while reading a book (Skienna) I came across the following statement:
Mergesort works by dividing nodes in half at each level until the number of nodes becomes 1 hence total number of ...
- 199
1
vote
1
answer
378
views
Why Does the Deterministic Selection Algorithm Run in $O(n)$ and not $O(n\log n)$?
Here is pseudocode for the algorithm:
...
2
votes
4
answers
403
views
Problems understanding proof of smn theorem using Church-Turing thesis
I am reading Barry Cooper's Computability Theory and he states the following as the s-m-n theorem:
Let $f:\mathbb{N}^2\mapsto\mathbb{N}$ be a (partial) recursive function. Then there exists a ...
0
votes
1
answer
686
views
Longest double increasing subsequence (LIS variant)
I'll start with the definitions:Let $S = s_1s_2...s_n$ be a sequence of $n$ integers. A double increasing subsequence of $S$ is a sequence $P=p_1p_2...p_k$ (not necessarily continuous) where for each $...
- 385
1
vote
1
answer
74
views
Revisiting Fixed Point: What does it mean in the world of computer science?
A while ago I asked Fixed point, what does it mean in the world of computer science?
While the answers did help me to understand what Fixed point meant, the answers left me in a murky world when ever ...
- 5,091
2
votes
1
answer
949
views
How to treat $\epsilon$ and '$' in top-down predictive parsing (predict table)?
How to treat $\epsilon$ and '\$' in top-down parser using predict table?
The construction of the predict table
Given a product $X \rightarrow w$, row $X$ and column $t$
-Mark $X \rightarrow w$ ...
- 567
2
votes
1
answer
876
views
Complexity of dynamic card game algorithm
Consider the following dynamic card game with a regular deck of 26 red cards and 26 black cards. A dealer draws the unturned cards one by one, and we can ask him to stop at any time. For every red ...
- 123
-1
votes
1
answer
388
views
Complexity and Recurrence relation for Lowest Common Ancestor Binary Tree
I have written this solution for finding the Lowest Common Ancestor in a Binary Tree. Now I wanted to find the time complexity of this problem by solving via recurrence relation. Can someone suggest ...
0
votes
1
answer
1k
views
Print Binary Tree Diameter Path [duplicate]
Diameter of the tree is defined as a long path or route, between any two nodes in a tree. The path may or may not goes through the ROOT.
Print the Longest leaf to leaf path in a binary tree and its ...
- 163
2
votes
1
answer
789
views
primitive recursion in the lambda calculus
I am having trouble finding out what a primitive subset of the lambda calculus would look like. I reference primitive recursion as shown here: "https://en.wikipedia.org/wiki/...
- 459
9
votes
1
answer
543
views
What is the running time of this recursive algorithm?
I made the following (ungolfed) Haskell program for the code golf challenge of computing the first $n$ values of A229037.
This is my proposed solution to compute the $n$th value:
...
- 205
3
votes
2
answers
3k
views
Recurrence relations when function call is made inside loop
int fun (int n)
{
int x=1, k;
if (n==1) return x;
for (k=1; k<n; ++k)
x = x + fun(k) * fun(n – k);
return x;
}
What is the value of fun(5)?
I ...
