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
1 vote
2 answers
52 views

Why is a recurrence of $2N_{h-2}$ equal to $2^{h/2}$?

I was watching video 7. Binary Trees, Part 2: AVL, where professor Erik Demaine stated that $$2N_{h-2} = 2^{h/2\text{ (or maybe with floor or something... maybe it's ceiling)}}$$ where $N$ stands for ...
user avatar
1 vote
1 answer
40 views

A recursive relation for the number of well formed nested parentheses of length $n$ and depth $\leq d$

Consider a function $C(n, d)$ which counts the number of well formed, i.e, balanced, parenthetical 'words' of length $n$ and maximal nested depth $\leq d$. That is, $(())$ has $n = 4, d = 2$. $()((())(...
user avatar
1 vote
1 answer
87 views

Am I drawing the recursion trees correctly?

I guess I've already figured out what is a recursion tree and how to construct one. Inspired by Figure 2.5 of "Introduction to Algorithms, 3rd Edition by CLRS", I drew some recursion trees ...
user avatar
  • 576
0 votes
1 answer
22 views

Recursive function - proof by induction

Let $\Sigma$ denote an alphabet and $[ \Sigma ]$ set of lists. I've encountered the following function: $f([])=[]$ (empty list) $f([x])=[x]$, for $x \in \Sigma$ $f(x:L)=f(L)$, for $x \in \Sigma$ and $...
user avatar
  • 1
2 votes
1 answer
55 views

Trying to understand the basic about recurrence trees

I have little background on recurrence trees, and I am working on the following exercise: Exercise. Take $T(n) = 2T(n/2) + 3\log(n)$. Draw the recurrence trees for $n=2$ and $n=4$. What can we ...
user avatar
  • 187
1 vote
3 answers
53 views

Recursive algorithm for adding numbers from 1 to n with O(1) time complexity

So I have a recursive algorithm which sums up the numbers from 1 to n plus one (hence the return 1): ...
user avatar
  • 13
0 votes
0 answers
26 views

Prove that a predicate is not computable

Prove that the following predicate is not computable: $P_e(n) = \begin{cases} 1 & \textrm{if } \phi_n(n) = e \\ 0 & \textrm{otherwise} \end{cases}$ Could someone explain how to approach ...
user avatar
1 vote
0 answers
76 views

Recursive algorithm running time?

I would like your opinion on how to detect the T(n) (Running Time) for the following recursive algorithm. Charm is an algorithm for discovering frequent closed itemsets in a transaction database. A ...
user avatar
0 votes
1 answer
17 views

Termination condition for max of array using divide and conuqer approach

I want termination proof of divide and conquer approach to find max of array,I want equational proof in form of lemma.Below is my attempt.I have got accepted everything in dafny ,it is only pointing ...
user avatar
-3 votes
1 answer
37 views

Recursion problem T(n)=3T(n/3)+3n

I just need help solving this problem. I know I'm supposed to be using the Master's Theorem but I don't know where to start
user avatar
1 vote
1 answer
49 views

Time complexity of merging two lists while preserving order

I have two lists l1 and l2 of possibly unequal sizes (say, m and ...
user avatar
  • 11
0 votes
0 answers
20 views

What is the standard definition of recursive automata (or state machines)?

I found this paper: https://courses.engr.illinois.edu/cs373/fa2009/recaut.pdf But it looks like recursion is done along an edge. I would have thought you have state machines nested inside nodes. ...
user avatar
0 votes
0 answers
27 views

Why are we allowed to ignore constant factors of $g(x)$ in recurrence while they are important in solving the recurrence?

I'm trying to learn about asymptotic notations and recurrences and I use MIT 6.042 Mathematics for Computer Science as my resource. and I have some questions about the Professor's talks. He said: ...
user avatar
  • 1
3 votes
1 answer
147 views

Skyline problem with triangular buildings

This question is based off of the usual Skyline problem, which is discussed in GeeksForGeeks and also several other websites. The following are two variations from the usual Skyline problem: Report ...
user avatar
1 vote
1 answer
61 views

Tower of Hanoi variation - Split into two towers of odd and even disks

Suppose we have three rods A, B and C, and rod A ...
user avatar
  • 119
0 votes
0 answers
23 views

recursive function without intermediate variables

The question was to convert this recursive code with intermediate variables to a functional program code without any intermediate variables. ...
user avatar
0 votes
0 answers
13 views

Simple examples of Recursive Enumerable Functions

My understanding of Recursively Enumerable Functions is that they're recursive functions, but for some values of the arguments you put into the function they will stop and give an answer, and for ...
user avatar
7 votes
2 answers
3k views

Is the Berkeley tutorial on Fibonacci trees using wrong figures?

I'm confused about the figures in a Berkeley tutorial on Fibonacci trees, which depicts fibtree(2) as and fibtree(3) as I thought fibtree(3) looks like the following (the figure is adapted from ...
user avatar
  • 576
0 votes
1 answer
47 views

Implementing a correct `let rec in` interpreter in Haskell with `eval` and `sub` semantics

I'm implementing the toy fb-lang from the principles of programming language book. It's a small interpreted language that uses eval(uate) expression function and <...
user avatar
  • 109
0 votes
0 answers
20 views

Unusual approach to tabulation algorithm

Consider simple tabulation algorithm firstly for Fibonacci numbers. We will use the dictionary as a cache (and Python as example PL): ...
user avatar
  • 101
13 votes
4 answers
3k views

Why is tail recursion better than regular recursion?

There is the axiom you should always prefer tail-recursion over regular recursion whenever possible. (I'm not considering tabulation as an alternative in this question). I understand the idea by why ...
user avatar
0 votes
0 answers
86 views

Space complexity for divide-and-conquer

Here's a simple question but I'm not sure there is a simple answer. This came up in an undergraduate algorithms class. Consider the following divide-and-conquer algorithm $A$ (here, $x_1, \ldots, x_n$ ...
user avatar
  • 101
0 votes
0 answers
26 views

Number of recursion of a recursive algorithm for input size $n/2$

There is a problem whose input size is $n$. The problem is solved in two steps. In the first step $n/2$ of inputs are eliminated in $O(n)$ and then in the second step, four different recursive ...
user avatar
  • 1,357
1 vote
1 answer
26 views

Solve recurrence where the base case's time complexity is a function of the original input size

I'm trying to analyse the time complexity of the following algorithm for generating the power set: ...
user avatar
  • 123
0 votes
1 answer
42 views

How to count the leaves of a tree without a outside function counter?

I got bombed in a interview because I was asked to write an algorithm which would count the leaves of a tree, I did this: ...
user avatar
-1 votes
1 answer
65 views

Finding the number of ways to reach a particular position in a grid from a starting position (given some cells which are blocked)

I came across this question in a job interview and I couldn't solve it. In a n*m matrix some cells are blocked.The robot can only move in direction of (x-1,y+2) or <...
user avatar
-1 votes
1 answer
433 views

Dynamic programming to find number of ways to divide string into primes

I am studying for final algorithms exam and saw this question: Given a string of length n consisting of digits [0-9], count the number of ways the given string can be split into prime numbers >= 2....
user avatar
0 votes
1 answer
37 views

How can we get upper bound in terms of Big Oh notation using Master theorem?

The recursion is: T(n) = 5T(n/2) + O(n) I solved for the time complexity using Master theorem and found Θ(n^2). but, the question has asked to find the upper bound ...
user avatar
0 votes
1 answer
52 views

How does primitive recursion handle mutual recursion?

My intuition is that you can't call a function that has not yet been defined, although I have yet to find a source confirming this. Is this true? Thanks, friends :)
user avatar
  • 23
0 votes
0 answers
35 views

Solving $T(n) = T(0.01n) + T(0.99n) + cn$ [duplicate]

How to solve the below relation? $$ T(n) = T(0.01n) + T(0.99n) + cn $$ This will not be a balanced tree. For $k$ levels I have something like $\bigl(\frac{1}{100} + \frac{99}{100}\bigr)^k \cdot cn$. I ...
user avatar
0 votes
1 answer
24 views

Recursive Bijections Between Countably Infinite Sets

The textbook I am currently studying (Introduction to Kolmogorov Complexity and Its Applications by Li and Vitanyi) uses the term 'recursive bijection'. In this context I believe that recursive refers ...
user avatar
0 votes
1 answer
133 views

Is top-down dynamic programming always recursive?

I think top-down dynamic programming is mostly recursive (at least when we use memoization). For instance, solving the rod-cutting problem by this algorithm: ...
user avatar
  • 377
1 vote
1 answer
69 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 ...
user avatar
  • 21
2 votes
1 answer
62 views

Are recursion and a stack equivalent in terms of inplementing DFS?

It is well known that DFS can be implemented either with recursion or a stack, and that both approaches are equivalent, but how far can we take that statement? Consider the following LeetCode problem: ...
user avatar
  • 1,071
0 votes
0 answers
54 views

is there a theory consider on infinitely many recursion?

of course there is a theory that how many recursive calling the same system to solve problems, this theory is "recursion theory", If i know correctly. and recursion theory is computability ...
user avatar
1 vote
1 answer
105 views

How to convert any recursive solution to a Dynamic programming table? Is there any tricks/tips to follow?

I've been able to form a recurrence relation with memoization in a recursive approach for most problems but the online coding rounds exceed the time limit or stack overflow occurs in all these ...
user avatar
0 votes
1 answer
119 views

Recursive Prefix-Sums K times

I have been wondering about the following question for quite some time: You are given an array $x$. Define f(x) as the prefix sums of this array. For example, f([1,0,1]) = [1,1,2] and f(f([1,0,1])) = [...
user avatar
  • 186
0 votes
1 answer
88 views

Tic-Tac-Toe in PSPACE

Why is a game like Tic-Tac-Toe in PSPACE? For example for a nxn grid you have nxn! possible game tree paths (duplicates and illegal moves aside), then don't you need (n^2)! memory slots?
user avatar
2 votes
0 answers
48 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.
user avatar
  • 121
0 votes
1 answer
93 views

Multiplying two integers by dividing each into 3 parts

Integer Multiplication: $x$ and $y$ are two n-bit integers, where $n=3^k$ for some $k>0$. We break $x$ into three parts $a$, $b$, $c$, each with $n/3$ bits; and $y$ into three parts $d$, $e$, $f$, ...
user avatar
0 votes
1 answer
72 views

Question on Erickson 'momselect' algorithm

In the Erickson Algorithms textbook (file:///C:/Users/G068078/OneDrive%20-%20Kaiser%20Permanente/Algorithms_Technique_and_Theory_CS_388G/Undergraduate_CS331/Algorithms-JeffE.pdf) it has pseudocode for ...
user avatar
1 vote
0 answers
89 views

Recursion analysis using Master Theorem

I have the following algorithm: ...
user avatar
  • 131
2 votes
1 answer
46 views

Calculate the number of "count inversions" of sub arrays

Recently, I encountered the following problem: Given an array $A$ of length $n$ $(0\le n\le 2^{17})$. Let $f(l, r, x)$ denotes the number of occurrences of $x$ in the subarray $a[l\ldots r]$. Find ...
user avatar
0 votes
0 answers
88 views

Total work done at a recursion tree level

In the proof of Master theorem in Dasgupta's Algorithms the author says that the total work done at a recursion tree level is $$a^k \times O\left(\frac{n}{b^k}\right)^d$$ where $a$ is the branching ...
user avatar
  • 123
-3 votes
2 answers
43 views

Solve $\sum_{i=0}^{\log_3 n-1}i\times 3^i$

I want to find the answer for $$\sum_{i=0}^{\log_3 n-1}i\times 3^i$$ Can you please explain? I this a geometric series?
user avatar
1 vote
0 answers
12 views

Heuristics to transform a recursively enumerable set into a diophantine set

The class of recursively enumerable sets is equal to the class of Diophantine sets. Given a recursive function, is there a way to produce a diophantine equation such that the trace of calls to the ...
user avatar
  • 2,196
0 votes
1 answer
52 views

Are the definitions of loop in CS and in programming (standard/common) identical?

Are the definitions of loop in CS and in programming (standard/common) identical? If not, what is the main difference / what are the main differences?
user avatar
1 vote
2 answers
252 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? ...
user avatar
0 votes
0 answers
32 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="...
user avatar
  • 1
1 vote
1 answer
40 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 ...
user avatar
  • 71

1
2 3 4 5
11