The tag has no wiki summary.

learn more… | top users | synonyms

1
vote
0answers
68 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 ...
-1
votes
0answers
4 views

Reccursive function of the sequence $$U_n=\frac{1}{3} (\frac{A}{U^2_{n-1}} + \frac{1}{U_{n-2}})$$ [migrated]

#include<stdio.h> #include<conio.h> #include<math.h> void triple_root(float B[1000],int i,float A,float b,float c) { float x; x=0.333*((A/(b*b))+(1/c)); ...
-1
votes
1answer
65 views

Build odd and even hanoi tower [closed]

I've got problem with hanoi tower. I know how to build normal hanoi tower, it's simple: void solveTowers(char src, char dst, char mid, int n) { if (n == 0) { return; } ...
2
votes
1answer
146 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
1answer
40 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
0answers
31 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 ...
1
vote
3answers
212 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 ...
3
votes
4answers
667 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) ...
0
votes
2answers
107 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
97 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
134 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 ...
0
votes
2answers
261 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 ...
23
votes
4answers
4k 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 ...
0
votes
2answers
78 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
4answers
251 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) ...
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
220 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
504 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
321 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
3answers
2k 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 ...
1
vote
1answer
154 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
4answers
200 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; ...
0
votes
3answers
201 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
5
votes
1answer
196 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. ...
2
votes
2answers
167 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) : ...
0
votes
3answers
207 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
109 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
191 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) { ...
3
votes
1answer
339 views

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

This is an interview question I was once asked, and now I ask many of my interviewees. I have yet to see anyone come up with a tail-recursive solution during the interview. Given a liked list, I'd ...
-1
votes
1answer
232 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
108 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
1k 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 ...
3
votes
2answers
1k views

Is recursive code slower than non-recursive code?

Now I'm only a novice programmer, but what my friends that are studying programming tell me is that recursive code is a good thing, it leads to less code duplication and it looks more elegant. Now ...
1
vote
5answers
1k views

What are the advantages of recursion compared to iteration? [duplicate]

I'm trying to understand when is preferred to use recursion rather than iteration. Actually I've encountered recursion only in Javascript but never in Python. I imagine that recursion should be used ...
3
votes
1answer
1k views

Utilising Promises, Closures and Recursion in Node.js

I have employed a recursive call to a closure in order to mitigate against some race conditions I am getting (That's what I think it is). I'd like to know if (and why) this is a good solution or a bad ...
0
votes
1answer
185 views

Designing software functions which are both pausable and restartable

Consider the following situation: One hardware device, two applications (1 C# application, 1 Firmware). The C# application sends frames to the firmware and the firmware executes scripts. C# -> ...
5
votes
3answers
492 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 ...
3
votes
1answer
90 views

Applying the Art Gallery problem to optimal sensor placement

I am trying to design an algorithm for optimal sensor placement in a given area. After doing some research I found the Art Gallery Problem. However, this problem assumes that the guards can see all ...
0
votes
2answers
57 views

Is array dependence on previous terms considered recursive?

For example, take the case of Fibonacci number to calculate nth number you require n-1 and n-2 term. If I do it with bottom up approach, is it recursion as f(n) depends on f(n-1)?
1
vote
1answer
323 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 ...
3
votes
1answer
311 views

How can Lisp produce an iterative process from a recursive procedure?

I am starting to learn Lisp, using the SICP book. The authors mention that a procedure (i.e. function) can be recursive or iterative. Additionally, the process those procedures will generate will also ...
0
votes
1answer
54 views

Verify 0 or 2+ sub sections in a section

There is a rule in writing: When you break a section into subsections, typically it should have more than one subsection. This goes back to the old high school composition rules: if you have an A. ...
6
votes
2answers
648 views

Can someone explain the concept behind Haskell's memoization?

(note I'm putting the question here because it's about the conceptual mechanics of it, rather than a coding problem) I was working on a small program, that was using a sequence of fibonacci numbers ...
0
votes
1answer
117 views

Better way to create samples

I've done this piece of code for creating bernulli samples, but I think that it is a so heavy algorithm because every time I call this recursive function I create a new vector that is passed to it. Is ...
-2
votes
1answer
451 views

Find product using summation C# Problem? [closed]

I am trying to write a simple program to find the product of two numbers (X, Y) without using multiplication. Meaning that I will only use summation to find the product. I am trying to use the ...
8
votes
4answers
795 views

When there's no TCO, when to worry about blowing the stack?

Every single time there's a discussion about a new programming language targetting the JVM, there are inevitably people saying things like: "The JVM doesn't support tail-call optimization, so I ...
0
votes
2answers
869 views

Getting the relational table data into XML recursively

I have levels of tables (Level1, Level2, Level3, ...) For simplicity, we'll say I have 3 levels. The rows in the higher level tables are parents of lower level table rows. The relationship does not ...
0
votes
1answer
172 views

Trace code pascal [closed]

I haven't worked with Pascal so far, and my problem is understanding the recursive aspects that prm assignment operators and how the final (correct) value is derived. Would someone please explain that ...
3
votes
1answer
2k views

Tips for Tail Call Recursion in Python [duplicate]

Ok, Python doesn't have tail call optimization. But for those who think better recursively than "looply", whats the best practices to write code?? 1000 stack calls are enough for many cases, but ...