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
2answers
204 views

Why is there no “traditional”-mathy way to describe the general algorithm and give a more math-friendly definition of algorithm?

Why is there no algebraic definition of algorithm besides recursive functions? If I'm wrong, what is the matheist definition of algorithm that you've ever seen in a paper and can you provide a link? ...
0
votes
0answers
21 views

Recursive approach of longest common subsequence

I tried to solve Longest common subsequence problem using recursion, however as I later discovered, my thinking approach was wrong. I took 2 strings say s1 and s2 with lengths l1 and l2, s1="...
0
votes
1answer
20 views

How do I work out the recurrence relation of the given function?

I am looking to find the recurrence relation of the following function: ...
0
votes
0answers
21 views

Python 3: Directly returning a list after removing an element [closed]

Suppose I have a list X = [8,1,5,3]. I want to remove item at index 0 from the list and return it directly using a function f. ...
-1
votes
1answer
28 views

Placing k Queens in a board, recursive problem

This is my first post here, Im a math student and I just took my first computer science course (introduction), so I apologize in advance if I'm asking something in a way that is not acceptable here. I ...
0
votes
1answer
32 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: ...
1
vote
1answer
36 views

How to perform AND on binary “recursive repeating sequences”?

Suppose, we have a two binary sequences, encoded as "recursive repeating sequences" (I don't know exactly how to name them). Each sequence can contain other sequences and has number related ...
1
vote
1answer
53 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 ...
1
vote
1answer
11 views

Induction on recursive formula

Okay so I have this recursive formula $T\left(n\right)=T\left(\frac{n}{2}\right)+O\left(n\right)+O\left(n\right)+2*O\left(1\right) \ \ \ ➜ \ \ \ T\left(n\right)=T\left(\frac{n}{2}\right)+O\left(n\...
-1
votes
1answer
46 views

Solve the following recurrence

I'm trying to solve this the recurrence : $$ T(n)=\begin{cases} 1, & \text{ if } n = 1 \\ T(n-1) +n(n-1), & \text{ if } n \geq 2 \end{cases} $$
0
votes
1answer
1k 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 ...
1
vote
1answer
33 views

Find the minimum cost of adding the elements of a set (greedy algorithm)

I'm VERY stuck with this problem: Given a set (with possible repeated elements), the cost of adding two elements $x, y$ is $x + y$. For example, the possible costs of the next set $\{1,2,5 \}$ are: ...
1
vote
1answer
14 views

can't quit understand one step of the recurrence time complexity calculation

I solved the question T(n) = T(sqrt(n)) + 1 but can't quit understand one step of the solution I don't understand the transition in (1). how did we conclude that T(m) = T(m/2) + 1 from the previous ...
1
vote
2answers
228 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
1answer
216 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
17k views

Solution to recurrence $T(n) = T(n/2) + n^2$

I am getting confused with the solution to this recurrence - $T(n) = T(n/2) + n^2$ Recursion tree - ...
0
votes
2answers
687 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
1answer
18 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 ...
0
votes
0answers
19 views

Recurrence relation of an algorithm

how can I know what are the recursive calls of this algorithm ? in line two there are 2 recursive calls and I don't know how to write this as T(n) for the Recurrence relation. Here is the algorithm :
0
votes
0answers
9 views

solving 𝑇(𝑛)=𝑇(𝑛/3)+𝑇(𝑛/6)+1 without Akra-bazzi method [duplicate]

I need to find $g(n)$ so that $𝑇(𝑛)=𝑇(𝑛/3)+𝑇(𝑛/6)+1 = \Theta(g(n))$. I know that the recursion tree height, $h$, is $\lg_6{n}\le h \le \lg_3{n}$ and that every level of the tree has at most $2^d$...
0
votes
1answer
56 views

How is equation 1 simplified to equation 2 as shown below

In CLRS (Intro to algorithms) on page 362, it says eqn(1) : can be simplified to this equation(2): I would like to know how this simplification was arrived at. It shouldn't necessarily be a formal ...
1
vote
0answers
41 views

Is there a term for the inverse of a fixed-point operator?

When working with recursion it is often useful to find the least or greatest fixed points of a morphism, often using a fixed-point combinator. When working with recursion schemes, the inverse ...
0
votes
1answer
590 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
55 views

Is well-founded recursion enough for practical total functional programming?

Total functional programming is a paradigm of non-Turing-complete programming languages where any program that type checks is proven to halt. Well-founded recursion is a recursive definition of a ...
0
votes
0answers
33 views

substitution method - proving karatsuba algorithm is not O(n)

I want to prove that $T(n) \neq O(n)$ for the Karatsuba algorithm, which has the following recurrence: $$ T(n) = \begin{cases} k_1, & \text{if $n$ = 1} \\ 3T(n/2) + k_2n, & \text{if $n \gt$ 1} ...
0
votes
0answers
29 views

Dynamic Programming, lru-cache, “minimum weight of a number”

I'm struggling with the following problem: The weight of a correct arithmetic expression, consisting only of the strings 1, x, +, is defined as the number of 1s appearing in the expression. Each ...
1
vote
1answer
39 views

Running time of a function $P$ calling itself via $P(P(n/2))$

int P(int n) { if (n==1) return 1; else return P(P(n/2)); } How will this function P(P(n/2)) be executed and what ...
0
votes
0answers
28 views

Why do online compilers/interpreters use different limits for the maximum recursion depth error?

When using two different online Python compilers/interpreters for executing a program (this one, and this one), I found that both sites showed the maximum recursion depth error at $n = 998$, whereas ...
2
votes
1answer
27 views

Code and time complexity of multiplication à la française

This references the multiplication algorithm in Chapter 1 of Algorithms by Dasgupta et al. I am trying to understand how the code for multiplication à la française works from the multiplication by ...
0
votes
0answers
20 views

I need good book about algorithms, which explains recursion, backtracking and depth first recursion for beginners [duplicate]

I'm learning programming, Python 3 in particular, and I have a good book "Beginning Python - From Novice to Professional" by Magnus Lie Hetland, but the book doesn't explain algorithms at ...
1
vote
2answers
40 views

Constant terms at each level of a recursion tree

In CLRS, exercise 4.4-5 the following question is asked: Use a recursion tree to determine a good asymptotic upper bound on the recurrence $$T(n) = T(n-1) + T(n/2) + n$$ In my recursion tree, the ...
0
votes
2answers
61 views

Prove by induction that a recurrence has solution $T(n)=\Theta(n^2 \log_{3}n)$

Prove by induction that $T(n)=\Theta(n^2 \log_{3}n)$ where $$T(n)= \begin{cases} 1 & \mbox{if } n=1,\\ 9T(\lceil n/3 \rceil)+n^2 & \mbox{otherwise.} \end{cases}$$ The base case for $n=1$ seems ...
1
vote
1answer
39 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 ...
0
votes
2answers
46 views

Solving $T(n)=3T\bigl(\bigl\lfloor \frac{n}{3}\bigr\rfloor\bigr) +2n\log n$ without the Master Theorem

I want to solve $$T(n)=3T\bigl(\bigl\lfloor \frac{n}{3}\bigr\rfloor\bigr) +2n\log n,$$ with base case $T(n) = 1$ if $n \leq 1$. I know that the solution is(with the help of the Master Theorem) $$\...
1
vote
1answer
31 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 ...
2
votes
1answer
81 views

Why, intuitively, does the Ackermann function require $\mu$-minimisation?

I have read proofs that the function is not primitive recursive and I (think) I understand them. Most I've seen show that the set of functions dominated by the Ackermann are exactly the primitive ...
0
votes
3answers
167 views

How many times in this pseudo-code is the function F called?

For this question, I thought function F called twice but it called three times. Are those three functions were called? F(N), F(K) and F(N-1)? How many times in this pseudo-code is the function F ...
1
vote
1answer
204 views

Finding Permutations with Exclusions

Recently, I was given a puzzle by a friend of mine, which has 6 pieces. Giddy to try it out, I took it apart without batting an eye to follow what I was removing or moving or sliding. I've been ...
2
votes
1answer
48 views

Is this an example of Tail Recursion

As I have read in this answer: What is tail recursion? tail recursion is a special case of recursion where the calling function does no more computation after making a recursive call. Here after the ...
1
vote
1answer
34 views

How to calculate the basic steps in Fibonacci sequences to get nFn and n^2

I am reading Algorithms by Sanjoy Dasgupta, Umesh Vazirani, Christos Papadimitriou and I am trying to understand how the number of steps $nF_n$ and $n^2$ were calculated. Here's the part of the book ...
1
vote
1answer
54 views

Using Subset Sum algorithm $O(n)$ times to find the subset

Subset Sum is a well-known dynamic programming problem, which states that given a succession of numbers and a number, the algorithm determines if exists a subset that its sum is equal to the given ...
3
votes
2answers
1k views

General method behind converting recursive inorder, preorder and postorder traversals of a binary tree to a non-recursive one?

I am reading both recursive and non-recursive using stack methods to implement inorder, preorder and postorder traversal of a binary tree at https://en.wikipedia.org/wiki/Tree_traversal#Depth-...
1
vote
1answer
31 views

How to prove $T(n) = 2T(n/2) + n/\log(n)$ can't be solved using the Master Theorem?

I have read (in this question) that this recursion can't be solved via Master Theorem. But I couldn't find exact and complete proof why the Master Theorem does not apply.
0
votes
0answers
16 views

It is possible proove the complexity of each query in a Segment Tree to O(log N) with recursion tree

Maybe the title is bad format but, I want to ask if is possible proof the Segment Tree complexity with the recursion tree. In other words I'm making a simple report on segment tree and I want to try ...
0
votes
0answers
29 views

Generalised letrec semantics for mutual recursion

I'm new to system types and I was wondering how mutual recursion is defined through generalized e::= ..|let rec x1=e1 ,...., xn=en in e .What has to be added in the "simple" let rec ...
1
vote
1answer
5k 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)$, with $F(0)=0, F(1)=1$ $f(n)=f(n-1)+f(n-2)$, with $f(0)=0, f(1)=1$ I don't know how to solve this. The $f(n)$ is basically just $F(...
4
votes
1answer
221 views

Struggling to understand the thought process required to come up with some recurrences for Dynamic Programming problems

I was doing a few dynamic programming problems and I am struggling to understand the thought process required to come up with recurrences. The first problem I solved was longest palindromic substring ...
0
votes
1answer
94 views

Solving the recursive equation $T(n)=T(k)+T(n-k-1)+O(n)$

The question is clear in the title. I am trying to solve this recursion as a part of showing that the worst case of quicksort algorithm occurs when $k=0$, but can't do it. I could do the following ...
0
votes
0answers
26 views

Back Substitution Method for solving recursive equation

Does back substitution method work for any recursive equation? If not is there any generalized form for recursive equation?

1
2 3 4 5
10