Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [recursion]

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

1
vote
1answer
53 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 ...
0
votes
0answers
18 views

Method for optimizing many levels of iteration where some combinations can be discarded

I have the following problem which I wish to optimize: Find the value $n$ for which the function $f(n)$ is maximized, where $0 < n < 3^{36}$. An optimization is possible, given that when ...
-1
votes
0answers
11 views

cyclomatic complexity of resursive function

My aim is to find the cyclomatic complexity of the code,but this involves a recursion so i am confused whether the recursive statement will take it to the beginning in cfg. Can anyone confirm..i have ...
2
votes
2answers
32 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
36 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
0answers
14 views

time complexity of recursive algorithm with loop [duplicate]

For approximating a recursive algorithms time complexity i found some great techniques e.g. here. But i'm not sure how one to get the time complexity of a recursive algorithm with a loop in it. For ...
0
votes
0answers
22 views

Can any recursion implementation be written into a bottom-up DP implementation?

Can any top-down recursion implementation be written into a bottom-up DP implementation?
0
votes
1answer
65 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 ...
0
votes
0answers
40 views

What's the lower bound of the height of an unbalanced recursion tree?

I don't understand what's going on here. People say, longest path should yield an upper bound of tree height while shortest path should yield a lower bound of tree height. Please take a look at https:/...
0
votes
0answers
24 views

knapsack type solution to the 8 queens problem

I'm new to learning programming, and came across this problem of placing 8 queens on a chessboard, such that no two queens are on the same row, column or diagonal; i.e. no two queens attack each other....
-1
votes
2answers
33 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
0answers
29 views

Recursion func to get list of objects

I want to write code that returns a list of $X_i$ values base on this logic. Assuming $X> 1$ a positive non decimal number, and $n$ is the number of objects: $X_n = X-X_1$ $X_i = X_{i+1} / 2$ $...
0
votes
0answers
27 views

Big-O of a recursive function [duplicate]

just wondering, what's the big o of this function, let say the initial value of the parameters is as following: ...
0
votes
1answer
22 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
76 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
0answers
50 views

What is the time complexity of this power algorithm?

I'm trying to learn more about time complexity of algorithms on my own, but it comes very confusing when recursion gets into it. The power function calculates $x^...
0
votes
2answers
35 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
81 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
86 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
22 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 ...
2
votes
1answer
164 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
27 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
42 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
70 views

Time Complexity of the code

I am having trouble finding the time complexity of the below code. ...
0
votes
0answers
29 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
3answers
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
487 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 ...
-2
votes
1answer
46 views

Solving double recurrence relation

How to calculate the rate of growth of the below function $f(x)$? $$ \begin{align*} f(x) &= \begin{cases} f(x-1) + g(x) & \text{if } x > 1, \\ 1 & \text{if } x \leq 1. \end{cases} \\ g(...
2
votes
0answers
24 views

Reference request: Leaf-heavy master theorem algorithms

I know many algorithms that can be analyzed using master theorem, but the only algorithm I know where the time is dominated by the leaves is fast matrix multiplication. Are there other recursive ...
0
votes
1answer
145 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 ...
0
votes
2answers
40 views

Recursive relations in binary trees

I have an exercise in my algorithm's Course for which I have the correction but do not understand it. 1.Exercise . Let Th be a full binary three of height h(meaning all the levels all completely ...
1
vote
0answers
362 views

Longest increasing subsequence (Dynamic Programming)

I have written the following recursive structure for finding length of longest increasing subsequence. ...
4
votes
0answers
46 views

The evolution of the term “recursive” from Goedel to Church to present day

I'm currently studying some of the history of computation / computability, in the early days known as recursion theory. I see Goedel's definition of recursive functions seems significant in his paper,...
0
votes
0answers
27 views

Recursive formula for finding ways to spend x amount of money on y items [duplicate]

So far, i've only made recursive formulas for finding simple patterns such as fibonacci, however i can't seem to get my head around this. The information available is that there are $n$ different ...
0
votes
2answers
164 views

Making a recursive formula for finding amount of ways to spend money on beer

So far, i've only made recursive formulas for finding simple patterns such as fibonacci, however i can't seem to get my head around this. The information available is that there are $n$ different ...
0
votes
0answers
38 views

Demonstrate that algorithm is O(n)

So i have this algorithm that checks if an binary tree is a binary search tree: ...
3
votes
2answers
57 views

Alan Perlis Epigram on Recursion

So, while trying to dive into "recursion" and the like, I came across an epigram about recursion by Alan Perlis: Recursion is the root of computation since it trades description for time. -- ...
0
votes
2answers
51 views

Proving the correctness of a square summing algorithm

int sumHelper(int n, int a) { if (n==0) return a; else return sumHelper(n-1, a + n*n); } int sumSqr(int n) { return sumHelper(n, 0); } I am supposed ...
0
votes
2answers
429 views

How does in-order traversal in Binary search tree works (recursion)

I visit some question but their implementations are slightly different and my doubt is not like theirs. I have this code in Javascript. The code is typical BST implementation with methods to support ...
1
vote
1answer
141 views

Understanding Martin Farach's suffix tree algorithm

I feel stuck at this point. I have spent several days trying to get my head around the algorithm, but both resources I have [1] [2] seems to skip over whatever details that would make me comfortable ...
0
votes
0answers
78 views

Proof of correctness recursive reverse digit function

This is an attempt to understand better recursion. The following recursive function returns the integer obtained by reversing the digits of an input integer. I'm trying to prove its correctness: <...
1
vote
1answer
35 views

Number of calls with length 2 array in quick-sort

I need to find average number of recursive calls in quick-sort with array of length 2. I established and solved the following recursion: $$T_N = \frac{1}{N}\sum_{k=1}^N\left(T_{k-1}+N_{N-k}\right) = \...
1
vote
1answer
25 views

Recurrence equation calculation

I have a recurrece equation Changed notations: $\qquad\displaystyle G(W) = \max \{ G(W - s_i) + v_i \mid 0 \leq i \leq n, w_i \leq W \}$, I am not sure if I understand $\ w_i $ correctly. On each ...
1
vote
1answer
153 views

Finding the longest overlapping interval pair

Say I have a list of $n$ integral intervals $[a,b]$ where each represents a set $S = \{a, a+1, \ldots, b\}$. An overlap is defined as $|S_1 \cap S_2|$. Example: $[3,6]$ and $[5,9]$ overlap on $[5,6]$ ...
3
votes
1answer
44 views

Generating all words of length $n$ avoiding $A^2$ and $B^3$

I need to find a way to iterate over all sequences of words in two letters $A,B$ avoiding the sequence $A^2 = AA$ and $B^3 = BBB$. First of all, what is the regular expression for such a thing? I ...
1
vote
1answer
41 views

How can I prove that $T(n)=\sqrt{n}T(\sqrt{n})+n$ grows as $\Theta(n\log \log{n})$? [duplicate]

How can I prove that if $T(n) = \sqrt{n}T(\sqrt{n}) + n$ then $T(n) = \Theta(n\log\log n)$? I tried to define $T(n)$ by $G(n)$, prove about $G(n)$, and then to return to $T(n)$, but it's not working.....
1
vote
0answers
20 views

Knight's Tour Parberry algorithm: 4 knight's tour merge procedure

I'm implementing Parberry's algorithm for closed Knight's tour problem. Brief idea of the algorithm: split the board in $4$ parts, find the tour on them recursively then delete $1$ edge in each part ...
0
votes
0answers
102 views

Doubt on analysis on time and space complexity of creating n² tuples

This is a question from a past-yr mid-term paper from my school(using Python language). Attached below is a diagram to show how a robot will move. Don't mind if the link seems dubious as I just used ...
9
votes
2answers
364 views

How to derive dependently typed eliminators?

In dependently-typed programming, there are two main ways of decomposing data and performing recursion: Dependent pattern matching: function definitions are given as multiple clauses. Unification ...
2
votes
2answers
259 views

Solve every problem with recursion [duplicate]

Is it possible to solve every problem (solvable with turing machine) with only recursion ? If yes, which principles or theories assure this ? Thanks