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
2
votes
1answer
43 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
51 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
43 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
52 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
101 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
86 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
107 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
383 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
295 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
32 views
1
vote
0answers
60 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
67 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
246 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
73 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
170 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
110 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
33 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
188 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
44 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
71 views

Recursive factorial algorithm

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

Merge sort and quicksort 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
273 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
67 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
360 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
17 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
609 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
95 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
41 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
49 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
37 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
1k 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
74 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
262 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
2k 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
64 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
38 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
92 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: ...
1
vote
2answers
154 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
247 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
354 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
62 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 ...
4
votes
1answer
2k 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 ...
1
vote
0answers
31 views

Is this solution is bad for the coin change problem? [closed]

was doing coin change problem as an assignment(didnt know before), after came with this solution i checked the solutions available couldnt find a similar one like this, just curious. removing the ...
1
vote
1answer
162 views

Asymptotic bound of a recursive function

Consider the following procedure computing a dummy function. Which one is a correct asymptotic bound for the running time of F(N) expressed in terms of N? ...
1
vote
2answers
122 views

Time Complexity of the code

I am having trouble finding the time complexity of the below code. ...
0
votes
0answers
47 views

Understanding How to Flatten a Nested Function System

There are at least two ways to flatten out a nested function. Both of them need to keep a certain amount of state to accomplish this. The two ways are: By creating several boolean variables for each ...
14
votes
2answers
4k views

Will this program terminate for every Integer?

In a Part Test for GATE Preparation there was a question : f(n): if n is even: f(n) = n/2 else f(n) = f(f(n-1)) I answered "It will terminate for all ...
2
votes
1answer
2k views

Water Jug Problem

I was reading an article on Water Jug Problem. The problem is -You are given a m litre jug and a n litre jug where 0 < m < n. Both the jugs are initially empty. The jugs don’t have markings to ...

1 2 3 4 5 8