Questions tagged [recursion]
Questions about objects such as functions, algorithms or data structures that are expressed using "smaller" instances of themselves.
43
questions
46
votes
5
answers
12k
views
Iteration can replace Recursion?
I've been seeing all over stack Overflow, e.g here, here, here, here, here and some others I don't care to mention, that "any program that uses recursion can be converted to a program using only ...
- 1,617
3
votes
3
answers
8k
views
Iterative and/or tail-recursive implementations of merge sort?
I recently learned how to implement merge-sort, using a standard recursive algorithm. Can the algorithm be implemented in a way that allows for a tail-recursive implementation? Can it be implemented ...
- 277
5
votes
1
answer
1k
views
Algorithm to find maximum number of floors you can check with N eggs and D maximum drops
Question: You are given access to a multistory building. You have N eggs and are allowed D maximum drops from their window.
Rules: If a egg is dropped from window of floor F and it breaks, it will ...
- 390
5
votes
2
answers
5k
views
single algorithm to work on both directed and undirected graph to detect cycles?
I have been trying to implement an algorithm to detect cycles (probably how many of them) in a directed and undirected graph. That is the code should apply for both ...
- 269
76
votes
4
answers
73k
views
What is tail recursion?
I know the general concept of recursion. I came across the concept of tail recursion while studying the quicksort algorithm. In this video of quick sort algorithm from MIT at 18:30 seconds the ...
- 1,191
26
votes
5
answers
47k
views
When to use recursion?
When are some (relatively) basic (think first year college level CS student) instances when one would use recursion instead of just a loop?
- 579
17
votes
2
answers
1k
views
Does the Y combinator contradict the Curry-Howard correspondence?
The Y combinator has the type $(a \rightarrow a) \rightarrow a$. By the Curry-Howard Correspondence, because the type $(a \rightarrow a) \rightarrow a$ is inhabited, it must correspond to a true ...
- 273
13
votes
1
answer
4k
views
Is this a generic way to convert any recursive procedure to tail-recursion?
It seems that I've found a generic way to convert any recursive procedure to tail-recursion:
Define a helper sub-procedure with an extra "result" parameter.
Apply what would be applied to the ...
- 1,081
3
votes
2
answers
3k
views
Show $x^y$ is a primitive recursive function
As this thread title gives away I need to prove $x^y$ to be a primitive recursive function.
So mathematically speaking, I think the following are the recursion equations, well aware that I am ...
- 311
3
votes
1
answer
1k
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.
...
- 131
2
votes
1
answer
2k
views
Proof of big theta using induction [duplicate]
Here is a recursive definition for the runtime of some unspecified function. $a$ and $c$ are positive constants.
$T(n) = a$, if $n = 2$
$T(n) = 2T(n/2) + cn$ if $n > 2$
Use induction to prove ...
- 23
2
votes
2
answers
2k
views
Why are unbalanced partitions worse than balanced partitions in Quicksort?
I am unable to understand why unbalanced partitions in quicksort is actually worse than balanced partitions.
After reading this document it shows that worse case partitions are of the type $(0,(n-1)),...
- 215
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
1
answer
199
views
Solve the recursive function $T(n) = T(\sqrt{n}) + T(n - \sqrt{n}) + \theta(n)$
in one of my college assignments i came up with the following recursive function which I'm ask to solve:
$T(n) = T(\sqrt{n}) + T(n - \sqrt{n}) + \theta(n)$
I could not use master method on it and it ...
- 250
0
votes
1
answer
1k
views
Register Machine code for Fibonacci Numbers
I am not sure whether this is the right place to ask this question.
I would like to write a register machine code which when given an input of n in register
1, returns (also in register 1) the nth ...
- 101
23
votes
2
answers
3k
views
Recursive definitions over an inductive type with nested components
Consider an inductive type which has some recursive occurrences in a nested, but strictly positive location. For example, trees with finite branching with nodes using a generic list data structure to ...
18
votes
3
answers
16k
views
Can a tree be traversed without recursion, stack, or queue, and just a handful of pointers?
Half a decade ago I was sitting in a data structures class where the professor offered extra credit if anyone could traverse a tree without using recursion, a stack, queue, etc. (or any other similar ...
7
votes
1
answer
729
views
Inductive vs. recursive definition
When should I call a definition recursive and when should I call it inductive?
I have read Carl Mummert's nice answer on MSE. So if I understand correctly we refer to definitions of objects like ...
- 22.2k
4
votes
1
answer
1k
views
Recursive definition of a language given the regular expression
Consider the language:
$$
L_1 = \{ x \in \Sigma^* : x \text{ does not contain the substring } 110\}
$$
I know that there is a DFA that accepts this language, and furthermore, that the regular ...
- 347
4
votes
2
answers
3k
views
Technique for converting recursive DP to iterative DP
I'm new to Dynamic Programming and before this, I used to solve most of the problems using recursion(if needed).
But, I'm unable to convert my recursive code to <...
- 226
4
votes
1
answer
812
views
How to show that f(x) is primitive recursive?
Let
$$f(x)=\begin{cases} x \quad \text{if Goldbach's conjecture is true
}\\ 0 \quad \text{otherwise}\end{cases}$$
Show that f(x) is primitive recursive.
I know a primitive recursive ...
- 2,193
3
votes
2
answers
1k
views
How to solve the recurrence: T(n) = n*T(n-1) + n?
In a an exercise I'm required to analyze the runtime of recursive function:
...
- 351
3
votes
3
answers
1k
views
How to write a recursive function that with certain time complexity
I'm now doing exam revision, and from some past year exam papers, I noticed some questions that ask to write a recursive method with signature like
...
- 785
3
votes
0
answers
479
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
1
answer
11k
views
CLRS 4.4-3 Height of recursion tree for T(N) = 4T(n/2 +2) + n
I'm having a hard time with the following question:
Use a recursion tree to determine a good asymptotic upper bound on the recurrence $T(n) = 4T(n/2 + 2) + n$. Use the substitution method to verify ...
- 133
3
votes
2
answers
29k
views
Solution to recurrence $T(n) = T(n/2) + n^2$
I am getting confused with the solution to this recurrence -
$T(n) = T(n/2) + n^2$
Recursion tree -
...
- 146
3
votes
1
answer
2k
views
Complexity of a recursive bignum multiplication algorithm
We have started learning about analysis of recursive algorithms and I got the gist of it. However there are some questions, like the one I'm going to post, that confuse me a little.
The exercise
...
- 683
2
votes
2
answers
2k
views
Need a practical solution for creating pattern database(5-5-5) for 15-Puzzle
I have asked this exact question on StackOverflow. I did not get the answer that I was looking for. Please read this question fully before answering. Thank You.
For static pattern database(5-5-5), see ...
- 261
2
votes
1
answer
810
views
primitive recursion in the lambda calculus
I am having trouble finding out what a primitive subset of the lambda calculus would look like. I reference primitive recursion as shown here: "https://en.wikipedia.org/wiki/...
- 459
2
votes
1
answer
736
views
$T(n) = \sqrt{n}\,T(\sqrt{n}) + n\log n$ [duplicate]
I tried to solve the recurrence $T(n) = \sqrt{n}\,T(\sqrt{n}) + n\log n$ with the master theorem but I can't get it to work.
How many arrays exist in each step in the recursion tree?
Or can I solve ...
- 123
2
votes
1
answer
564
views
Would adding recursive named functions to Simply typed lambda calculus make it Turing complete?
Say I have Simply typed lambda calculus, and add an assignment rule:
<identifier> : <type> = <abstraction>
Where ...
- 745
1
vote
1
answer
586
views
Find one-variable recursive formula for running time of Karatsuba multiplication
I'm currently trying trouble to set up the recursive expression for the Karatsuba multiplication of two integers with $n$ and $m$ bits (both having a different number of bits). Usually, the recursion ...
- 111
1
vote
0
answers
108
views
How many ways we can partition a multiset, where each part/segment in the partition has distinct elements? [closed]
We define the set S as $\{(s_1, f_1), (s_2, f_2), ..., (s_i, f_i)\}$, where each $f_i$ is the frequency that $s_i$ is repeated in the multiset T. How many ways can we partition the multiset T into ...
0
votes
3
answers
948
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 ...
- 11
0
votes
2
answers
45
views
Prove $T(n)=2T(\dfrac{n}{2})+\Theta(n\log{n})=\Theta(n\log^2{n})$ using induction
Please first take a brief look at my previous question. Here I want to do something similar but for $T(n)=2T(\dfrac{n}{2})+\Theta(n\log{n})$. I know the answer is $T(n)=\Theta(n\log^2{n})$ and I want ...
- 151
0
votes
1
answer
83
views
Change of associativity for a given right-recursive grammar
In section 3.7.1, of the book titled: Compiler design in C, by Allen I. Holub (made available freely online, by the author here, & the page #19 of errata, here), have on page #176, the mention of ...
- 187
0
votes
1
answer
315
views
Time complexity of merging two lists while preserving order
I have two lists l1 and l2 of possibly unequal sizes (say, m and ...
- 9
0
votes
2
answers
73
views
Finding the runtime out of a recursion formula when using divide-and-conquer
In divide-and-conquer, one uses the following formula to find the runtime:
$$T(n) = aT(n/b) + f(n).$$
I am confused with the meaning of the constants $a$ and $b$, as well as by the question of how to ...
- 113
0
votes
2
answers
181
views
Prove by induction that a recurrence has solution $T(n)=\Theta(n^2 \log_{3}n)$
Prove by induction that $T(n)=\Theta(n^2 \log_{3}n)$ where
$$T(n)= \begin{cases} 1 & \mbox{if } n=1,\\ 9T(\lceil n/3 \rceil)+n^2 & \mbox{otherwise.} \end{cases}$$
The base case for $n=1$ seems ...
- 147
0
votes
1
answer
80
views
Converting a algorithm to a runtime function
I need to find an upper limit for the runtime of $f(n)$.
...
- 143
0
votes
1
answer
657
views
Time complexity of mutually recursive functions
Suppose I have two mutually recursive functions like this:
...
0
votes
1
answer
3k
views
Particularly Tricky Recurrence Relation (Master's Theorem)
Master's theorem is shown below,
The recursive function to be solved is shown below,
I understand that a refers to the number of recursive calls in this function (...
-1
votes
1
answer
652
views
Understanding the reason behind the μ (mu) operator [closed]
What is the purpose of the $\mu$ operator?
Is there a real world example?
Is it correct that it can create partial
functions out of total functions and it makes a function $g$ with k
parameters out ...
- 135