A message from our CEO about the future of Stack Overflow and Stack Exchange. Read now.

Questions tagged [recursion]

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

Filter by
Sorted by
Tagged with
1
vote
0answers
1k views

Longest increasing subsequence (Dynamic Programming)

I have written the following recursive structure for finding length of longest increasing subsequence. ...
5
votes
0answers
50 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,...
0
votes
2answers
352 views

Making a recursive formula for finding amount of ways to spend money on beer

So far, i've only made recursive formulas for finding simple patterns such as fibonacci, however i can't seem to get my head around this. The information available is that there are $n$ different ...
4
votes
2answers
150 views

Alan Perlis Epigram on Recursion

So, while trying to dive into "recursion" and the like, I came across an epigram about recursion by Alan Perlis: Recursion is the root of computation since it trades description for time. -- ...
0
votes
2answers
120 views

Proving the correctness of a square summing algorithm

int sumHelper(int n, int a) { if (n==0) return a; else return sumHelper(n-1, a + n*n); } int sumSqr(int n) { return sumHelper(n, 0); } I am supposed ...
0
votes
2answers
1k views

How does in-order traversal in Binary search tree works (recursion)

I visit some question but their implementations are slightly different and my doubt is not like theirs. I have this code in Javascript. The code is typical BST implementation with methods to support ...
4
votes
1answer
282 views

Understanding Martin Farach's suffix tree algorithm

I feel stuck at this point. I have spent several days trying to get my head around the algorithm, but both resources I have [1] [2] seems to skip over whatever details that would make me comfortable ...
0
votes
0answers
123 views

Proof of correctness recursive reverse digit function

This is an attempt to understand better recursion. The following recursive function returns the integer obtained by reversing the digits of an input integer. I'm trying to prove its correctness: <...
1
vote
1answer
86 views

Number of calls with length 2 array in quick-sort

I need to find average number of recursive calls in quick-sort with array of length 2. I established and solved the following recursion: $$T_N = \frac{1}{N}\sum_{k=1}^N\left(T_{k-1}+N_{N-k}\right) = \...
1
vote
1answer
30 views

Recurrence equation calculation

I have a recurrece equation Changed notations: $\qquad\displaystyle G(W) = \max \{ G(W - s_i) + v_i \mid 0 \leq i \leq n, w_i \leq W \}$, I am not sure if I understand $\ w_i $ correctly. On each ...
1
vote
1answer
312 views

Finding the longest overlapping interval pair

Say I have a list of $n$ integral intervals $[a,b]$ where each represents a set $S = \{a, a+1, \ldots, b\}$. An overlap is defined as $|S_1 \cap S_2|$. Example: $[3,6]$ and $[5,9]$ overlap on $[5,6]$ ...
2
votes
1answer
44 views

Generating all words of length $n$ avoiding $A^2$ and $B^3$

I need to find a way to iterate over all sequences of words in two letters $A,B$ avoiding the sequence $A^2 = AA$ and $B^3 = BBB$. First of all, what is the regular expression for such a thing? I ...
1
vote
1answer
52 views

How can I prove that $T(n)=\sqrt{n}T(\sqrt{n})+n$ grows as $\Theta(n\log \log{n})$? [duplicate]

How can I prove that if $T(n) = \sqrt{n}T(\sqrt{n}) + n$ then $T(n) = \Theta(n\log\log n)$? I tried to define $T(n)$ by $G(n)$, prove about $G(n)$, and then to return to $T(n)$, but it's not working.....
1
vote
0answers
36 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 ...
0
votes
0answers
197 views

Doubt on analysis on time and space complexity of creating n² tuples

This is a question from a past-yr mid-term paper from my school(using Python language). Attached below is a diagram to show how a robot will move. Don't mind if the link seems dubious as I just used ...
10
votes
2answers
504 views

How to derive dependently typed eliminators?

In dependently-typed programming, there are two main ways of decomposing data and performing recursion: Dependent pattern matching: function definitions are given as multiple clauses. Unification ...
2
votes
2answers
317 views

Solve every problem with recursion [duplicate]

Is it possible to solve every problem (solvable with turing machine) with only recursion ? If yes, which principles or theories assure this ? Thanks
1
vote
2answers
2k views

Big O notation for recursive algorithm [duplicate]

In order to find Big O for a recursive algorithm, it is needed to know the stopping criteria of that algorithm. For the recursive algorithm to find Factorial of a number it is very easy to find the ...
0
votes
0answers
46 views

Is there a proof for the halting problem that does not involve an infinite nest of functions? [duplicate]

I have been doing a fair amount of research about the halting problem. Most solutions I come across have the following pattern: We assume we have a program H that solves the halting problem. We then ...
2
votes
0answers
57 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 ...
0
votes
1answer
618 views

Recursive Algorithm Copying Array vs. Time Complexity

If I am implementing binary search using a recursive algorithm on an array it will be bounded by $O(\log(n))$. However, what will occur if the array is NOT passed by referenced and rather by value. ...
0
votes
0answers
75 views

Time Complexity — Recursion

It's been a long time since I've studied time complexity in school, but I've been tasked with finding the time complexity of an algorithm. Here is the algorithm in a pseudo-pseudocode (yes, two ...
1
vote
0answers
412 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
0answers
73 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 $\...
2
votes
0answers
408 views

How to “convert” a top-down solution to a bottom-up algorithm? [duplicate]

When I'm working on a algorithm problem, I can usually find a top-down solution that works with recursion. Then for optimization purpose I try to do a bottom-up approach (dynamic programming) to ...
0
votes
1answer
119 views

If set $C$ is recursively enumerable and $B$ is Recursive, and if $B-C$ is recursively enumerable then is $C$ recursive or not?

So this is how i solve it but someone told me its wrong: $B-C = B\cap \overline C $ and since $B\cap \overline C $ is r.e and B is recursive recursive sets are closed under intersection then $\...
0
votes
0answers
28 views

how to solve Recurtion equation [duplicate]

Does someone know how to solve the below? $$T(n)=2T(n-1)-T(n-2)+5n+7$$ $$T(n)=2T(sqrt(n))+(logn/(log(logn))$$ $$T(n)=T(sqrt(n)[5])+log(log[3]n)$$
1
vote
4answers
531 views

Towers of Hanoi First Move

I've finally more or less understood the recursive algorithm for solving the Towers of Hanoi. My Python code is below. However one thing still bugs me - I can't yet work out how this simple seeming ...
7
votes
2answers
154 views

Ackerman hierarchy for higher order primitive recursion in System T

Gödel defines in his System T primitive recursion over higher types. I found notes from Girard where he explains the implementation of System T on top of simply typed lambda calculus. On page 50 he ...
3
votes
1answer
61 views

Is there any practical application for arrays that contain themselves?

I'm reading the introduction to Godel, Escher, Bach and and there's heavy discussion of mathematical sets which contain themselves. Being a far better programmer than mathematician, I put it into ...
3
votes
1answer
49 views

Integer log2 as a catamorphism?

Recursion schemes are structured methods for expressing recursive functions, of increasing interest due to their ubiquity in functional programming. For example, catamorphisms (familiar in the guise ...
2
votes
1answer
412 views

If all edges are unweighted AND DIRECTED, can one use BFS to obtain a MST?

I've looked through CS SE and I've found a page that said you could find use BFS to find a MST if the edges are unweighted, but what if the edges are directed? Given a directed graph between V ...
8
votes
2answers
2k views

Difference between Tail-Recursion and structural recursion

Is there any difference between structural-recursion and Tail-recursion or they both are same? I see that in both of these recursions , the recursive function is called on the subset of the orignal ...
-2
votes
1answer
232 views

Is it beneficial to convert recursion to tail recursion? [duplicate]

If it is beneficial, then how Big-O (time complexity) is affected? Embedded link provided by members does not answer original question.
-1
votes
1answer
121 views

Can we use recursion for large pool of input data? [closed]

While studying recursion, I came to know that for every function call it has to store intermediate data on stack for later use. If so, then for large amount of data, recursion can be inefficient. ...
1
vote
1answer
168 views

Towers of Hanoi Algorithm “Using Auxiliary” Peg

I'm trying to fully understand how the recursive Towers of Hanoi Algorithm works and to implement it in code. Something that keeps throwing me of is the use of phrases like "move n-1 discs from A to ...
2
votes
1answer
573 views

DP tiling a 2xN tile with L shaped tiles and 2x1 tiles?

https://www.iarcs.org.in/inoi/online-study-material/topics/dp-tiling.php The second question in the above link requires us to fill an 2xN grid with tiles of dimension 2x1 and an L shaped tile. ...
2
votes
2answers
126 views

Recursive definition of a language $ L $ over $ \{a,b\} $

How would I start the recursive definition of the following language: L over {a, b} such that L consists of strings in which each occurrence of b is immediately preceded and followed by an a The ...
0
votes
2answers
267 views

Why is recursive programming problematic for branch predictors

Consider for example the following recursive program: ...
0
votes
0answers
86 views

What is the run time of this algorithm?

Robot in a grid: Imagine a robot sitting on the upper left corner of a grid with $r$ rows and $c$ columns. The robot can only move in two directions, right or down, but certain cells are off limits ...
1
vote
1answer
62 views

Dynamic Programming Recursive Algorithm - Number of heads in a series

So I have this programming prompt which asks me to figure out how many permutations of a 32 coin toss sequence do not have three or more heads consecutively tossed. We are supposed to use Dynamic ...
14
votes
2answers
571 views

What property of cons allows elimination of tail recursion modulo cons?

I'm familiar with the idea of basic tail recursion elimination, where functions that return the direct result of a call to themselves can be rewritten as iterative loops. ...
0
votes
0answers
31 views

How is this defined in an iterative style?

This is the so-called recursive style: And this is the so-called iterative style: It seems like it is defined recursively to me. The function doesn't hide the next call of the function defined in it ...
1
vote
2answers
322 views

Find height of deepest FULL level in binary tree

Suppose I have a binary tree that is guaranteed to have at least one level that holds the maximum amount of nodes possible. I want to find the height of the deepest level that is full/holds the ...
0
votes
0answers
209 views

Understanding time complexity for kth minimum in CLRS

In chapter 10.3. Selection in worst - case linear time ($k$th minimum) from Introduction to Algorithms by Cormen, Leiserson and Rivest, the time complexity expected for step 5 of the algorithm ...
0
votes
1answer
180 views

How to convert this recursive algorithm to an iterative form?

Let us assume there's a folder structure as shown below: The letters a-d represent folders and the number 1-5 represent video files where for the file n, ...
1
vote
1answer
110 views

Converting Recursion into Into Iteration [duplicate]

While reading Code Complete second edition, I came across this line: You can do anything with stacks and iteration that you can do with recursion. Is this true? or there are functions, that must ...
1
vote
0answers
20 views

recursive function Time complexity [duplicate]

I studied this algorithm. Link. Is is about finding all possible binary trees with given inorder traversal. I want to analyze this code with Big-O notation. I think it is O(N^3). Below is my thought. ...
1
vote
3answers
2k views

What is the time complexity of this binomial coefficient algorithm?

Here's a naïve algorithm that computes $ \binom{n}k $ (or "n choose k"), with either $k=0$ or $1\le k \le n$: ...
1
vote
1answer
38 views

If $R(x,y)$ is a recursive relation, then $\exists y\leq 2$ such that $R(x,y)$ is recursive

The theorem says: If $R(x,y)$ is a recursive relation, then there exists $y\leq2$ such that $R(x,y)$ is recursive. Here is my attempt of proof: Since $R(x,y)$ is recursive, we can construct a ...