# Questions tagged [recursion]

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

581 questions
Filter by
Sorted by
Tagged with
41 views

### Trying to implement BFS and I am stuck

I am trying to write down a code which would blindly search for a condition using breadth first search.I have been thinking of it for quite some time and I cant figure out how to continue. On the one ...
12 views

### Better implementations for this dynamic program to solve optimization problem?

In the code below, I describe a problem and provide a backtracking implementation in Python that solves it: ...
• 181
54 views

### Similar problem to Knight's tour

You have board size and one Knight but what is different is that when you move it you have to duplicate the knight and the 2 duplicates have to be in valid position from the knight This gets repeated ...
1 vote
35 views

### Complexity of simulations in simulations

This video of a group, who simulated (a very simple version of) Minecraft inside Minecraft itself got me thinking about the performance of such setups. Another example to what I'm referring to, would ...
45 views

### Prove $T(n)=2T(\dfrac{n}{2})+\Theta(n\log{n})=\Theta(n\log^2{n})$ using induction

Please first take a brief look at my previous question. Here I want to do something similar but for $T(n)=2T(\dfrac{n}{2})+\Theta(n\log{n})$. I know the answer is $T(n)=\Theta(n\log^2{n})$ and I want ...
68 views

### Checking equality of self-referential lists

Define that an srlist ("self-referential list") over $X$ consists of a list of elements of $X \sqcup \mathrm{srlist}(X).$ So basically, the items can be primitive values, or further self-...
1 vote
146 views

### Understanding the Recursive Algorithm for Integer Division

In my reference, Page 26, Algorithms by Sanjoy Dasgupta, Christos H. Papadimitriou, and Umesh V. Vazirani, a division algorithm is give as, \begin{align} &\text{function divide}(x, y)\\\\ &\...
• 139
1 vote
50 views

### Diffucuty in understanding code after a recursive call

This is an example algorithm of a recursive insertion sort I'm trying to understand. I've have tried understanding this with the help of print statements (which I've commented). ...
1 vote
54 views

### Are there situations where we can decrease the time complexity of a program by increasing its ordinal complexity?

Are there (interesting) situations where we can decrease the time complexity of a program by increasing its ordinal complexity? For example, is it possible to find a primitive recursive function such ...
• 177
86 views

### When to do proof by structural induction Vs defining a recursive function?

I'm trying to isolate the key differences between induction and recursion so that I am able to know when to use one over the other. From my understanding, both can be used to prove properties about ...
• 165
36 views

### Can proofs by induction be achieved by defining a recursive function between two recursive objects?

I have two types of objects, X and Y, each are recursive structures, and contain different structures sets of tuples containing sets.. etc. The number of elements in X and Y are is the same. I need to ...
• 165
1 vote
72 views

### Having trouble on logic behind recursion

I am struggling to write my own recursive function.I understand how to find the base case but I cant find easily the pattern on the relationship between 2 complicated cases.Do you know any website ...
• 143
34 views

### Are recursive Horn clauses first order?

My understanding is that recursive definitions are considered second-order since they require the fixpoint operator in order to be formulated as "true" definitions. This is even though they ...
• 272
82 views

### Change of associativity for a given right-recursive grammar

In section 3.7.1, of the book titled: Compiler design in C, by Allen I. Holub (made available freely online, by the author here, & the page #19 of errata, here), have on page #176, the mention of ...
• 187
40 views

### Is my mathematical representation of search in binary search tree correct?

You are given the root of a binary search tree (BST) and an integer val. Find the node in the BST that the node's value equals <...
• 113
1 vote
54 views

### Understanding the Internal Stack Frames in a Recursive Function Call

I'm trying to understand how the system's call stack works internally when a recursive function is called. Specifically, I'm looking at a function that computes the maximum depth of a binary tree ...
• 113
29 views

### Binary search calculating complexity big o

I'm studying recursion and a i have a doubt about the running time complexity of the binary search. I didnt understand this passage in my book : ...
• 1
67 views

• 179
36 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 ...
• 179
1 vote
150 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 ...
• 133
39 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. ...
136 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 ...
57 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 ...
• 1
127 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 ...
• 1,018
116 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 ...
76 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 ...
71 views

### Finding the runtime out of a recursion formula when using divide-and-conquer

In divide-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$ and $b$, as well as by the question of how to ...
• 113
66 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 ...
• 125
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, ...
• 143
134 views

### Tail call optimization via translating to CPS

I am struggling to wrap my head around this compiler technique, so let's say here's my factorial function ...
• 235
1 vote
43 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
60 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: ...
• 413
133 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. ...
• 21
1 vote
208 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 ...
• 111