# Questions tagged [recursion]

Questions about objects such as functions, algorithms or data structures that are expressed using "smaller" instances of themselves.

547 questions
Filter by
Sorted by
Tagged with
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 ...
8 views

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

I am trying to solve the [skyline problem] 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 ...
31 views

...
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). ...
• 113
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
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
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
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 ...
• 195
1 vote
33 views

1 vote
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
46 views

• 1,427
1 vote
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
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: ...
• 251
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 <...
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....
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 ...
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
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 ...
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
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
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