Questions tagged [recursion]
Questions about objects such as functions, algorithms or data structures that are expressed using "smaller" instances of themselves.
119
questions with no upvoted or accepted answers
5
votes
0
answers
54
views
The evolution of the term "recursive" from Goedel to Church to present day
I'm currently studying some of the history of computation / computability, in the early days known as recursion theory.
I see Goedel's definition of recursive functions seems significant in his paper,...
- 317
4
votes
0
answers
135
views
Why can't a programming language be both fully recursive and polymorphic
In my theory of computation class last Spring my professor said in passing that a programming language cannot be both fully recursive and polymorphic. I didn't think much of it till now? What does it ...
- 141
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
3
votes
0
answers
51
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
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 ...
- 325
2
votes
0
answers
59
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.
- 121
2
votes
0
answers
122
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 ...
- 21
2
votes
0
answers
109
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, ...
- 121
2
votes
0
answers
78
views
Reference request: Leaf-heavy master theorem algorithms
I know many algorithms that can be analyzed using master theorem, but the only algorithm I know where the time is dominated by the leaves is fast matrix multiplication.
Are there other recursive ...
- 152
2
votes
0
answers
60
views
number lesser than a given number composed of only binary numbers
Give a decimal number, such as 123. Need to figure out all smaller numbers lesser than 123 made up by ...
- 21
2
votes
0
answers
1k
views
Help with deterministic selection algorithm
All we know what is Deterministic Selection Algorithm:
Line up elements in groups of five (this number $5$ is not important, it could be e.g. $7$ without changing the algorithm much). Call each group ...
2
votes
0
answers
205
views
Recursive definitions, How it is done?
I read that recursive definitions, refer to the definition of a function in that function body, cannot be done in $\lambda$-calculus, but recursion can be achieved by using $Y$ combinator.
As I know, ...
- 1,072
2
votes
0
answers
212
views
Maximum Move in a maze
Given a N * N maze, and string of N,E,W,S denoting positions to move to. I need to determine how many moves are possible in sequence out of a string (containing these 4 letters only) from each cell as ...
- 21
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
2
votes
0
answers
54
views
Smarter recursion to compute #tilings of $m \times n$ board with small shapes that fit in $2 \times 2$ square?
This is a generalization of another question I posted because I wasn't clear that I cared about more than $2 \times 1$ dominoes (it's just a special case), and there is an explicit tractable formula ...
- 1,691
2
votes
1
answer
76
views
Runtime complexity of permutation function
I am trying to find the asymptotic run time complexity of the following function which will return a list of all permutations of nums.
...
- 21
1
vote
1
answer
103
views
Expected runtime of recursive algorithm with optional part
I have a randomized recursive algorithm which expected running time is $T(n)$. In particular, the recursion looks like this: $$ T(n) \leq \mathcal cn + R ,$$ where $R$ is a recursive term that depends ...
- 73
1
vote
0
answers
39
views
The complexity of Steinberg's strip-packing algorithm
In reading the paper "a strip-packing algorithm with absolute performance bound 2", the author gives a recursion formula $T(l)=T(l')+T(l'')+O(min\{l'\log{l'},l''\log{l'}',l\})$, where $l'+l''...
- 11
1
vote
0
answers
80
views
Recursive algorithm running time?
I would like your opinion on how to detect the T(n) (Running Time) for the following recursive algorithm.
Charm is an algorithm for discovering frequent closed itemsets in a transaction database. A ...
1
vote
1
answer
100
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 ...
- 21
1
vote
0
answers
90
views
1
vote
0
answers
16
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 ...
- 2,230
1
vote
0
answers
49
views
Is there a term for the inverse of a fixed-point operator?
When working with recursion it is often useful to find the least or greatest fixed points of a morphism, often using a fixed-point combinator. When working with recursion schemes, the inverse ...
- 11
1
vote
0
answers
97
views
Space usage of recursive functions with no return
Consider an algorithm for reversing a sequence given below:
...
- 135
1
vote
1
answer
87
views
Using inductive hypothesis on recurrence relation?
I have a recurrence relation as follows
$$T(n) = 2T(\lfloor n/2\rfloor) + n\log(n)$$
Using the induction hypothesis how do I obtain a relation $T(n)\leq E$ such that $E$ contains neither $T$ nor floor ...
- 11
1
vote
0
answers
199
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 "...
- 111
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
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
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
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
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
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
0
answers
55
views
How to solve 2 variable recursion?
T(m,n) = T(m-1,n) + T(floor(m/2), n-1)
Base conditions
T(m,n) = 1 when n = 0
T(m,n) = 0 when m < n
Edited: Below is the code for which I want to know the time complexity in terms of m and n.
<...
1
vote
0
answers
131
views
Is McCarthy Formalism first ever formalism for defining functions recursively in computer science?
McCarthy formalism is a formalism for defining functions recursively, first introduced in classic paper Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I (1960).
...
- 133
1
vote
0
answers
2k
views
Longest increasing subsequence (Dynamic Programming)
I have written the following recursive structure for finding length of longest increasing subsequence.
...
- 461
1
vote
0
answers
135
views
Knight's Tour Parberry algorithm: 4 knight's tour merge procedure
I'm implementing Parberry's algorithm for closed Knight's tour problem.
Brief idea of the algorithm: split the board in $4$ parts, find the tour on them recursively then delete $1$ edge in each part ...
- 111
1
vote
0
answers
95
views
A question on analysis of the time complexity of a recursive branching algorithm
I'm reading papers on algorithms of maximum independent problem and the basic recursive branching rules is as follows:
Let $G(V,E)$ be an $n$-node undirected, simple graph without loops, and $\...
- 632
1
vote
0
answers
29
views
Creating a self-affine fractal on L-systems
Hi I would like to create a self-affine fractal on L-Systems.
The axiom I have created is FF-GGG-GG-GGG++GGG+GG-GGG+GG+GGG+FF++ffGG+GGG+FF+GGG which creates the image below
At each stage I would like ...
- 11
1
vote
0
answers
858
views
Why do we count the ceils and floors in recursive functions?
When we solve the recursive functions using substitution method, the impact of ceil and floor functions is trivial when the size of the input is large enough. For example the answer of
$$
T(n) = T(\...
- 1,509
1
vote
0
answers
68
views
Why do we not store the min in any of the recursive clusters in a Van Emde Boas tree?
I was reading the chapter of van Emde Boas in CLRS (page 547 section 20.3 3rd edition) and it says:
Furthermore, the element stored in min does not appear in any of the recursive $vEB( \sqrt[\...
- 2,960
1
vote
0
answers
758
views
Finding the $k$th smallest element in union of two sorted arrays
I know that this problem is solvable in linear time with a merge but I want to get a sub-linear algorithm.
What I came up is that, if a[k] < b[k] then the $k$th ...
1
vote
0
answers
348
views
Can the Sieve of Eratosthenes be adapted to find twin primes
The Sieve of Eratosthenes is an algorithm generate the prime numbers, $2,3,5,7,11,13,...$ by drawing a list of numbers crossing out multiples of the smallest number in the list.
Is there anyway to ...
- 1,911
1
vote
0
answers
283
views
Using the μ (mu) operator
Problem
I've got this function:
$f(x,y)=(6-3\cdot x)\cdot(y+2)$, with $(x,y)\in\mathbb{N}^2$
Now I have to find $g=\mu f$.
Proposed solution
My solution was to find the smallest $n\in\mathbb{N}$ to ...
- 135
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
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
0
votes
0
answers
26
views
How to Remove Left Recursion from this Grammar?
How to remove left recursion in the following Grammar:
S→Bb/a
B→Bc/Sd/e
Im new to this, below is the way I'm doing it:
...
- 1
0
votes
0
answers
13
views
Finding a ArrayList Connection (representing Subway Lines) with Recursion
I have this ArrayList (called linArray) (and this only) that contains Subway exchange stations (first the station name and then the lines you can exchange to at that station):
...
0
votes
0
answers
25
views
Does a bijective function exists behind every recurrence relation?
Consider these 2 questions where recurrence relations can be applied:
Q1) Given an (nxm) where n denotes rows and m denotes columns of a grid, find the number of unique paths ($a_{n,m}$) that goes ...
