As of May 31, 2023, we have updated our Code of Conduct.

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
1 answer
18 views

Clarification of divide-and-conquer recurrence explanation in 'Introduction to Algorithms' (CLRS)

The following excerpt is from page 39 of the 4th edition of 'Introduction to Algorithms' (emphasis added): 2.3.2 Analyzing divide-and-conquer algorithms [...] A recurrence for the running time of a ...
user51462's user avatar
  • 101
0 votes
0 answers
26 views

How to Remove Left Recursion from this Grammar?

How to remove left recursion in the following Grammar: S→Bb/a B→Bc/Sd/e Im new to this, below is the way I'm doing it: ...
whoAsked's user avatar
0 votes
1 answer
57 views

How is there a paradox in the halting problem when you can trace it and it's very clearly non-halting?

Here's Alan Turing's halting problem in pseudocode: ...
Curious cat's user avatar
0 votes
1 answer
53 views

How to derive time complexity of the Recurrence Relation - T(n,m) = T(n-1,m) + T(n,m-1) + c

I know that, T(n,m) = T(n-1,m) + T(n,m-1) + c it's the recurrence equation of Longest Common Subsequence algorithm. And the time complexity of the LCS in case of recursive method is O(2^n+m). The base ...
Samiddha 's user avatar
0 votes
2 answers
96 views

Complexity of generating all subsets of size $k$ using recursion

What is the complexity of the following (Python) code, that builds the list L of all subsets of size $k$ of a given set? ...
Greg82's user avatar
  • 125
0 votes
0 answers
13 views

Finding a ArrayList Connection (representing Subway Lines) with Recursion

I have this ArrayList (called linArray) (and this only) that contains Subway exchange stations (first the station name and then the lines you can exchange to at that station): ...
BlueInundation's user avatar
0 votes
0 answers
25 views

Does a bijective function exists behind every recurrence relation?

Consider these 2 questions where recurrence relations can be applied: Q1) Given an (nxm) where n denotes rows and m denotes columns of a grid, find the number of unique paths ($a_{n,m}$) that goes ...
rustlecho's user avatar
0 votes
0 answers
28 views

How to solve recurrences of this type?

$T(n) = 2 T(\lceil \frac{2n}{3} \rceil) + T(\lceil \frac{n}{3} \rceil) + O(n log n)$ From the 3-ary recurrence tree, one can say that $T(n) \geq cnlog^{2}n$ for some constant c, using the shortest ...
Biggo's user avatar
  • 1
0 votes
0 answers
34 views

Is recursiveness always from bottom to top?

Lets assume dir a has dir b which has dir c. In a recursive deletion of these directories we ...
obligatory's user avatar
0 votes
1 answer
44 views

Complexity of recursive function that calls itself with it's own return value

Given the following code: int f3(int n) { if(n <= 2) return 1; f3(1 + f3(n-2)); return n - 1; } I was trying to find the time complexity and I got this ...
complexity's user avatar
1 vote
0 answers
96 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 ...
AmirHosein Adavoudi's user avatar
0 votes
2 answers
43 views

Types and programming languages: strange term construction?

Pierce's Types and Programming Languages has the following definition of terms: $$S_0=\emptyset$$ $$S_{i+1} = \{true,false,0\} \cup \{succ(t), pred(t),iszero(t)|t \in S_i\} \cup\{if(t_1)then (t_2)...
Hank Igoe's user avatar
  • 159
0 votes
0 answers
33 views

Programming language implementation challenge: is recursion harder than HOFs, or vice versa?

(Initially this question was on cstheory, but I was told cs would be a better fit, so posting it here.) All other things being equal, which of the following languages would be more challenging to ...
Hank Igoe's user avatar
  • 159
1 vote
3 answers
118 views

In theory, is it impossible, or possible (although ridiculously impractical), to inline recursive functions?

In an older question I asked about stack, the statement came up that recursive functions cannot be inlined (link). I am interested in whether this statement is actually true or not. I understand that ...
BipedalJoe's user avatar
0 votes
1 answer
30 views

Implementation of cantor set without recursion

I'm working on the implementation of a cantor set on a 2-dimensional plane. It looks like this. Honestly, There is the obvious algorithm for the cantor set, but it includes a recursive method call. ...
Winter Endless's user avatar
0 votes
3 answers
133 views

is there an O(n^2) approach to this problem?

Given an array of N elements, I need to split it into k subarrays, where k can be between 2 <= k <= N. A sub-array's score is determined by: (left boundary point - right boundary point of the ...
stillmute's user avatar
-4 votes
2 answers
31 views

Let F be a function defined for all nonnegative integers by the following recursive definition

Let F be a function defined for all nonnegative integers by the following recursive definition. F(0) = 0, F(1)= 1 F(n + 2) = 2F(n) + F(n +1), n>0 Compute the first six values of F; that is, write ...
Max's user avatar
  • 1
0 votes
0 answers
16 views

How to prune a tree of selective nodes without recursion, using a stack [duplicate]

I can't solve the following problem without recursion. I get that the solution has to do with making a list of nodes to process but that's where I get stuck. The problem is to remove all nodes from a ...
Ilias Karim's user avatar
0 votes
1 answer
101 views

Minimizing/Maximizing recursion depth for DFS

The idea for this problem comes from GATE CS 2014 Set-3 Q13. Given a graph, are there any heuristics to figure out a DFS traversal which has minimum/maximum recursion depth? Consider the graph from ...
Rinkesh P's user avatar
  • 980
1 vote
1 answer
103 views

Expected runtime of recursive algorithm with optional part

I have a randomized recursive algorithm which expected running time is $T(n)$. In particular, the recursion looks like this: $$ T(n) \leq \mathcal cn + R ,$$ where $R$ is a recursive term that depends ...
joeren1020's user avatar
0 votes
1 answer
55 views

Recursive DFS Problem

I have been struggling with this contest problem for awhile now which is found at this link: https://people.eecs.berkeley.edu/~hilfingr/programming-contest/pacific-northwest/2009/b.pdf Short summary ...
Stef Man's user avatar
0 votes
2 answers
46 views

How to find the runtime out of a recursion formula when using divide and conquer

In dived 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,b$ as well as by the question how to find f(n). ...
user153448's user avatar
-3 votes
1 answer
51 views

How to solve T(n)=2T(√n)+(loglogn)^2?

Trying to solve the recurrence, but no clue how to deal with the (loglogn)^2 part
Chris W's user avatar
0 votes
0 answers
34 views

Iterative algorithm for assembly index? [duplicate]

DOI: 10.3390/e24070884 provides pseudocode for computing the assembly index of an object. It is written as recursive algorithm, which might be fine. But I would like to implement an iterative version ...
Galen's user avatar
  • 125
0 votes
0 answers
30 views

Defining dynamic programming [duplicate]

Could we say that Dynamic programming is nothing but recursion + Memoization? Although the formal definition of dynamic programming is that the problem should have an optimal substructure property, ...
nicku's user avatar
  • 143
0 votes
0 answers
85 views

Tail call optimization via translating to CPS

I am struggling to wrap my head around this compiler technique, so lets say here's my factorial function ...
hello world's user avatar
1 vote
0 answers
40 views

The complexity of Steinberg's strip-packing algorithm

In reading the paper "a strip-packing algorithm with absolute performance bound 2", the author gives a recursion formula $T(l)=T(l')+T(l'')+O(min\{l'\log{l'},l''\log{l'}',l\})$, where $l'+l''...
Twilight7's user avatar
1 vote
2 answers
55 views

Can a strict right fold be implemented in a single loop?

A strict left fold is straightforward to implement as a loop, rather than with recursion: ...
Xophmeister's user avatar
2 votes
1 answer
79 views

Runtime complexity of permutation function

I am trying to find the asymptotic run time complexity of the following function which will return a list of all permutations of nums. ...
user1234's user avatar
1 vote
1 answer
149 views

How are regular languages not structurally recursive?

This blog posting states that "regular languages aren't structurally recursive" while "That's not the case for context-free grammars" In what sense is the term "structurally ...
user3414663's user avatar
0 votes
3 answers
78 views

Compute a commutative and associative operation on n-2 arguments efficiently

Considering a function $f$ such that: $$ f(x_1, x_2, x_3) = f(f(x_1, x_2), x_3) = f(x_1, f(x_2, x_3)) $$ and $$ f(x_1, x_2) = f(x_2, x_1) $$ and a set $X = \{ x_1, \dots, x_n \}$; how to compute $$f(...
fontanf's user avatar
  • 103
-1 votes
1 answer
45 views

Complexity of T(n)=2T(n-1)

I built a recursion tree like this: 0 / \ 0 0 /\ /\ ... ... So the tree has height n, and width $2^n$. But if the sum of all levels is $\sum_{i=0}^{n}...
BrKo14's user avatar
  • 1
0 votes
1 answer
76 views

Show that the function that counts the number of occurrences of 6 in a natural number is recursive primitive

I have to show that given $f:\mathbb{N}\rightarrow\mathbb{N}$ the function that returns the number of times $6$ appears in the input (for example $f(436546)=2$) is primitive recursive. The exercise ...
giggiox's user avatar
  • 11
0 votes
1 answer
39 views

Does a closed formula exist for each recurrent formula?

I'm interested in a question that probably lies close to the very concept of recursion. I have no idea whether my statement is true or false, neither I have tools to check it, so I'll just ask the ...
Rusurano's user avatar
1 vote
2 answers
68 views

Why is a recurrence of $2N_{h-2}$ equal to $2^{h/2}$?

I was watching video 7. Binary Trees, Part 2: AVL, where professor Erik Demaine stated that $$2N_{h-2} = 2^{h/2\text{ (or maybe with floor or something... maybe it's ceiling)}}$$ where $N$ stands for ...
Fausto Zamparelli's user avatar
1 vote
1 answer
157 views

A recursive relation for the number of well formed nested parentheses of length $n$ and depth $\leq d$

Consider a function $C(n, d)$ which counts the number of well formed, i.e, balanced, parenthetical 'words' of length $n$ and maximal nested depth $\leq d$. That is, $(())$ has $n = 4, d = 2$. $()((())(...
Haustiminus's user avatar
1 vote
1 answer
110 views

Am I drawing the recursion trees correctly?

I guess I've already figured out what is a recursion tree and how to construct one. Inspired by Figure 2.5 of "Introduction to Algorithms, 3rd Edition by CLRS", I drew some recursion trees ...
JJJohn's user avatar
  • 588
0 votes
1 answer
58 views

Recursive function - proof by induction

Let $\Sigma$ denote an alphabet and $[ \Sigma ]$ set of lists. I've encountered the following function: $f([])=[]$ (empty list) $f([x])=[x]$, for $x \in \Sigma$ $f(x:L)=f(L)$, for $x \in \Sigma$ and $...
Adamat's user avatar
  • 1
2 votes
1 answer
77 views

Trying to understand the basic about recurrence trees

I have little background on recurrence trees, and I am working on the following exercise: Exercise. Take $T(n) = 2T(n/2) + 3\log(n)$. Draw the recurrence trees for $n=2$ and $n=4$. What can we ...
Rodrigo's user avatar
  • 189
1 vote
3 answers
145 views

Recursive algorithm for adding numbers from 1 to n with O(1) time complexity

So I have a recursive algorithm which sums up the numbers from 1 to n plus one (hence the return 1): ...
maxig's user avatar
  • 13
0 votes
0 answers
31 views

Prove that a predicate is not computable

Prove that the following predicate is not computable: $P_e(n) = \begin{cases} 1 & \textrm{if } \phi_n(n) = e \\ 0 & \textrm{otherwise} \end{cases}$ Could someone explain how to approach ...
felifreee's user avatar
1 vote
0 answers
80 views

Recursive algorithm running time?

I would like your opinion on how to detect the T(n) (Running Time) for the following recursive algorithm. Charm is an algorithm for discovering frequent closed itemsets in a transaction database. A ...
Danilo Giovannico's user avatar
0 votes
1 answer
24 views

Termination condition for max of array using divide and conuqer approach

I want termination proof of divide and conquer approach to find max of array,I want equational proof in form of lemma.Below is my attempt.I have got accepted everything in dafny ,it is only pointing ...
user avatar
-3 votes
1 answer
82 views

Recursion problem T(n)=3T(n/3)+3n

I just need help solving this problem. I know I'm supposed to be using the Master's Theorem but I don't know where to start
Justin Fabusuyi's user avatar
0 votes
1 answer
198 views

Time complexity of merging two lists while preserving order

I have two lists l1 and l2 of possibly unequal sizes (say, m and ...
sam's user avatar
  • 9
0 votes
0 answers
39 views

What is the standard definition of recursive automata (or state machines)?

I found this paper: https://courses.engr.illinois.edu/cs373/fa2009/recaut.pdf But it looks like recursion is done along an edge. I would have thought you have state machines nested inside nodes. ...
Daniel Donnelly's user avatar
3 votes
1 answer
255 views

Skyline problem with triangular buildings

This question is based off of the usual Skyline problem, which is discussed in GeeksForGeeks and also several other websites. The following are two variations from the usual Skyline problem: Report ...
Fred Jefferson's user avatar
1 vote
1 answer
293 views

Tower of Hanoi variation - Split into two towers of odd and even disks

Suppose we have three rods A, B and C, and rod A ...
Daniel's user avatar
  • 119
0 votes
0 answers
26 views

recursive function without intermediate variables

The question was to convert this recursive code with intermediate variables to a functional program code without any intermediate variables. ...
Sanduni Aaloka's user avatar
0 votes
0 answers
18 views

Simple examples of Recursive Enumerable Functions

My understanding of Recursively Enumerable Functions is that they're recursive functions, but for some values of the arguments you put into the function they will stop and give an answer, and for ...
Spitzfire's user avatar

1
2 3 4 5
12