The Stack Overflow podcast is back! Listen to an interview with our new CEO.

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
0answers
195 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
163 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
186 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
68 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
609 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
940 views
1
vote
0answers
302 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
394 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
1k views

How does recursion work in void method java [closed]

...
2
votes
0answers
137 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
162 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
151 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
173 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
427 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
142 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
126 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
357 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
458 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
94 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
104 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
102 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
231 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 ...
40
votes
5answers
9k 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
158 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
582 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$....
1
vote
2answers
6k views

Converting recursive algorithm to DP

As a follow-up to this question , I've found a recursive algorithm that solves the given problem, but it runs too slow to pass all given tests. ...
2
votes
1answer
434 views

Computing the minimal flexible distance of two vectors using dynamic programming

I can't figure out a recurrence equation for a dynamic programming assignment. Formally, we aim to minimize the total sum of distances between matched points with the following constraints: Every ...
0
votes
0answers
61 views

Time complexity of 1-d clustering recursive algorithm

I have the following code: ...
4
votes
2answers
417 views

Number of different binary search trees storing n distinct keys?

How many different binary search trees are possible that store the values 1,2,...,n ? So far I found a recursive formula for the number (by case distinction what's at the root): $ T(n) = 2T(n-1) + \...
0
votes
0answers
31 views

Given the following code, array A and 2 indexes, find out by using substitution technique the $\Theta$

While setting left=0, right=n-1 and A an array of n numbers, find out the running time complexity in terms of $\Theta$. Firstly find out the recurrence and then evaluate it by using the substitution ...
13
votes
1answer
2k views

Is this a generic way to convert any recursive procedure to tail-recursion?

It seems that I've found a generic way to convert any recursive procedure to tail-recursion: Define a helper sub-procedure with an extra "result" parameter. Apply what would be applied to the ...
2
votes
1answer
2k views

What is the time complexity of binary sum (recursion) [duplicate]

Currently, I'm reading Data Structures and Algorithms in Java, 6 edition by Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser link, particularly a chapter about recursions. There is an ...
1
vote
1answer
872 views

What is a recursion for Huffman encoding?

If I had to write the Huffman encoding as a recursion in terms of the cost $C_{ij}$, given weights/frequencies $W = [w_1,\ldots,w_n]$, how would I do it? (where this is creating a minimum cost tree, $...
2
votes
1answer
885 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-...
0
votes
1answer
522 views

What is the time complexity (upper bound) for this simple recursive function? [duplicate]

So I have function that I have written to return the maximum value between index i and index x of a given array using recursion as follows: ...
3
votes
0answers
46 views

Termination of deterministic term rewriting

Consider a simple language: $$t ::= plus ~ t ~ t ~ | ~ gen ~ t ~ | ~ except ~ N ~ t ~ | ~ N$$ with N constructors plus, gen and except, N being the natural numbers, and $G = \{t_n\}$ a finite, ...
1
vote
1answer
211 views

Why is this problem listed as “Dynamic Programming”

I found a problem in the dynamic programming section of hackerrank but its not clear why dynamic programming should be used to solve it. The problem is as follows: Nikita just came up with a new ...
0
votes
1answer
429 views

Algorithm to build a “hand” calculation for riichi mahjong game

I would like to discuss an algorithm to build a "hand" calculation for riichi mahjong game. I will simplify terms to focus on the algorithm and not on the game specific terms. Let's imagine that we ...
0
votes
1answer
196 views

Solution to the recurrence T(n) = 2T(n − 3) [duplicate]

We were asked the following question in our exam: Solve or bound the recurrence T(n) = 2T(n − 3) for n>3 provided ...
4
votes
1answer
9k views

Can Breadth-First Search be Implemented Recursively without Data Structures?

I'm in a data structures course, but our current unit discusses recursion and not data structures, and I need to implement breadth-first recursion for the purpose of finding the shortest path through ...