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
0
votes
0answers
138 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
93 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
394 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
45 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
58 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
39 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
247 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
576 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
331 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
3k 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
49 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
757 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
85 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
515 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
76 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 $\...
3
votes
0answers
527 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
127 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
582 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 ...
8
votes
2answers
179 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 ...
2
votes
1answer
53 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
461 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
250 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
127 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
198 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 ...
3
votes
1answer
684 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
160 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
337 views

Why is recursive programming problematic for branch predictors

Consider for example the following recursive program: ...
0
votes
0answers
89 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
69 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
654 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
40 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
328 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
234 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
197 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
117 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
3k 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
40 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 ...
0
votes
0answers
367 views

Understanding Dynamic Programming through this example

I have trouble understanding The classic Mailbox Manufacturers Problem. You can read it here: https://open.kattis.com/problems/mailbox I have also found a solution text: http://www.ida.liu.se/projects/...
0
votes
0answers
128 views

Recursive algorithm for counting pairs of ancestor and child, where sum =n

Hey, this is a question from my handouts, but how would I go about writing a recursive program that would return the number of pairs of an ancestor and a child, whose sum equals to n, given that the ...
0
votes
1answer
580 views

How solve this recurrence: T(n) = 2t(n-1) - t(n-2) +5n +7 [duplicate]

I am trying to solve the recurrence: T(n) = 2t(n-1) - t(n-2) +5n +7 but without success. And from here I don't know how to continue?
0
votes
0answers
211 views

Iteration vs. recursion: what do these terms really mean?

Most of us know the typical answer to this question: if a function calls itself, it's recursion, if it's a loop, it's iteration. We also know that recursion can be simulated using iteration (by ...
0
votes
0answers
47 views

time complexity question

I am reading a free algorithms textbook http://www.cse.iitd.ernet.in/~Naveen/courses/CSL630/all.pdf and on page 13 i am stuck on an example they give. "At this time, the fastest computer in the ...
0
votes
0answers
16 views

How to solve this recursive relation T(n)= 2T(n/2) + 3T(n/5) +n [duplicate]

I don't think I'm able to solve this using the master's theorem, and solving separately doesn't seem to make sense. How does one go about solving this recursive relation? T(n)= 2T(n/2) + 3T(n/5) +n
0
votes
0answers
340 views

How to calculate the depth of the call stack for the average case of quicksort

In the best case of quicksort the depth of the call stack is measured by $\lceil\log_2 n\rceil$ if I am not wrong. What would be the formula for calculating the depth of the call stack in case of an ...

1 2 3
4
5
9