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
2answers
35 views

How can any non-primitive-recursive function like the Ackermann function be implemented on hardware?

If for-loops and function calls both boil down to jump instructions when implemented on a real machine, then how is "The Ackermann function isn't implementable with for-loops" a meaningful phrase?
0
votes
1answer
14 views

Complexity of iterative exponentiation

I've watched multiple videos and read articles about recursion but I'm still confused. I've got this problem here but I'm unsure how to answer it: The following function calculates $x^n$ ...
0
votes
0answers
27 views

Is it still called “recursion” when you're using call-stack as a stack?

The most obvious way to solve a problem of balancing parentheses, like https://leetcode.com/problems/valid-parentheses/, is through a stack (a last-in-first-out (LIFO) datastructure). However, if you ...
-2
votes
0answers
28 views

Towers of Hanoi through ITERATION [on hold]

instead of recursion i tried my own version of solution...can anyone tell me the difference between my solution and that of standard iteration solution ...
3
votes
1answer
41 views

Is this lambda abstraction created as a generator of a recursive function?

In lambda calculus, a recursive function $f$ is obtained by $$ f = Y g $$ where $Y$ is the Y combinator and $g$ is the generator of $f$ i.e. $f$ is a fixed point of $g$ i.e. $f == g f$. In The ...
-2
votes
0answers
25 views

What is the running time of the following procedure? [duplicate]

Please help me calculate the time complexity of the following procedure. Power(n) 1:If n=0 then 2: return 1 3:else if 4: return Power(n-1) + Power(n-1) Explain ...
-1
votes
0answers
15 views

What recursive T(N) function typically can conclude the algorithm is O(n ^ 2), O(n log n), O(n), and O(log n)?

Is it true that some common forms of recursive T(n) can give the following conclusions? When T(n) = T(n/c) + b where c is a constant > 1, b is any constant ...
1
vote
0answers
31 views

Transforming an immutable binary tree without recursion [closed]

I'm struggling on this one. I have a Binary Decision Diagram, which is pretty much tree-like. Each node has a hi and lo node. I need to recurse into the tree, and if some conditions are the case ...
1
vote
1answer
39 views

Recursion Time Complexity (Half n' Half)

This is my solution for Leetcode 395, and I'm wondering how I can come up with its time complexity: Input: string $s = s_1,\ldots,s_n$, integer $k$ Go over all symbols $s_1,\ldots,s_n$, one by one ...
3
votes
2answers
74 views

Is there any recursive function f whose code is unique?

I am doing some reviewing for the term final on computability and found out this simple exercise. I am very fresh on theoretical computer science so if you do have an answer please make it simple. ...
1
vote
0answers
30 views

How to approach backtracking when using immutable types (Python)? [closed]

In Python when we are building a recursive algorithm that uses backtracking a mutable type such as a list is great to use. It can be modified at each call in our recursion tree, then returned back to ...
0
votes
2answers
47 views

Iteration vs Recursion question in Lisp method

I am curious if the following method would be called iterative or recursive: ...
2
votes
1answer
24 views

Turing Machine equivalence in MinTM proof

The proof with contradiction that $MIN_{\mathrm{TM}}$ is not Turing-recognizable from Michael Sipser's textbook "Introduction to the Theory of Computation" (Theorem 6.7) is as follows: $C=$ "On ...
1
vote
1answer
61 views

How to find the Big-O for finding combinations of balanced parentheses?

Given n pairs of parentheses, a function which returns the total number of all combinations well-formed parentheses could be: ...
0
votes
1answer
49 views

Count the number of ways numbers 1,2,…,n can be divided into two sets of equal sum

count the number of ways numbers 1,2,…,n can be divided into two sets of equal sum. This is my recursive algorithm, what is wrong here?: ...
2
votes
2answers
39 views

How to use Master Theorem with strange format of $b$ parameter?

I have a funcion $T: \mathbb{N}\to\mathbb{N}$ defined as: $$T(n)=\begin{cases} 6 &\text{ if } n=0,\\ T(n-1) + 6n + 6 &\text{otherwise.} \end{cases}$$ How can I apply the Master Theorem to ...
2
votes
2answers
87 views

Prove that $T(n) \leq 8n^2$ or find value of $n$ when statement is not true (recurrence relation)

We have a function $T: \mathbb{N}\to\mathbb{N}$ defined recurrently: $$T(n)=\begin{cases} 0 &\text{ if } n=0,\\ 3T(\lfloor{n/2}\rfloor) + 2n^2 &\text{otherwise.} \end{cases}$$ Prove that for ...
2
votes
1answer
168 views

Are all foldable data structures also recursive?

I was checking what Wikipedia has to say on reduce. It says: In functional programming, fold (also termed reduce, accumulate, aggregate, compress, or inject) refers to a family of higher-order ...
1
vote
1answer
61 views

Assigning $m$ balls to $n$ buckets - recursive algorithm

I came across the following problem and the answer to that problem: Given $m$ balls and $n$ bins, find out how many ways to assign the balls to the bins. Notice the bins have no order: for example, ...
1
vote
1answer
77 views

Given price and number of pages of each book, What is the maximum number of pages you can buy?

You are in a book shop which sells n different books. You know the price and number of pages of each book. You have decided that the total price of your purchases will be at most x. What is the ...
1
vote
0answers
37 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. <...
0
votes
2answers
103 views

What is the height of a tree with recursion formula: $T(n) = T(n - \sqrt{n})$

I know if the time complexity of an algorithm is given with the above formula, then the algorithm works in constant time but my question is that what will be the height of the recursion tree for this ...
2
votes
1answer
53 views

Number of Function Calls In Recursive Code

I am new to recursion. I am doing some practice questions and I was wondering what the technique is for going from some recursive code to identifying the number of function calls it makes. ...
2
votes
1answer
30 views

Understanding proof of upper bound on complexity of recursive computation of graph chromatic polynomial

This question is about section 2.3 of Wilf's ``Algorithms and Complexity'' https://www.math.upenn.edu/~wilf/AlgoComp.pdf in which he analyses the complexity of a recursive computation of the ...
2
votes
1answer
55 views

What is the closed-form expression for $T_n = \left(\sum_{i=1}^{n-1}7 T_i\right) + 1$ where $T_1 = 1 ?$ [closed]

Problem: Find the closed-form expression for$$ T_n = \left(\sum_{i=1}^{n-1}7 T_i\right) + 1 \tag{1} $$where $T_1 = 1 .$ Calculating this sum I came up with the following result: $$ T_n = 8^{\left(...
2
votes
1answer
40 views

Is there purely recursive functions? [duplicate]

Is there any problem that can be only solved with recursion, and not with iteration? (haven't been able to find anything online). If there isn't any, is there a reason why? Thanks in advance!
2
votes
1answer
29 views

Computability: Proving a predicate is not recursively enumerable

Let P(p) <=> for each x, comp(p,x) is defined. Can anyone explain to me how to prove that P is not RE (recursively enumerable) ?
0
votes
1answer
47 views

Multiple choices for a single case in the recursive formula of a Dynamic Programming algorithm

I am developing a Dynamic Programming algorithm for a problem in scheduling. In the recursive formula, I have three cases: (1) $t_{i-1} = int$ (2) $t_{i-1} = app \quad \& \quad r(j) \leq p $ and (...
0
votes
1answer
35 views

Recursive definition for the length of a string?

I found a couple of answers online but I don't quite understand why the answer is right: The length of a string is: If a string has no characters, then its length is 0. Otherwise, the length of the ...
0
votes
0answers
66 views

Write the Brute Force Recursive Code to generate the longest substring containing k distinct vowels

Given a string s we have to find the length of the longest substring of s which contain exactly K distinct vowels. This is the problem statment given on geeksforgeeks Input : s = “artyebui”, k = 2 ...
1
vote
1answer
75 views

Avoiding “side effects” in recursive functions

I am writing a function to find the intersection between two sets. The non-functional requirements of the assignment include avoiding "side effects". ...
0
votes
0answers
13 views

T(n) = T(n-1) +3n^2 - 2n +1 [duplicate]

I was wondering how do I solve this, I've been trying any possible way to but I've failed: $$\begin{align*} T(n) &= T(n-1) +3n^2 - 2n +1 ,& n \ge 1 \\ T(0) &=2 &\\ \end{align*}$$
5
votes
1answer
207 views

Worst-case input for median-of-medians with groups of size 3

Typically, median of medians algorithm is written with groups of size $5$ or $7$ to ensure worst-case linear performance. The argument against groups of size $k=3$ is typically that we get a ...
0
votes
2answers
178 views

prove by induction that the complete recursion tree for computing the nth Fibonacci number has n leaves

I have referenced this similar question: Prove correctness of recursive Fibonacci algorithm, using proof by induction *Edit: my professor had a significant typo in this assignment, I have attempted ...
0
votes
0answers
31 views
1
vote
0answers
50 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). ...
1
vote
1answer
36 views

Whether it's necessary for a grammar to be ambiguous when it is both left recursive and right recursive

I read somewhere that if a grammar is left recursive as well as right recursive, then it is not necessarily ambiguous. I couldn't make up my mind on this statement. How can a grammar which is both ...
2
votes
1answer
166 views

Can memoization be applied to any recursive algorithm?

I am new to the concepts of recursion, backtracking and dynamic programming. I am having a hard time understanding if at all I can apply memoization to a particular recursive algorithm and if there ...
0
votes
0answers
50 views

Dynamic Programming solution for finding shortest distance to travel between points

So consider a person located at point $c$ (let's say $c=140$). Given a set of other points, for example, $P = \{100, 50, 190\}$. The cost of traveling to a point $P_i$ is then $|c-P_i|$. Points can be ...
0
votes
1answer
65 views

Recursively edit 2-D array using backtracking

I have a 2-D array which contain 3 types of elements: C (Contaminant) R (Rock) W (Water) The rule is that: contaminant can seep through water but not through rocks. Let's say I have the ...
2
votes
2answers
71 views

Recursion to DP Solution

There's a problem in Kleinberg & Tardos's Algorithm Design (Chapter 6, Question 4) where you are running a lightweight consulting business that has two offices: NYC and SF. In month $i$, you'll ...
2
votes
1answer
32 views

Maximum Expected Fishing Day (Recurrence Relation)

John joined a meetup where organize day long fishing trip once a month. The organizers are vary poor at planning, so will organize fishing on a random day of the month without any advance notice. ...
7
votes
4answers
157 views

What is the depth of recursion if we split an array into $\log_2(n)$ with each recursive call?

We have a function which takes an array as input. It breaks an array into $\log_2(n)$ parts with equal sizes where $n$ is the size of the subarray. It keeps breaking each of the subarrays until there ...
2
votes
1answer
41 views

Is there a relation between the size of the domain/range of a function and its computability?

This was a question given in a course, without answer. The referenced literature (just a few books) do not cover it, unfortunately. I think there is no relation with the range as the range of the ...
0
votes
1answer
63 views

Recursive factorial algorithm

I'm struggling to understand this factorial algorithm. ...
0
votes
1answer
150 views

Merge sort and quciksort recursion tree depth

1) I need to determine recursion tree depth for strings composed of 10, 100 and 1000 elements when using merge sort. For the 10 elements one I can do it on a paper, just drawing tree, but what about ...
2
votes
1answer
147 views

Induction to prove equivalence of a recursive and iterative algorithm for Towers of Hanoi

Using induction how do you prove that two algorithm implementations, one recursive and the other iterative, of the Towers of Hanoi perform identical move operations? The implementations are as follows....
0
votes
3answers
55 views

Which is better ? Iterations or Recursions?

I've heard that any algorithm using iterations can be changed into one that uses recursions and vice-versa. But which type of repetition is preferable for minimum amount of computational effort and ...
0
votes
0answers
239 views

Shortest Uncommon Subsequence

Here is another GeeksforGeeks problem that asks how to find the shortest Uncommon Subsequence of 2 strings? For example, Input : S = “babab” T = “babba” Output : 3The subsequence “aab” of ...