# Questions tagged [recursion]

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

561 questions
Filter by
Sorted by
Tagged with
1 vote
119 views

### Can the algorithm be optimized?

I am new to backtracking and recursion. I have seen numerous explanations on how on to find the minimum number of coins needed to make a particular amount. This involves a top down dynamic approach ...
466 views

### Facility location on a tree

Question: Given a tree representing a neighbourhood where each node is a house. Assign an antenna to each node such that the whole tree is covered. An antenna of strength 0 can only ...
1 vote
230 views

### How to solve recursion T(n)=T(n/2)+T(n/3)+n?

How to solve recursion $T(n)=T(n/2)+T(n/3)+n$? I do not really know how to approach this kind of recurrence.
57 views

### Marginal Probability of Generating a Tree

Fix some finite graph $G = (V, E)$, and some vertex $x$. Suppose I generate a random sub-tree of $G$ of size $N$, containing $x$, as follows: Let $T_0 = \{ x \}$. For $0 < n \leqslant N$ i. Let ...
1 vote
563 views

### Convert tree with recursive relationship to parent-child tree

Background: I have a .yaml file which holds around >3000 elements. The elements are related to each other through a recursive relationship. I want to create a tree view containing those items. A good ...
65 views

### I am unable to understand the logic behind the code (I've added exact queries as comments in the code)

Our local ninja Naruto is learning to make shadow-clones of himself and is facing a dilemma. He only has a limited amount of energy (e) to spare that he must entirely distribute among all of his ...
51 views

### Turing Recursive Definition vs General Perception

So what confuses me is that let's consider a function f. According to a definition from a text book it asserts that f is called recursive, if there is a Turing machine that computes it (for all input ...
1 vote
71 views

70 views

526 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 ...
105 views

### Iterative-substitution method yields different solution for T(n)=3T(n/8)+n than expected by using master theorem

I's like to guess the running time of recurrence $T(n)=3T(n/8)+n$ using iterative-substitution method. Using master theorem, I can verify the running time is $O(n).$ Using subtitution method however, ...
2k views

### Min-coin change problem with limited coins

I have been assigned the min-coin change problem for homework. I have to calculate the least number of coins needed to make change for a certain amount of cents in 2 scenarios: we have an infinite ...
1 vote
165 views

### Find the fixed point of a recursive functional?

A functional is a function which takes another function as a parameter. The fixed point of a function is an input such that F(x) = x Given an example functional, <...
49 views

### Recursive set for a string

Given the definition: ...
3k views

### Explanation of O(n2^n) time complexity for powerset generation

I'm working on a problem to generate all powersets of a given set. The algorithm itself is relatively straightforward: ...
517 views

### Cover interval with minimum sum intervals - DP recursion depth problem

READ ME FIRST: I have just found the official solutions online (have been looking for them for a while, but after posting this I quickly found it), and I'm currently trying to understand it. As I can ...
54 views

### Recurrence Relations

I am starting to learn recurrence relations in class and I am having issue with this example: T(N) = 2N - 1 + T(N-1) I am bit confused as to get the base case. I'm sorry if this seems elementary, ...
68 views

### How to show that a partial function is recursive?

I try to prove that this function is recursive: $$f(x_1,x_2)= \begin{cases} 2x_1-x_2 & \text{if x_1 \geqslant \sqrt{x_2}} \newline \bot & \text{otherwise} \end{cases}$$ I think that I need ...
53 views

### Converting a function with single parameter to a function with multiple parameters

I have been solving some algorithm questions recently and a pattern I have observed in some problems is as follows: Given a string or a list, do an aggregation operation on each of its elements. Here ...
1 vote
204 views

664 views

### Pseudo code of recursive method of printing all permutations of $n$ given integers

I really don't understand this pseudo code. The function prints all permutations of $n$ given integers, assuming that all numbers are different. Is there a way to explain this code more easily as I ...
448 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 ...
142 views

1 vote
45 views

### Hanoi towers recursive expression for EVERY algorithm

What the recursive algorithm for moving $n$ disks says, is: If $n > 1$, move $n-1$ discs from A to B. Move the $n$th disk from A to C. If $n > 1$, move $n-1$ discs from B to C. Let $T_n$ be ...
26 views

### Recursive Call Inside Argument List (C++) [closed]

So, my professor asked me to implement recursion in different ways to compute $a^n$ (a and n being integers) and rank them according to their space efficiency. Now, here is one of the methods I came ...
261 views

### Can every problem that uses recursion be solved using iteration? [duplicate]

We all know iterations and recursions are a powerful thing in programming. But this doubt always troubles me whenever I write an iteration or recursion. Can every recursive problem solved using ...
99 views

### How to find the substitutions that convert the starting sequence into the final sequence? CCC19J5

Here is Canadian Computing Competition 2019 Junior problem 5 on dmoj.ca. You can also see the original problem at cemc.uwaterloo.ca as well. A substitution rule describes how to take a sequence of ...
1 vote
51 views

### Removing recursion from a function with multiple params

I am given the following function as a brain teaser: ...