The 2024 Developer Survey results are live! See the results

# Questions tagged [recursion]

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

601 questions
Filter by
Sorted by
Tagged with
20 views

### How is this factorial Y combinator evaluating in scheme?

I can't understand how this is evaluating in scheme. ((lambda (n) ((lambda (fact) (fact fact n)) (lambda (ft k) (if (= k 1) 1 (* k (ft ft (- k 1))))))) 5) ...
1 vote
101 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 ...
2k 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 ...
58 views

### Binary search calculating complexity big o

I'm studying recursion and a i have a doubt about the running time complexity of the binary search. I didnt understand this passage in my book : ...
78 views

### Clarification of divide-and-conquer recurrence explanation in 'Introduction to Algorithms' (CLRS)

The following excerpt is from page 39 of the 4th edition of 'Introduction to Algorithms' (emphasis added): 2.3.2 Analyzing divide-and-conquer algorithms [...] A recurrence for the running time of a ...
1 vote
141 views

### Diffucuty in understanding code after a recursive call

This is an example algorithm of a recursive insertion sort I'm trying to understand. I've have tried understanding this with the help of print statements (which I've commented). ...
126 views

### Expected runtime of recursive algorithm with optional part

I have a randomized recursive algorithm which expected running time is $T(n)$. In particular, the recursion looks like this: $$T(n) \leq \mathcal cn + R ,$$ where $R$ is a recursive term that depends ...
40 views

### What is the complexity of this tree recursive integer replacement algorithm?

LeetCode has an Integer Replacement problem defined as follows: Given a positive integer $n$, you can apply one of the following operations: If $n$ is even, replace $n$ with $n / 2$. If $n$ is odd, ...
1 vote
124 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 ...
82 views

### Is my mathematical representation of search in binary search tree correct?

You are given the root of a binary search tree (BST) and an integer val. Find the node in the BST that the node's value equals <...
1 vote
106 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 ...
15 views

### Incorrect integration results in Adaptive Quadrature routine with periodic functions

I have just finished writing an iterative Adaptive Quadrature routine in C++ that uses the trapezium rule as a base. I plan on writing one using Simpson's rule next. The routine is quite simple. The ...
48 views

### Big O notation of T(n) = T(n/2) + O(log n) using master theorem?

I am aware that the algorithm has 1 recursive call of size n/2 and the non-recursive part takes O(log n) time. Master theorem formula is T(n) = aT(n/b) + O(n^d). In this case a = 1, b = 2, but I am ...
1 vote
43 views

### Algorithms by Dasgupta-Papadimitriou-Vazirani Prologue confusion

We will see in Chapter 1 that the addition of two n-bit numbers takes time roughly proportional to n; this is not too hard to understand if you think back to the gradeschool procedure for addition, ...
135 views

...
80 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: ...
485 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 ...
609 views

### Can the minimisation operation be seen from a programming language perspective?

If $f$ is a total function $\mathbb N^k\to\mathbb N$, and $g$ is a total function $\mathbb N^{k+2}\to\mathbb N$, then we say that $h:\mathbb N^{k+1}\to\mathbb N$ is definable by primitive recursion ...
115 views

### Let F be a function defined for all nonnegative integers by the following recursive definition

Let F be a function defined for all nonnegative integers by the following recursive definition. F(0) = 0, F(1)= 1 F(n + 2) = 2F(n) + F(n +1), n>0 Compute the first six values of F; that is, write ...
45 views

### Why is incompleteness important?

Or take Russel's paradox. Either the barber does or doesn't shave himself -- that's all there is. How you describe it is an artificial construct. Godel's theorem is like dividing by zero and declaring ...
71 views

### What are the fixed-points of the Y combinator?

Since the Y combinator itself is a function (albeit a higher-order one), I was wondering what the fixed-points of Y itself are.
1k views

### Does the Y combinator contradict the Curry-Howard correspondence?

The Y combinator has the type $(a \rightarrow a) \rightarrow a$. By the Curry-Howard Correspondence, because the type $(a \rightarrow a) \rightarrow a$ is inhabited, it must correspond to a true ...
141 views

### Number of ways in which a '?' in a given string can be replaced with numbers from [0-9]

I came across this interesting problem in a test and I couldn't complete it. There is a string given s which can consists of numbers between 0-9 and '?'. In place of '?' we can insert any of the ...
1 vote
44 views

### Bottom-up well-balanced mergesort

If you implement mergesort top-down you can always split the input of length $n$ into one of length $\lfloor n / 2\rfloor$ and one of length $\lceil n / 2 \rceil$. This ensures that all merges are ...
1 vote
67 views

### How to Solve the Recurrence Relation $T(n) = 8T\left(\frac{n - \sqrt{n}}{4}\right) + n^2$ in terms of $\Theta$?

The provided recurrence relation is as follows: $$T(n) = 8T\left(\frac{n - \sqrt{n}}{4}\right) + n^2$$ The goal is to express the solution in terms of the asymptotic notation $\Theta$. Unfortunately,...
80 views

### How to solve the recurrence $T(n) = 4T\left(\frac{n}{2}\right) + \frac{n}{\lg n}$ in terms of $\Theta$?

I'm attempting to solve the recurrence relation: $$T(n) = 4T\left(\frac{n}{2}\right) + \frac{n}{\lg n}$$ in terms of its asymptotic behavior ($\Theta$), specifically using the first case of the ...
1 vote
128 views

### Recursive DFS Problem

I have been struggling with this contest problem for awhile now which is found at this link: https://people.eecs.berkeley.edu/~hilfingr/programming-contest/pacific-northwest/2009/b.pdf Short summary ...
113 views

### Making use of one function to recursively find n/3 of another

Given an algorithm M that computes the median of an array A in O(n) time, describe an O(n) algorithm to repeatedly call M in order to find the element of rank n/3 in A. This is a problem I am tasked ...
179 views

...
1 vote
106 views

### Complexity of recursive function using Master theorem

this code aims to determine whether there exists a contiguous subarray starting from index 0 in the given array A whose elements sum up to the target value S. can we apply Master theorem to find out ...
143 views

### How to Remove Left Recursion from this Grammar?

How to remove left recursion in the following Grammar: S→Bb/a B→Bc/Sd/e Im new to this, below is the way I'm doing it: ...
1 vote
89 views

1 vote
367 views

### Understanding the Recursive Algorithm for Integer Division

In my reference, Page 26, Algorithms by Sanjoy Dasgupta, Christos H. Papadimitriou, and Umesh V. Vazirani, a division algorithm is give as, \begin{align} &\text{function divide}(x, y)\\\\ &\...
74k views

### What is most efficient for GCD?

I know that Euclid’s algorithm is the best algorithm for getting the GCD (great common divisor) of a list of positive integers. But in practice you can code this algorithm in various ways. (In my case,...