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
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
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 ...
• 141
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 ...
• 31
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, ...
• 610
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 ...
• 379
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 ...
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.
• 121
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 ...
• 21
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, ...
• 121
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 ...
• 152
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 ...
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 ...
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, ...
• 994
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 ...
• 21
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
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,721
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. ...
• 21
1 vote
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). ...
1 vote
52 views

• 111
1 vote
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. <...
1 vote
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). ...
• 133
1 vote
2k views

Longest increasing subsequence (Dynamic Programming)

I have written the following recursive structure for finding length of longest increasing subsequence. ...
• 481
1 vote
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 ...
1 vote
101 views

• 3,040
1 vote
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 ...
1 vote
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 ...
• 1,941
1 vote
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 ...
• 135
1 vote
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 ...
• 21
1 vote
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 ...
• 131
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 ...
• 49
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 ...
• 101