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
0 answers
16 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 ...
0 votes
0 answers
8 views

Skyline problem-Program going into infinite loop for some inputs [closed]

I am trying to solve the [skyline problem][1] using the divide and conquer approach. For some inputs (attached) the program goes into infinite loop, but some other inputs it is working correctly. I ...
-4 votes
0 answers
31 views

How exactly is am I supposed to see these recursive calls as a tree?

...
  • 1
0 votes
2 answers
25 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). ...
-3 votes
1 answer
36 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
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 ...
  • 103
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, ...
  • 19
0 votes
0 answers
55 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 ...
1 vote
0 answers
33 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''...
1 vote
2 answers
52 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: ...
1 vote
1 answer
50 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. ...
1 vote
1 answer
75 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 ...
0 votes
3 answers
72 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(...
  • 103
-1 votes
1 answer
41 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}...
  • 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 ...
  • 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 ...
1 vote
2 answers
59 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 ...
1 vote
1 answer
72 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$. $()((())(...
1 vote
1 answer
96 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 ...
  • 578
0 votes
1 answer
46 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 $...
  • 1
2 votes
1 answer
59 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 ...
  • 187
1 vote
3 answers
65 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): ...
  • 13
0 votes
0 answers
27 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 ...
1 vote
0 answers
79 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 ...
0 votes
1 answer
20 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 ...
's user avatar
-3 votes
1 answer
42 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
0 votes
1 answer
105 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
0 answers
34 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. ...
0 votes
0 answers
28 views

Why are we allowed to ignore constant factors of $g(x)$ in recurrence while they are important in solving the recurrence?

I'm trying to learn about asymptotic notations and recurrences and I use MIT 6.042 Mathematics for Computer Science as my resource. and I have some questions about the Professor's talks. He said: ...
  • 1
3 votes
1 answer
175 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 ...
1 vote
1 answer
116 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 ...
  • 119
0 votes
0 answers
24 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. ...
0 votes
0 answers
15 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 ...
7 votes
2 answers
3k views

Is the Berkeley tutorial on Fibonacci trees using wrong figures?

I'm confused about the figures in a Berkeley tutorial on Fibonacci trees, which depicts fibtree(2) as and fibtree(3) as I thought fibtree(3) looks like the following (the figure is adapted from ...
  • 578
0 votes
1 answer
61 views

Implementing a correct `let rec in` interpreter in Haskell with `eval` and `sub` semantics

I'm implementing the toy fb-lang from the principles of programming language book. It's a small interpreted language that uses eval(uate) expression function and <...
  • 109
0 votes
0 answers
22 views

Unusual approach to tabulation algorithm

Consider simple tabulation algorithm firstly for Fibonacci numbers. We will use the dictionary as a cache (and Python as example PL): ...
  • 101
13 votes
4 answers
3k views

Why is tail recursion better than regular recursion?

There is the axiom you should always prefer tail-recursion over regular recursion whenever possible. (I'm not considering tabulation as an alternative in this question). I understand the idea by why ...
0 votes
0 answers
110 views

Space complexity for divide-and-conquer

Here's a simple question but I'm not sure there is a simple answer. This came up in an undergraduate algorithms class. Consider the following divide-and-conquer algorithm $A$ (here, $x_1, \ldots, x_n$ ...
  • 101
0 votes
0 answers
26 views

Number of recursion of a recursive algorithm for input size $n/2$

There is a problem whose input size is $n$. The problem is solved in two steps. In the first step $n/2$ of inputs are eliminated in $O(n)$ and then in the second step, four different recursive ...
  • 1,427
1 vote
1 answer
33 views

Solve recurrence where the base case's time complexity is a function of the original input size

I'm trying to analyse the time complexity of the following algorithm for generating the power set: ...
  • 123
0 votes
1 answer
46 views

How to count the leaves of a tree without a outside function counter?

I got bombed in a interview because I was asked to write an algorithm which would count the leaves of a tree, I did this: ...
-1 votes
1 answer
80 views

Finding the number of ways to reach a particular position in a grid from a starting position (given some cells which are blocked)

I came across this question in a job interview and I couldn't solve it. In a n*m matrix some cells are blocked.The robot can only move in direction of (x-1,y+2) or <...
-1 votes
1 answer
533 views

Dynamic programming to find number of ways to divide string into primes

I am studying for final algorithms exam and saw this question: Given a string of length n consisting of digits [0-9], count the number of ways the given string can be split into prime numbers >= 2....
0 votes
1 answer
49 views

How can we get upper bound in terms of Big Oh notation using Master theorem?

The recursion is: T(n) = 5T(n/2) + O(n) I solved for the time complexity using Master theorem and found Θ(n^2). but, the question has asked to find the upper bound ...
0 votes
1 answer
54 views

How does primitive recursion handle mutual recursion?

My intuition is that you can't call a function that has not yet been defined, although I have yet to find a source confirming this. Is this true? Thanks, friends :)
  • 23
0 votes
1 answer
24 views

Recursive Bijections Between Countably Infinite Sets

The textbook I am currently studying (Introduction to Kolmogorov Complexity and Its Applications by Li and Vitanyi) uses the term 'recursive bijection'. In this context I believe that recursive refers ...
0 votes
1 answer
164 views

Is top-down dynamic programming always recursive?

I think top-down dynamic programming is mostly recursive (at least when we use memoization). For instance, solving the rod-cutting problem by this algorithm: ...
  • 377
1 vote
1 answer
92 views

Making use of one function to recursively find n/3 of another

Given an algorithm M that computes the median of an array A in O(n) time, describe an O(n) algorithm to repeatedly call M in order to find the element of rank n/3 in A. This is a problem I am tasked ...
  • 21
2 votes
1 answer
73 views

Are recursion and a stack equivalent in terms of inplementing DFS?

It is well known that DFS can be implemented either with recursion or a stack, and that both approaches are equivalent, but how far can we take that statement? Consider the following LeetCode problem: ...
  • 1,071
0 votes
0 answers
54 views

is there a theory consider on infinitely many recursion?

of course there is a theory that how many recursive calling the same system to solve problems, this theory is "recursion theory", If i know correctly. and recursion theory is computability ...

1
2 3 4 5
11