The tag has no usage guidance.

learn more… | top users | synonyms

1
vote
1answer
158 views

Why do I need to use recursion on the classic employee manager database relationship?

Take the data from the Oracle scott database. I have modified it to have multiple levels of management from the original, select * from scott.emp order by mgr desc; empno ename job ...
-2
votes
0answers
22 views

NullPointerException in clojure recursive function [migrated]

I'm learning Clojure and try to loop on a list using a recursive function. I manage to go all the way down the nested calls of the recursion but I have a java.lang.NullPointerException when it starts ...
2
votes
1answer
57 views

How to calculate number of indirect dependencies of a class?

Most of the static code analysis tools which analyse class dependencies generate dependency pairs of classes where each pair represents a direct dependency between two classes. Given those dependency ...
0
votes
2answers
74 views

Given a tree calculating Max Sum from top to bottom suing DFS? optimization?

given a tree i want to calculate max sum of each path from top to bottom. I used DFS for the operation. Here is the function which takes root as input and gives max sum of the path from top to bottom ...
0
votes
2answers
119 views

Time complexity analysis for recurrence relation

I was asked to figure out the time complexity analysis for the following recurrence relation T(n) = 4*T(n-1) + c. Basically, I did a replacement.. T(n-1) = 4 * T(n-2) + c and so on.. T(n) = 4^k T(1) ...
5
votes
2answers
1k views

Writing recursive functions

I am having a lot of trouble writing recursive functions related to trees. I can't just use google for these functions as they are not general and I won't be able to use google in an exam setting! Is ...
0
votes
4answers
8k views

Finding the time complexity of the following program that uses recursion

I need to find the time complexity in terms of Big Oh notation for the following program which computes the factorial of a given number: The program goes like this: public int fact(int n){ if (n ...
0
votes
0answers
32 views

What's the bound of the following recurrence?

Given the following recurrence: T(n) = T(n-1) + n^2 How can I prove it to be O(n^3) with the substitution method? The O(n^3) guess derives from the fact that at every step of the recursion we pay ...
5
votes
4answers
634 views

Does the Composite design pattern implement recursive behavior?

The Composite design pattern allows us to call an operation() on a 'composite' node in a tree structure, and this operation() will be called on all of the children, subchildren and so on. When an ...
2
votes
2answers
102 views

Why left recursion not looping?

I'm trying to read the parser of PHP, that says: top_statement_list: top_statement_list top_statement | /* empty */ ; It is a left-recursion, but why it don't looping infinitely? My ...
3
votes
1answer
366 views

How can I rewrite this linked-list manipulation as tail-recursive?

Given a liked list, I'd like to swap every pair of nodes as follows: input: a-b-c-d-e-f-g output: b-a-d-c-f-e-g If there's an odd number of nodes then the last node is tacked on as-is. This should ...
4
votes
2answers
395 views

Is this the right strategy to convert an in-level order binary tree to a doubly linked list?

So I recently came across this question - Make a function that converts a in-level-order binary tree into a doubly linked list. Apparently, it's a common interview question. This is the strategy I ...
0
votes
1answer
87 views

Recursion, iteration, and …? [closed]

Here are three common code structures that apply a function multiple times: foo(x) { if basecase(x) return k else return foo(g(x)) } uses recursion. for i in 0..10 { n *= bar(i) } uses ...
1
vote
3answers
281 views

Check distance between all elements in a list of numbers in O(n*lg(n))

I have an exercise for my algorithms and data structures class, where I basically have to implement a divide and conquer algorithm or function called check_distance to determine whether all numbers in ...
0
votes
1answer
124 views

What are the time and space complexities of this recursive method that reverses a singly linked list?

What are the Time and Space complexities of this Java method that reverses a singly linked list (of length n)? I'm more interested in knowing the reasoning behind the space complexity. Let me know if ...
0
votes
0answers
84 views

Software paradigms: prove that sum and sum1 are equal

Here are given two functions that calculate the sum of elements in a list. The proof should be done using induction. The hypothesis is: sum(as) = sum1(as, 0) def sum( as : List [ Int ] ) : Int = as ...
3
votes
4answers
846 views

Robot in a grid

This was recently asked to someone I know. A robot has to move in a grid which is in the form of a matrix. It can go to A(i,j)--> A(i+j,j) (Down) A(i,j)--> A(i,i+j) (Right) ...
1
vote
1answer
357 views

Is this a good example of open recursion?

I understand open recursion as the process of a method on a class calling another method on a class using a keyword such as this, but whereby the method call may actually be bound to a sub class at ...
15
votes
9answers
6k views

How do I explain “Recursion” to a 8 years old kid? [duplicate]

Possible Duplicate: In plain English, what is recursion? What is the best way to explain "Recursion" to 8 years old kid? I tried with the Fibonacci Series but i failed.
46
votes
18answers
26k views

In plain English, what is recursion?

The idea of recursion is not very common in real world. So, it seems a bit confusing to the novice programmers. Though, I guess, they become used to the concept gradually. So, what can be a nice ...
46
votes
17answers
5k views

Recursion without factorial, Fibonacci numbers etc

Almost every article I can find about recursion includes the examples of factorial or Fibonacci Numbers, which are: Math Useless in real life Are there some interesting non-math code examples to ...
2
votes
1answer
217 views

General Way to convert a loop (while/for) to recursion or from a recursion to a loop?

This problem is mainly focusing on the algorithm, maybe something abstract and more acedemic;) The example is offering a thought, I wanna a generic way, so example is only used as to make us more ...
0
votes
0answers
36 views

build list of possible permutations with dynamic set size

I'm trying to develop code/pseudocode to build a list of all permutations given the following data. I'm developing in a java-like language for a web app. I don't have any java libraries for this ...
5
votes
1answer
199 views

Best way to deal with Floors and Ceiling when using substitution method to solve Recurrences

I'm currently using substitution method to solve recurrences. The problem I'm having is dealing with T(n) that have either ceilings or floors. For example in the following example see example here. ...
27
votes
8answers
15k views

What methods are there to avoid a stack overflow in a recursive algorithm?

Question What are the possible ways to solve a stack overflow caused by an recursive algorithm? Example I'm trying to solve Project Euler problem 14 and decided to try it with a recursive ...
0
votes
2answers
115 views

Trouble understanding simple recursion in c [duplicate]

My function: int num(int x) { if(x>0) num(x-1); else return 0; printf("%d",x); } This function takes a input x and prints the numbers from 1 upto x.I can't seem to ...
1
vote
1answer
102 views

Why does this recursion method work? I have explored it for a day or two, and I cannot figure out why

Problem Statement: I have a tree with node values ( i , j ) where i , j < 1. The children of each node take on the values (i - 1, j), (i - 1, j - 1), and (i, j - 1) respectively. Now, i and j have ...
3
votes
2answers
141 views

Is there a (systematic) way to convert a recursive program to a version using user stack?

I have an image (an array of 1000 x 1000 pixels) of 1s and 0s. I was asked to do edge detection, so I wrote this program in C to traverse the figure. My idea was to convert every pixel surrounded by ...
11
votes
7answers
2k views

Recursion — is it “divide and conquer” or “code reuse”

Recursion -- as we all know -- is one of those problems -- that wrapping your head around feels like achieving a "milestone" in your programming voyage. But when it comes to actually using it in ...
0
votes
2answers
284 views

Is recursion a declarative approach to solve the problems?

I have noticed many problems in algorithms textbook are solved by recursion (divide and conquer, backtracking,...) As I tried to enhance my skills in writing them, I have noticed, I just need to ...
27
votes
4answers
6k views

Why doesn't Java have optimization for tail-recursion at all?

From what I have read: The reason is because it is not easy to determine which method will actually be called as we have inheritance. However, why doesn't Java at least have tail-recursion ...
5
votes
4answers
275 views

How to convert the following node evaluation procedure to a non recursive solution?

I have the following recursive method. It evaluates a node (that represent a logical expression), using deep first search traversal : EvaluateNode(Node node) { bool result; switch(node.Type) ...
5
votes
3answers
470 views

How can I best study a problem to determine whether recursion can/should be used?

In some cases, I fail to see that a problem could be solved by the divide and conquer method. To give a specific example, when studying the find max sub-array problem, my first approach is to brute ...
0
votes
1answer
90 views

Handling the process of large-scale lists [closed]

What are the efficient ways to process huge lists (+10 millions), and things to consider while manipulating huge lists. First question, when should I use recursion, and when I shouldn't. In both ...
1
vote
1answer
272 views

Is it possible to apply Master Theorem for finding the square and cube root

I was asked to calculate the running time of an algorithm which finds the square root and cube root of a given number. Is it possible to apply Master theorem with regards to this? First, I need to ...
1
vote
1answer
719 views

how to enumerate/generate all possible binary trees from N leaves and N-1 nodes?

I am trying to implement the 24 Game in ansi C. This game goes as follows: For a list of four given numbers, try to find a solution involving these four numbers, that, using addition(+), ...
2
votes
1answer
332 views

Do compilers un-inline recurrent expressions?

Does a compiler look for recurrent expressions to convert it into 'function' to reduce binary size and improve performance? Of course, the obvious answer might be "some do it, some don't", so I ask ...
3
votes
4answers
205 views

Wrap all external calls with flag to fight against recursion and double-entry?

Producing predictable output for each possible input is the responsibility of each module. For example (in C#): class Logger { public ITextWriter Writer { get; set; } private uint counter; ...
1
vote
1answer
170 views

How to efficiently sort a recursively defined Stack?

I am trying to implement a recursively defined Stack and sort it in Java. I don't have a particular usage of this program in mind. I found this approach of stack implementation a bit useful while ...
3
votes
3answers
4k views

Find all possible subarrays of an Array

I am lost I just can't seem to get my head around backtracking/recursion approaches. I understand how simple recursion problems like factorials work I can even trace those by hand. But when it comes ...
0
votes
3answers
203 views

What does this function do?

Does this function means its calculating x=(x-1) + x^2? Function unknown(x) if ( x == 1 ) return 1 else return unknown(x‐1) + x*x
21
votes
8answers
4k views

Are functional languages better at recursion?

TL;DR : Do functional languages handle recursion better than non-functional ones? I am currently reading Code Complete 2. At some point in the book, the author warns us about recursion. He says it ...
0
votes
3answers
241 views

How to convert this recursive problem to iterative? Line Simplification algorithm fails to run due to Maximum Recursion Depth being hit

I am implementing the Douglas, Peucker's Line Simplification algorithm in Python. I started with this implementation. However, it fails to run in Python due to Maximum Recursion Depth being hit. How ...
2
votes
2answers
175 views

Is this looping solution possible with recursion?

Eventually, I would like to generalize this solutions to work with a Tuple of any length. I think recursion is required for that, but I haven't been able to do it. def combineRanges(maxValues) : ...
2
votes
2answers
115 views

General recursion to tail-recursion

Is it theoretically possible to transform every kind of general-recursion into tail-recursion? Are they equivalent for example from a lambda-calculus point of view? That's a debate between me and an ...
2
votes
2answers
233 views

Calling same method on different object - Recursion?

I have an object that contains a reference to another object of the same type. Example in PHP: class A { protected $child; public function __construct(A $child = null) { ...
-1
votes
1answer
324 views

Recursion VS memory allocation [duplicate]

Which approach is most popular in real-world examples: recursion or iteration? For example, simple tree preorder traversal with recursion: void preorderTraversal( Node root ){ if( root == null ) ...
4
votes
3answers
3k views

Are there advantages for using recursion over iteration - other than sometimes readability and elegance? [duplicate]

I am about to make two assumptions. Please correct me if they're wrong: There isn't a recursive algorithm without an iterative equivalent. Iteration is always cheaper performance-wise than recursion ...
2
votes
3answers
111 views

Is there any point in writing a random tester for code that deals with inductive data structures?

Let's say we're writing a simple JSON parser and we've fully covered the code with unit tests: it can parse primitives "0", "123", "-456", '""', '"asd"', true, false it can parse arrays "[]", "[1, ...
2
votes
4answers
2k views

Can recursion be done in parallel? Would that make sense?

Say, I am using a simple recursive algo for fibonacci , which would be executed as: fib(5) -> fib(4)+fib(3) | | fib(3)+fib(2)| fib(2)+fib(1) and so on ...