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
3
votes
3answers
7k 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 ...
5
votes
1answer
755 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 ...
46
votes
5answers
11k 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 ...
3
votes
1answer
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 ...
70
votes
4answers
66k 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 ...
26
votes
5answers
45k 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?
16
votes
2answers
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 ...
13
votes
1answer
3k 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 ...
3
votes
2answers
2k 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 ...
3
votes
1answer
864 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
1answer
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 ...
2
votes
2answers
1k 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)),...
1
vote
0answers
680 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 ...
1
vote
1answer
40 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 ...
0
votes
1answer
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 ...
18
votes
3answers
15k 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 ...
22
votes
2answers
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 ...
3
votes
2answers
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: ...
3
votes
1answer
10k 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 ...
2
votes
1answer
471 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 ...
4
votes
1answer
730 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 ...
3
votes
2answers
17k 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 - ...
3
votes
0answers
413 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 ...
2
votes
2answers
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 ...
0
votes
1answer
502 views

Time complexity of mutually recursive functions

Suppose I have two mutually recursive functions like this: ...
-1
votes
1answer
532 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 ...
4
votes
2answers
1k 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 <...
4
votes
1answer
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 ...
3
votes
3answers
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 ...
3
votes
1answer
1k 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 ...
2
votes
1answer
541 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/...
2
votes
1answer
365 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 ...
1
vote
1answer
469 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 ...
0
votes
2answers
61 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 ...
0
votes
0answers
71 views

Get the maximum sum of n items below a threshold

Consider a modified Knapsack Problem where: The number of items to be included is fixed. The value of each item is equal to its weight. Therefore, given a set of numbers, a threshold and the number ...
0
votes
1answer
73 views

Converting a algorithm to a runtime function

I need to find an upper limit for the runtime of $f(n)$. ...
0
votes
2answers
687 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 ...
0
votes
1answer
2k 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 (...