Questions tagged [recursion]

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

127 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
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,...
Greg Peckory's user avatar
4 votes
0 answers
139 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 ...
Michael Chav's user avatar
3 votes
0 answers
487 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 ...
billo's user avatar
  • 31
3 votes
0 answers
53 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, ...
choeger's user avatar
  • 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 ...
Gergely's user avatar
  • 379
2 votes
0 answers
78 views

Implementation of the divide-and-conquer principle for a specific summation formula

I have found two formulas in the work on pages 5 and 6, of which I am trying to develop a recursive implementation. The similarity to the DFT or FFT might be useful here. I divide this question into ...
TreeBook1's user avatar
2 votes
0 answers
61 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.
brj's user avatar
  • 121
2 votes
0 answers
137 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 ...
Yoav's user avatar
  • 21
2 votes
0 answers
110 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, ...
inamiy's user avatar
  • 121
2 votes
0 answers
86 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 ...
user2316602's user avatar
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 ...
user3053970's user avatar
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 ...
letotyrazdeta's user avatar
2 votes
0 answers
206 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, ...
alim's user avatar
  • 994
2 votes
0 answers
218 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 ...
sammy's user avatar
  • 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 ...
choeger's user avatar
  • 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 ...
user2566092's user avatar
  • 1,721
2 votes
1 answer
162 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. ...
user1234's user avatar
1 vote
1 answer
83 views

Diffucuty in understanding code after a recursive call

This is an example algorithm of a recursive insertion sort I'm trying to understand. I've have tried understanding this with the help of print statements (which I've commented). ...
river_bell's user avatar
1 vote
0 answers
52 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''...
Twilight7's user avatar
1 vote
0 answers
81 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 ...
Danilo Giovannico's user avatar
1 vote
0 answers
92 views

Recursion analysis using Master Theorem

I have the following algorithm: ...
Mouvre's user avatar
  • 131
1 vote
0 answers
51 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 ...
Etherian's user avatar
1 vote
0 answers
114 views

Space usage of recursive functions with no return

Consider an algorithm for reversing a sequence given below: ...
GilbertS's user avatar
  • 135
1 vote
1 answer
100 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 ...
Jon Anderson's user avatar
1 vote
0 answers
241 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 "...
pinpinokio's user avatar
1 vote
0 answers
717 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 ...
Simon Pio.'s user avatar
1 vote
2 answers
118 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 ...
Alon's user avatar
  • 153
1 vote
0 answers
229 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, <...
user116456's user avatar
1 vote
0 answers
27 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_{...
Shreck Ye's user avatar
  • 145
1 vote
0 answers
164 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)$, ...
entechnic's user avatar
  • 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)...
pylab's user avatar
  • 11
1 vote
0 answers
49 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 ...
entechnic's user avatar
  • 143
1 vote
0 answers
268 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 \\...
user12055579's user avatar
1 vote
0 answers
57 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. <...
Prarthit Mehra's user avatar
1 vote
0 answers
140 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). ...
Siegmeyer's user avatar
  • 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. ...
shiwang's user avatar
  • 481
1 vote
0 answers
143 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 ...
False Promise's user avatar
1 vote
0 answers
101 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 $\...
Mengfan Ma's user avatar
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 ...
Henry McKay's user avatar
1 vote
0 answers
896 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(\...
M a m a D's user avatar
  • 1,519
1 vote
0 answers
73 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[\...
Charlie Parker's user avatar
1 vote
0 answers
769 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 ...
Susmita Ghosh's user avatar
1 vote
0 answers
349 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 ...
john mangual's user avatar
  • 1,941
1 vote
0 answers
289 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 ...
polym's user avatar
  • 135
1 vote
1 answer
107 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 ...
Möbius's user avatar
  • 21
1 vote
1 answer
122 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 ...
Spindoctor's user avatar
0 votes
0 answers
41 views

Correctness Proof of Recursive Function

This code determines whether there exists a contiguous subarray starting from index 0 in the given array A whose elements sum up to the target value S. I want to prove its correctness. I know it's ...
Moh's user avatar
  • 49
0 votes
0 answers
37 views

Calculating Runtime Complexity: Recursion + Memoization vs Dynamic Programming (with example)

For cases where recursion is used as well as memoization (so that a number of subtrees of what would otherwise be the overall recursive call tree are each replaced to be ...
mishar's user avatar
  • 101
0 votes
0 answers
29 views

USACO Ski Course Design

So I was doing this problem, but it led me to a different solution. The actual solution is this: Problem - Farmer John has N hills on his farm (1 <= N <= 1,000), each with an integer elevation ...
AdsDeWorst's user avatar
0 votes
0 answers
14 views

Better implementations for this dynamic program to solve optimization problem?

In the code below, I describe a problem and provide a backtracking implementation in Python that solves it: ...
lafinur's user avatar
  • 181