# Questions tagged [recursion]

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

583 questions
Filter by
Sorted by
Tagged with
36 views

### Implementation of the divide-and-conquer principle for a specific summation formula

I have found two formulas in the work on pages 5 and 6, of which I am trying to develop a recursive implementation. The similarity to the DFT or FFT might be useful here. I divide this question into ...
2k views

### Prove Recursive formula (Dynamic programming) N(C,i)

I've been asked to prove the correctness of the following recursive formula. The formula is trying to define, how many ways you can spend your money C on the i amount of beers. I did the following ...
37 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 : ...
26 views

### Which of the following statements about computable functions is true? [closed]

Assume that $f: \mathbb{N} \to \mathbb{N}$ is total and $g: \mathbb{N} \to \mathbb{N}$ is primitive recursive and $h: \mathbb{N} \to \mathbb{N}$ is Turing computable. Which of the following statements ...
53 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 ...
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: ...
55 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 ...
117 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 ...
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 ...
77 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 ...
1 vote
110 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 ...
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
111 views

### Understanding recursion tree for withdrawal formula

$$T(n) = T(n-a) + T(a) + cn$$ Now the solution says that the height of the tree $(h)$ is: $$h = \left \lfloor n/a \right \rfloor$$ And I don't understand why. Maybe I didn't understand the ...
1 vote
157 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)\\\\ &\...
73k views

### What is most efficient for GCD?

I know that Euclid’s algorithm is the best algorithm for getting the GCD (great common divisor) of a list of positive integers. But in practice you can code this algorithm in various ways. (In my case,...
1 vote
98 views

### Using inductive hypothesis on recurrence relation?

I have a recurrence relation as follows $$T(n) = 2T(\lfloor n/2\rfloor) + n\log(n)$$ Using the induction hypothesis how do I obtain a relation $T(n)\leq E$ such that $E$ contains neither $T$ nor floor ...
1 vote
52 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). ...
87 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 ...
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 ...
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 ...
135 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 ...
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 ...
36 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 ...
70 views

### Need help with recurrence relation and postcondition of a function

I just wanted to make sure I'm on the right track regarding this. Here's the function that I'm dealing with: ...
441 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 ...
1k views

### Recursive Algorithm Copying Array vs. Time Complexity

If I am implementing binary search using a recursive algorithm on an array it will be bounded by $O(\log(n))$. However, what will occur if the array is NOT passed by referenced and rather by value. ...
88 views

### What are the guidelines/tips for calculating the complexity of a chained-recursive function?

Any help will be appreciated, as I wasn't able to find much about it online in the last few days and I can't seem to write a suitable recurrence relation for this kind of functions.. Are there any ...
84 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 ...
73 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 ...
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 <...
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 ...
68 views

### Finding asymptotically tight upper bound of a recursion relation

Find an asymptotic tight upper bound for the following recursion relation: $$T(n)=5T(\frac{n}{5})+\log^2(n)$$ I tried to solve it by applying iteration: T(n)=5T(\frac{n}{5})+\log^2(n)=5(5T(\frac{n}{...
12k views

### Iteration can replace Recursion?

I've been seeing all over stack Overflow, e.g here, here, here, here, here and some others I don't care to mention, that "any program that uses recursion can be converted to a program using only ...
57 views

### Programs with feedback?

Suppose we have a program like this: ...
33 views

### Axiomatically, what characterizes “recursion”?

My question is admittedly simple, but the desire is to have an insightful view on it behind a conventional definition. In different foundational or axiomatic systems, I have come to consider “...
1 vote
63 views

### Justification for the properties of algorithmic recurrences in 'Introduction to Algorithms' (CLRS, 4e)

The fourth edition of 'Introduction to Algorithms' defines algorithmic recurrences on page 77 as follows: **Algorithmic recurrences [...] A recurrence is algorithmic, if for every sufficiently large ...
8k views

### What's the Big O runtime of a DFS word search through a matrix?

The problem is to try and find a word in a 2D matrix of characters: Given a 2D board and a word, find if the word exists in the grid. The word can be constructed from letters of sequentially adjacent ...
52 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: ...
178 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? ...
68 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: ...
1 vote
106 views

### How to generate tree variants of a tree using recursion?

I have a tree T, I need to generate all possible variants of T by permuting all its child nodes(please refer the following figure). how can I generate all variants, T, using recursion? any help is ...
67 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 ...
316 views

### Time complexity of merging two lists while preserving order

I have two lists l1 and l2 of possibly unequal sizes (say, m and ...
14 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): ...
26 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 ...
29 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 ...