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
0answers
22 views

Egg dropping problem binomial coefficient recursive solution

I have a question about the binomial coefficient solution to the generalization of the egg dropping problem (n eggs, k floors) In the binomial coefficient solution we construct a function $f(x,n)$, ...
0
votes
0answers
18 views

File Systems (Operating Systems)

The figure below depicts the structure of a simple inode-based file system. Each rectangle represents a disk block of some fixed block size. In respect to this diagram, I am asked: (a): Does this ...
1
vote
0answers
23 views

Finding the closed form of this recurrence

We have the following recurrence $T$: $$ T(n,k) = \left\{ \begin{array}{ll} \alpha n^2 + \beta n + \delta & \quad \text{if }\; n \le k \\ T(\lceil n / 2 \rceil, k)...
1
vote
0answers
26 views

Hanoi towers recursive expression for EVERY algorithm

What the recursive algorithm for moving $n$ disks says, is: If $n > 1$, move $n-1$ discs from A to B. Move the $n$th disk from A to C. If $n > 1$, move $n-1$ discs from B to C. Let $T_n$ be ...
0
votes
1answer
17 views

Recursive Call Inside Argument List (C++) [closed]

So, my professor asked me to implement recursion in different ways to compute $a^n$ (a and n being integers) and rank them according to their space efficiency. Now, here is one of the methods I came ...
0
votes
0answers
28 views

Can every problem that uses recursion be solved using iteration? [duplicate]

We all know iterations and recursions are a powerful thing in programming. But this doubt always troubles me whenever I write an iteration or recursion. Can every recursive problem solved using ...
-4
votes
1answer
45 views

How to find the substitutions that convert the starting sequence into the final sequence? CCC19J5

Here is Canadian Computing Competition 2019 Junior problem 5 on dmoj.ca. You can also see the original problem at cemc.uwaterloo.ca as well. A substitution rule describes how to take a sequence of ...
1
vote
1answer
46 views

Removing recursion from a function with multiple params

I am given the following function as a brain teaser: ...
1
vote
0answers
18 views

Least constraining value heuristic in Sudoku [closed]

I was trying to implement Least Constraining Value Heuristic in Sudoku but wasn't getting the idea on how to do it. Can someone share their idea for the same ?
1
vote
0answers
44 views

How to prove a recursive's function Big-Theta without using repeated substitution, master theorem, or having the closed form?

I have a function defined: $V(j, k)$ where $j, k \in \mathbb{N}$ and $t > 0 \in \mathbb{N}$ and $1 \leq q \leq j - 1$. Note $\mathbb{N}$ includes $0$. $V(j, k) = \begin{cases} tj & k \leq 2 \\...
1
vote
2answers
55 views

How can I show h(n) = O( √ n)?

Is there any way to make recursion tree that satisfies the height $h(n) = h(n−\sqrt{n}) + 1$ to show $h(n) = O(\sqrt{n})$?
1
vote
1answer
17 views

Does a recursive call reset to the beginning of the method if the call is in the middle?

Or does it finish the method? Sorry for noob question.
2
votes
1answer
32 views

How does this recursive algorithm work?

One question from the Grokking Algorithms book: Implement a max([]int) function, returning the biggest element in the array. Here's my solution in Golang (adapted ...
0
votes
0answers
12 views

Manage nested recursions in the design of a concatenative language interpreter

I'm in the designing of an interpreter for a stack based concatenative language, and I'm currently stuck with a problem about recursion of some of my concatenative program to calculate factorial: <...
1
vote
1answer
129 views

Solving the recurrence relation T(n) = 2T(n/2) + nlog n via summation

I have seen a few examples of using the master theorem on this to obtain O(n*log^2(n)) as an answer. I am trying to solve this by unrolling and solving the summation, but I can't seem to get the same ...
1
vote
2answers
37 views

What is an example of a (simple) tail recursive algorithm that doesn't use a helper function?

I know one can compute things using tail recursion with helper functions like: ...
2
votes
2answers
77 views

Find both lower and upper asymptotic bounds for $T(n) = 2T(\frac{n}{2})+n^4$

So far we have learned Recursion Tree, Substitution Method, and Master's Theorem. I'm not sure how we can find lower AND upper bounds. I know that using Master's Theorem, we get $T(n) = \Theta(n^4)$, ...
3
votes
1answer
81 views

Solve recurrence relation that depends on depth of recursion

The specific problem I'm working on is the puzzle presented in this video. For those who don't want to watch the video, my summary of the puzzle is: A frog is sitting on the edge of a pond facing ...
3
votes
1answer
106 views

Distinct Binary Heaps

I have $n$ elements out of $n-1$ are distinct. The repeated element is either minimum or maximum element. I need to figure out how many distinct max heaps can be made from it. My analysis : I started ...
1
vote
3answers
75 views

How can any non-primitive-recursive function like the Ackermann function be implemented on hardware?

If for-loops and function calls both boil down to jump instructions when implemented on a real machine, then how is "The Ackermann function isn't implementable with for-loops" a meaningful phrase?
1
vote
1answer
21 views

Complexity of iterative exponentiation

I've watched multiple videos and read articles about recursion but I'm still confused. I've got this problem here but I'm unsure how to answer it: The following function calculates $x^n$ ...
0
votes
0answers
27 views

Is it still called “recursion” when you're using call-stack as a stack?

The most obvious way to solve a problem of balancing parentheses, like https://leetcode.com/problems/valid-parentheses/, is through a stack (a last-in-first-out (LIFO) datastructure). However, if you ...
3
votes
1answer
50 views

Is this lambda abstraction created as a generator of a recursive function?

In lambda calculus, a recursive function $f$ is obtained by $$ f = Y g $$ where $Y$ is the Y combinator and $g$ is the generator of $f$ i.e. $f$ is a fixed point of $g$ i.e. $f == g f$. In The ...
1
vote
0answers
41 views

Transforming an immutable binary tree without recursion [closed]

I'm struggling on this one. I have a Binary Decision Diagram, which is pretty much tree-like. Each node has a hi and lo node. I need to recurse into the tree, and if some conditions are the case ...
1
vote
1answer
46 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 ...
3
votes
2answers
84 views

Is there any recursive function f whose code is unique?

I am doing some reviewing for the term final on computability and found out this simple exercise. I am very fresh on theoretical computer science so if you do have an answer please make it simple. ...
1
vote
0answers
73 views

How to approach backtracking when using immutable types (Python)? [closed]

In Python when we are building a recursive algorithm that uses backtracking a mutable type such as a list is great to use. It can be modified at each call in our recursion tree, then returned back to ...
0
votes
2answers
51 views

Iteration vs Recursion question in Lisp method

I am curious if the following method would be called iterative or recursive: ...
2
votes
1answer
30 views

Turing Machine equivalence in MinTM proof

The proof with contradiction that $MIN_{\mathrm{TM}}$ is not Turing-recognizable from Michael Sipser's textbook "Introduction to the Theory of Computation" (Theorem 6.7) is as follows: $C=$ "On ...
1
vote
1answer
85 views

How to find the Big-O for finding combinations of balanced parentheses?

Given n pairs of parentheses, a function which returns the total number of all combinations well-formed parentheses could be: ...
0
votes
1answer
73 views

Count the number of ways numbers 1,2,…,n can be divided into two sets of equal sum

count the number of ways numbers 1,2,…,n can be divided into two sets of equal sum. This is my recursive algorithm, what is wrong here?: ...
2
votes
2answers
43 views

How to use Master Theorem with strange format of $b$ parameter?

I have a funcion $T: \mathbb{N}\to\mathbb{N}$ defined as: $$T(n)=\begin{cases} 6 &\text{ if } n=0,\\ T(n-1) + 6n + 6 &\text{otherwise.} \end{cases}$$ How can I apply the Master Theorem to ...
2
votes
2answers
90 views

Prove that $T(n) \leq 8n^2$ or find value of $n$ when statement is not true (recurrence relation)

We have a function $T: \mathbb{N}\to\mathbb{N}$ defined recurrently: $$T(n)=\begin{cases} 0 &\text{ if } n=0,\\ 3T(\lfloor{n/2}\rfloor) + 2n^2 &\text{otherwise.} \end{cases}$$ Prove that for ...
2
votes
1answer
169 views

Are all foldable data structures also recursive?

I was checking what Wikipedia has to say on reduce. It says: In functional programming, fold (also termed reduce, accumulate, aggregate, compress, or inject) refers to a family of higher-order ...
1
vote
1answer
79 views

Assigning $m$ balls to $n$ buckets - recursive algorithm

I came across the following problem and the answer to that problem: Given $m$ balls and $n$ bins, find out how many ways to assign the balls to the bins. Notice the bins have no order: for example, ...
1
vote
1answer
84 views

Given price and number of pages of each book, What is the maximum number of pages you can buy?

You are in a book shop which sells n different books. You know the price and number of pages of each book. You have decided that the total price of your purchases will be at most x. What is the ...
1
vote
0answers
37 views

How to solve 2 variable recursion?

T(m,n) = T(m-1,n) + T(floor(m/2), n-1) Base conditions T(m,n) = 1 when n = 0 T(m,n) = 0 when m < n Edited: Below is the code for which I want to know the time complexity in terms of m and n. <...
0
votes
2answers
143 views

What is the height of a tree with recursion formula: $T(n) = T(n - \sqrt{n})$

I know if the time complexity of an algorithm is given with the above formula, then the algorithm works in constant time but my question is that what will be the height of the recursion tree for this ...
2
votes
1answer
56 views

Number of Function Calls In Recursive Code

I am new to recursion. I am doing some practice questions and I was wondering what the technique is for going from some recursive code to identifying the number of function calls it makes. ...
2
votes
1answer
39 views

Understanding proof of upper bound on complexity of recursive computation of graph chromatic polynomial

This question is about section 2.3 of Wilf's ``Algorithms and Complexity'' https://www.math.upenn.edu/~wilf/AlgoComp.pdf in which he analyses the complexity of a recursive computation of the ...
2
votes
1answer
55 views

What is the closed-form expression for $T_n = \left(\sum_{i=1}^{n-1}7 T_i\right) + 1$ where $T_1 = 1 ?$ [closed]

Problem: Find the closed-form expression for$$ T_n = \left(\sum_{i=1}^{n-1}7 T_i\right) + 1 \tag{1} $$where $T_1 = 1 .$ Calculating this sum I came up with the following result: $$ T_n = 8^{\left(...
2
votes
1answer
49 views

Is there purely recursive functions? [duplicate]

Is there any problem that can be only solved with recursion, and not with iteration? (haven't been able to find anything online). If there isn't any, is there a reason why? Thanks in advance!
2
votes
1answer
40 views

Computability: Proving a predicate is not recursively enumerable

Let P(p) <=> for each x, comp(p,x) is defined. Can anyone explain to me how to prove that P is not RE (recursively enumerable) ?
0
votes
1answer
48 views

Multiple choices for a single case in the recursive formula of a Dynamic Programming algorithm

I am developing a Dynamic Programming algorithm for a problem in scheduling. In the recursive formula, I have three cases: (1) $t_{i-1} = int$ (2) $t_{i-1} = app \quad \& \quad r(j) \leq p $ and (...
0
votes
1answer
64 views

Recursive definition for the length of a string?

I found a couple of answers online but I don't quite understand why the answer is right: The length of a string is: If a string has no characters, then its length is 0. Otherwise, the length of the ...
0
votes
0answers
82 views

Write the Brute Force Recursive Code to generate the longest substring containing k distinct vowels

Given a string s we have to find the length of the longest substring of s which contain exactly K distinct vowels. This is the problem statment given on geeksforgeeks Input : s = “artyebui”, k = 2 ...
1
vote
1answer
89 views

Avoiding “side effects” in recursive functions

I am writing a function to find the intersection between two sets. The non-functional requirements of the assignment include avoiding "side effects". ...
0
votes
0answers
13 views

T(n) = T(n-1) +3n^2 - 2n +1 [duplicate]

I was wondering how do I solve this, I've been trying any possible way to but I've failed: $$\begin{align*} T(n) &= T(n-1) +3n^2 - 2n +1 ,& n \ge 1 \\ T(0) &=2 &\\ \end{align*}$$
6
votes
1answer
321 views

Worst-case input for median-of-medians with groups of size 3

Typically, median of medians algorithm is written with groups of size $5$ or $7$ to ensure worst-case linear performance. The argument against groups of size $k=3$ is typically that we get a ...