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
1answer
548 views

How solve this recurrence: T(n) = 2t(n-1) - t(n-2) +5n +7 [duplicate]

I am trying to solve the recurrence: T(n) = 2t(n-1) - t(n-2) +5n +7 but without success. And from here I don't know how to continue?
0
votes
0answers
195 views

Iteration vs. recursion: what do these terms really mean?

Most of us know the typical answer to this question: if a function calls itself, it's recursion, if it's a loop, it's iteration. We also know that recursion can be simulated using iteration (by ...
0
votes
0answers
46 views

time complexity question

I am reading a free algorithms textbook http://www.cse.iitd.ernet.in/~Naveen/courses/CSL630/all.pdf and on page 13 i am stuck on an example they give. "At this time, the fastest computer in the ...
0
votes
0answers
16 views

How to solve this recursive relation T(n)= 2T(n/2) + 3T(n/5) +n [duplicate]

I don't think I'm able to solve this using the master's theorem, and solving separately doesn't seem to make sense. How does one go about solving this recursive relation? T(n)= 2T(n/2) + 3T(n/5) +n
0
votes
0answers
286 views

How to calculate the depth of the call stack for the average case of quicksort

In the best case of quicksort the depth of the call stack is measured by $\lceil\log_2 n\rceil$ if I am not wrong. What would be the formula for calculating the depth of the call stack in case of an ...
2
votes
2answers
897 views

Why are unbalanced partitions worse than balanced partitions in Quicksort?

I am unable to understand why unbalanced partitions in quicksort is actually worse than balanced partitions. After reading this document it shows that worse case partitions are of the type $(0,(n-1)),...
1
vote
2answers
240 views

Confusion over the complexity of parameter passing in merge sort

I'm working through CLRS on problem 4-2, which says the following: Throughout this book, we assume that parameter passing during procedure calls takes constant time, even if an $N$-element array is ...
1
vote
0answers
28 views

Creating a self-affine fractal on L-systems

Hi I would like to create a self-affine fractal on L-Systems. The axiom I have created is FF-GGG-GG-GGG++GGG+GG-GGG+GG+GGG+FF++ffGG+GGG+FF+GGG which creates the image below At each stage I would like ...
4
votes
1answer
2k views

Recursion Davis' Staircase understanding

I'm going through a hackerrank challenge on recursion https://www.hackerrank.com/challenges/ctci-recursive-staircase and I'm having difficulty understanding how the solution below solves the problem. ...
2
votes
1answer
184 views

what are Structural recursion, primitive recursion, recursion combinator and recursion principles?

Recently, I encountered terminologies such as primitive recursion and recursion combinator. One of the sources is here link I googled and read some, but missing the points of them. I know that ...
2
votes
0answers
197 views

Recursive definitions, How it is done?

I read that recursive definitions, refer to the definition of a function in that function body, cannot be done in $\lambda$-calculus, but recursion can be achieved by using $Y$ combinator. As I know, ...
2
votes
2answers
85 views

Find X contiguous segments in a range of integers

I've been struggling with the following problem: how do I find all possible sub-ranges in a range of integers where each segment is at least length 1, and I specify the total number of segments? A ...
2
votes
1answer
200 views

Rod Cutting without using dynamic approach

Question I want to Implement Rod cutting Algorithm without Dynamic Programming Approach. Let me Describe the problem statement. Given a rod of length $n$ inches and a table of prices $p_{i}$ for $...
1
vote
1answer
713 views

Space and time complexity of balanced parentheses enumeration algorithm

Consider the following recursive algorithm for printing all balanced strings with $n$ left and right parentheses. It is called with prefix = $\epsilon$ (the empty string): A(prefix): If prefix ...
2
votes
1answer
1k views

How can I convert a for loop to a recursive function?

My loop is pretty simple. The function takes in two parameters, a and b; both are integers where a<=b. The function will then create a list of numbers from a to b. This is what I created: ...
1
vote
0answers
239 views

Why is A* considered as a recursive search algorithm? [closed]

I'm currently studying informed search algorithms. I've found a paper telling that A* is a recursive algorithm but I can't see where's the recursion part of this algorithm. Why is A* considered as ...
0
votes
1answer
182 views

$f:\Bbb N\dashrightarrow\Bbb N$ is partial recursive $\Leftrightarrow$ its graph is a recursively enumerable? [closed]

I have known that: A function $\Bbb N → \Bbb N$ is recursive if and only if its graph is a recursive subset of $\Bbb N^2$. Now I am considering about the partial functions. Is it the fact that: ...
4
votes
1answer
197 views

Why is it that if we assume the Church-Turing thesis to be true, then human language must be recursive if the brain is finite?

I was reading "Why Only Us" by Chomsky and Berwick, and it said: If one subscribes to the Church-Turing thesis along with the assumption that the brain is finite, then there is no way out: we ...
1
vote
1answer
66 views

Turning generative recursion results (leaves of a tree) into connected components (where each neighbour differs by one element)

I'm generating valid timetables for my uni with a simple generative recursion algorithm like this (disregarding handling of course-specific labs and tutorials) ...
0
votes
0answers
74 views

Finding islands recursively in a matrix [duplicate]

I had this question in an interview recently. I was unable to answer this question and would really like to start a discussion on how to approach this problem and get the most efficient solution. You ...
3
votes
2answers
718 views

How to solve the recurrence: T(n) = n*T(n-1) + n?

In a an exercise I'm required to analyze the runtime of recursive function: ...
8
votes
2answers
985 views
1
vote
0answers
339 views

Why do we count the ceils and floors in recursive functions?

When we solve the recursive functions using substitution method, the impact of ceil and floor functions is trivial when the size of the input is large enough. For example the answer of $$ T(n) = T(\...
0
votes
0answers
16 views

The 0-1 Knapsack problem - Regression equation [duplicate]

I'm trying to figure out the regression equation for the 0-1 Knapsack problem recursive algorithm: ...
2
votes
1answer
436 views

A better upper bound to a recursive function

it's my first answer here. I do have an algorithm to calculate the factorial of a given number $n$ recursively, but without using any multiplication like the usual one, only sums are available. I'...
-1
votes
1answer
2k views

How does recursion work in void method java [closed]

...
2
votes
0answers
141 views

Maximum Move in a maze

Given a N * N maze, and string of N,E,W,S denoting positions to move to. I need to determine how many moves are possible in sequence out of a string (containing these 4 letters only) from each cell as ...
0
votes
0answers
43 views

Recursive algorithm. Complexity [duplicate]

I need your help with time complexity. I have this recursive function: $$ F(n) = \left\{ \begin{array}{l l} F(n-2) + 10 F\big(\frac{n}{6}\big)^2 + 6 F\big(\frac{n}{7}\big) + \frac{n^4}{5} & \...
0
votes
0answers
239 views

Stack depth and initial call

I've not been able to find a precise definition of "stack depth" anywhere and have a rather simple question. When dealing with trees I'm used to the maximum depth (or height) of the tree being the ...
0
votes
0answers
153 views

Finding the shortest tour of a Pyramidal traveling salesman problem

We have a directed graph $G=(V,A)$ with $V=\{1,2,...,n\}$ where for each $(i,j)$ the distance $l(i,j)\in A$ is known. We want to find a pyramidal tour that has minimal length and that includes all ...
2
votes
2answers
183 views

Converting $\beta$-bit integer to a decimal representation in $\Theta(M(\beta) \log \beta)$

The following problem is from CLRS (31.1-13, Page 933, 3rd edition): Give an efficient algorithm to convert a given $\beta$-bit (binary) integer to a decimal representation. Argue that if ...
0
votes
0answers
41 views

what will be the time complexity of below recursive algorithm [duplicate]

Please help me find the time-complexity of below recursive algo. I have guessed for first two return statements.Please correct me if I am wrong. But I can't find time-complexity of third return ...
2
votes
1answer
90 views

Decimal to Binary converter with a flaw

Hi I wrote the following recursive decimal to binary function while studying for Andela. ...
1
vote
1answer
58 views

Can such an algorithm be written using recursion

I'm writing an algorithm that, given a limit N, and given a list of elements of value V, find all the possible combinations so ...
1
vote
0answers
470 views

What is a “pure recursive approach” [closed]

I am working on a homework assignment to create a function and it says to use a "pure recursive approach". I am trying to piece together what is actually meant by this. I am aware a recursive function ...
1
vote
2answers
1k views

Recursive algorithm - a^(2^n) [closed]

The a^n was pretty easy: function powN(a, n) { if(n == 0) return 1; return a * powN(a, n - 1); }; But somehow I got ...
2
votes
2answers
5k views

Time complexity of recursive power code

While I was learning about time complexity of recursive functions, I came across this code to calculate $x^n$: ...
1
vote
1answer
151 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 ...
0
votes
1answer
128 views

Formulating a recursion using mathematical notation [closed]

So I'm assigned a task that involves formulating a quite complex recursion of several variables using 'mathematical notation'. The assignment is quite sparse when it comes to additional information, ...
3
votes
1answer
382 views

Counting Total Number of Non-Equivalent Configurations in a 2-D Grid

This is a challenging question I've been trying (unsuccessfully) to solve via programming, math or both. Suppose you're given a 2D grid, whose width and height, $w$ and $h$, can each range from $1$ ...
0
votes
1answer
34 views

Evaluating tree data iteratively

Community, I'm working on a project lifting assembler code to a AbstractSyntaxTree-like structures like these: In order to be able to evaluate the final value of a tree given only leafes with ...
5
votes
1answer
506 views

Confused between turing-completeness and universal approximation - are they related?

I am trying to de-knot a point of confusion in my mind regarding "turing-completeness" and the "universal approximation theorem". The context here is deep neural nets: So, consider two types of ...
0
votes
0answers
39 views

Finding time complexity of an algorithm [duplicate]

I am to find the time complexity of my algorithm and I found one method here. However I am really not sure about it correctness thus I would like to check it. There is my algorithm (N is a set (len(N) ...
-2
votes
1answer
97 views

How do you convert this iterative code to recursive?

How do you convert the following algorithm from the iterative paradigm to the recursive paradigm? Input: array $A[1],\ldots,A[n]$ Output: last index $i$ such that $A[i] = i$, or $-1$ if none ...
1
vote
1answer
111 views

Complete $\mu$-recursive function that is not primitive recursive

Could you find an example of a complete $\mu$-recursive function that is not a primitive function?
2
votes
2answers
105 views

Help with recursive algorithm analysis

Given this algorithm: int foo(int num) { if (num == 0){ return 0; } else { return 1 + foo(num/10); } } Me and my friend are debating ...
4
votes
2answers
240 views

What is a 'subrecursive algorithm'?

I am reading Exploring Robotic Minds by Prof. Jun Tani, and came across the term subrecursive. Original context: Another possibility might be to assume ...
44
votes
5answers
10k views

Iteration can replace Recursion?

I've been seeing all over stack Overflow, e.g here, here, here, here, here and some others I don't care to mention, that "any program that uses recursion can be converted to a program using only ...
3
votes
3answers
164 views

Solving recurrence $T_k(n) = T_k\left(\left \lfloor \frac{n}{2} \right \rfloor\right) + T_k\left(\left \lceil \frac{n}{2} \right \rceil\right)$

I am currently solving a problem that I have reduced to computing the following function efficiently. $$T_k(n) = T_k\left(\left \lfloor \frac{n}{2} \right \rfloor\right) + T_k\left(\left \lceil \...
1
vote
1answer
588 views

Running time of greedy scheduling algorithm

Here is an algorithm to output a subset of activities S such that no activities in S overlap and profit(S) is maximum. Define $p[i]$ to be the largest index $j$ such that $a_j$ does not overlap $a_i$....