Questions tagged [recursion]

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

1
vote
2answers
33 views

Prove that $T(n) \leq 8n^2$ or find value of $n$ when statement is not true (reccurence 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 ...
0
votes
0answers
120 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
35 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
59 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
71 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
49 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
23 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
54 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
39 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
26 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
45 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
26 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
39 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
61 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*}$$
5
votes
1answer
160 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 ...
0
votes
2answers
135 views

prove by induction that the complete recursion tree for computing the nth Fibonacci number has n leaves

I have referenced this similar question: Prove correctness of recursive Fibonacci algorithm, using proof by induction *Edit: my professor had a significant typo in this assignment, I have attempted ...
0
votes
0answers
31 views
1
vote
0answers
41 views

Is McCarthy Formalism first ever formalism for defining functions recursively in computer science?

McCarthy formalism is a formalism for defining functions recursively, first introduced in classic paper Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I (1960). ...
1
vote
1answer
33 views

Whether it's necessary for a grammar to be ambiguous when it is both left recursive and right recursive

I read somewhere that if a grammar is left recursive as well as right recursive, then it is not necessarily ambiguous. I couldn't make up my mind on this statement. How can a grammar which is both ...
2
votes
1answer
128 views

Can memoization be applied to any recursive algorithm?

I am new to the concepts of recursion, backtracking and dynamic programming. I am having a hard time understanding if at all I can apply memoization to a particular recursive algorithm and if there ...
0
votes
0answers
45 views

Dynamic Programming solution for finding shortest distance to travel between points

So consider a person located at point $c$ (let's say $c=140$). Given a set of other points, for example, $P = \{100, 50, 190\}$. The cost of traveling to a point $P_i$ is then $|c-P_i|$. Points can be ...
0
votes
1answer
50 views

Recursively edit 2-D array using backtracking

I have a 2-D array which contain 3 types of elements: C (Contaminant) R (Rock) W (Water) The rule is that: contaminant can seep through water but not through rocks. Let's say I have the ...
2
votes
2answers
57 views

Recursion to DP Solution

There's a problem in Kleinberg & Tardos's Algorithm Design (Chapter 6, Question 4) where you are running a lightweight consulting business that has two offices: NYC and SF. In month $i$, you'll ...
2
votes
1answer
32 views

Maximum Expected Fishing Day (Recurrence Relation)

John joined a meetup where organize day long fishing trip once a month. The organizers are vary poor at planning, so will organize fishing on a random day of the month without any advance notice. ...
7
votes
4answers
143 views

What is the depth of recursion if we split an array into $\log_2(n)$ with each recursive call?

We have a function which takes an array as input. It breaks an array into $\log_2(n)$ parts with equal sizes where $n$ is the size of the subarray. It keeps breaking each of the subarrays until there ...
2
votes
1answer
40 views

Is there a relation between the size of the domain/range of a function and its computability?

This was a question given in a course, without answer. The referenced literature (just a few books) do not cover it, unfortunately. I think there is no relation with the range as the range of the ...
0
votes
1answer
60 views

Recursive factorial algorithm

I'm struggling to understand this factorial algorithm. ...
0
votes
1answer
121 views

Merge sort and quciksort recursion tree depth

1) I need to determine recursion tree depth for strings composed of 10, 100 and 1000 elements when using merge sort. For the 10 elements one I can do it on a paper, just drawing tree, but what about ...
2
votes
1answer
109 views

Induction to prove equivalence of a recursive and iterative algorithm for Towers of Hanoi

Using induction how do you prove that two algorithm implementations, one recursive and the other iterative, of the Towers of Hanoi perform identical move operations? The implementations are as follows....
0
votes
3answers
54 views

Which is better ? Iterations or Recursions?

I've heard that any algorithm using iterations can be changed into one that uses recursions and vice-versa. But which type of repetition is preferable for minimum amount of computational effort and ...
0
votes
0answers
141 views

Shortest Uncommon Subsequence

Here is another GeeksforGeeks problem that asks how to find the shortest Uncommon Subsequence of 2 strings? For example, Input : S = “babab” T = “babba” Output : 3The subsequence “aab” of ...
0
votes
0answers
16 views

Is there a specific search paradigm for finding pairs in a set?

I'm dealing with a very common problem in computer programming that involves, for example 4 people to be divided into 2 pairs. Mathematically, this is just a permutations problem, and the number of ...
2
votes
2answers
184 views

Technique for converting recursive algorithm to DP

I'm new to Dynamic Programming and before this, I used to solve most of the problems using recursion(if needed). But, I'm unable to convert my recursive code to <...
2
votes
2answers
72 views

Algorithm for generate all solutions to a linear Diophantine equation

Consider the linear Diophantine equation of the form: $$\sum_{i=1}^{k}a_ix_i=n.$$ My goal is to list all the non-negative solutions to this equation. I wrote the following recursive algorithm, but I ...
1
vote
1answer
36 views

Polynomial time algorithm - Matching pairs of vertices

Let T be a tree with root r and S a set with an even number of vertices of T. Design a polynomial time algorithm that finds |S|/2 simple and disjoint paths in edges matching pairs of vertices in S. ...
1
vote
3answers
47 views

Write a routine to print the numbers 1 to 6 and back to 1 again without using any loops [closed]

Can anyone help with this question? I currently have this solution that prints 1 2 3 4 5 6 but I'm having trouble going back down to 1. ...
-2
votes
1answer
32 views

Few questions about Mergesort and Recirsion algorithms

Can we use recursive algorithm to find the greatest element of a finite list when numbers are unsorted. How to use recursive algorithm to find the least element of a finite list of unsorted numbers ...
1
vote
1answer
272 views

How to solve F(n)=F(n-1)+F(n-2)+f(n) recursive function?

Like in the title the following equation: F(n)=F(n-1)+F(n-2)+f(n) F(0)=0, F(1)=1 ...
2
votes
2answers
49 views

Possible to use Master theorem? $T(n) = aT(\lfloor \frac{n}{b} \rfloor) + g(n)$

The master theorem can be used in case of a recurrence relation of the form $T(n) = aT(\frac{n}{b}) + g(n)$ But is it possible to use the master theorem for recurrence relations of the form $T(n) = ...
0
votes
1answer
160 views

Handling epsilon productions in recursive descent parsing

I am working on a recursive descent parser for lambda calculus. In my grammar, after removing left-recursion, I am left with the following two productions: ...
0
votes
1answer
731 views

Complexity of finding a majority element

I was given a question that is stated that; Suppose you’re consulting for a bank that’s concerned about fraud detection, and they come to you with the following problem. They have a collection ...
-1
votes
2answers
55 views

Using Iterative method to find recurrence relation vs Master Theorm

I'm trying to solve this recurrence relation using the iterative method and i keep getting the different answer from using the master theorem. $$\begin{aligned} T(n) &= 5T(n/2) +n^2 \\ &=...
0
votes
1answer
29 views

Is any State Space Tree always Binary Tree?

A backtracking algorithm generates, explicitly or implicitly, a state-space tree. Introduction to the design & analysis of algorithms / Anany Levitin I wonder that whether the saying ...
1
vote
1answer
85 views

Answering questions about the recurrence of certain aspects of an algorithm

I am thoroughly confused by a problem that was brought up in class: Given the following pseudocode for a function RANDOM which generates a random number based off of recursion: ...
0
votes
2answers
92 views

Pancake Sorting Graph Recursive Definition

I'm having trouble understanding exactly how the graph for Pn (where n = number of pancakes) is defined recursively for n>= 4. I can see obviously that, in the case of n=4, there will be 4 rough ...
1
vote
3answers
102 views

Time complexity of function vs return value

I came across following problem: Find the time complexity of below recurrence relation: $T(n)=\begin{cases} & 2T(n/2)+C; & n>1\\ & C;&n=1 \\ \end{cases}$ The solution ...
-1
votes
1answer
203 views

Finding recurrence equation for a variant of insertion sort [closed]

I have a variant of Insertion sort (recursive version) that we call split insertion sort because there are two kinds of input. The input array has both numbers and alphabets, hence we have to sort ...
1
vote
1answer
37 views

How to implement recursive solution with large number or parameterized possible next steps

I was looking at a recursive solution for the robot on a grid problem which basically states that there is a robot on the top left corner on a grid and you are supposed to find a path to the bottom ...