Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Questions tagged [recursion]

For questions about recursion, the practice of calling a method or function from within itself.

Filter by
Sorted by
Tagged with
1 vote
9 answers
3k views

can every program still be written without recursion or cyclic calls?

I'm wondering if it was theoretically possible for a compiler to determine maximum stack depth at compile time if a limitation was placed on the program. The limitation being that you can't use ...
glades's user avatar
  • 419
3 votes
2 answers
528 views

Maintaining global states in a recursive function

I am writing a recursive function. Some of the parameter data is different for each recursive call but some of the data only need to have one copy existing at any one time during the recursive call. ...
CPlus's user avatar
  • 1,187
13 votes
8 answers
6k views

How do compilers work in a language that doesn't allow recursion?

I'm recently learning the programming language, and I wonder how compilers work when the language itself does not allow recursion, like how the compiler or the runtime checkers makes sure that there ...
csxyyyyy's user avatar
  • 151
0 votes
1 answer
126 views

Is there a name for this technique of simplifying recursion code by passing some logic from the caller to the callee?

The technique involves moving some logic from the caller to the callee. Usually the logic that is moved is a check. Here's an example of the technique applied to code that solves the "Construct ...
joseville's user avatar
  • 123
0 votes
1 answer
42 views

How do I create a new class or struct with property of its own type?

I have been trying to figure out if I can create a class or struct with a property that is of the same class or struct. An example would be struct Number { var Value: Int = 0 var Rate: Number(...
Timothy's user avatar
2 votes
3 answers
395 views

Are user-callable recursive functions an anti-pattern?

I have a function in python that calls itself recursively, and has some internal variables passed down the recursion using keyword arguments (that are not listed in the docstring) Is it a problem to ...
holox's user avatar
  • 31
1 vote
2 answers
980 views

Calling recursive method in a loop - Backtracking

I'm confused about a matter that I've been unable to figure out. I'm doing some leetcode problems. In backtracking problems, sometimes we use loop within our recursive method to call the recursion but ...
Umer Farooq's user avatar
2 votes
3 answers
972 views

Are lessons on tail recursion transferable to languages that don't optimize for it?

I'm currently reading through Structure and Interpretation of Computer Programs (SICP). During the course of that book, the lesson of "you can optimize recursive procedures by writing them as ...
J. Mini's user avatar
  • 1,017
23 votes
8 answers
12k views

Can I use additional parameters in recursion problems?

Okay, I was being interviewed at a company and the interviewer asked me a recursion problem. It was an online interview, so, he had set up the problem statement and a function signature on CodeSandbox ...
Bharat Soni's user avatar
0 votes
5 answers
486 views

How to deail with a hypothetical situation in which a pub/sub cycle gets into an unending recursive loop?

Let me explain what I mean. Imagine A subs to event b. In such case A pubs event a. B subs to event a. In this case B subs b. This is a full-blown circle. How does a pub/sub cycle deal with such ...
Aurlito's user avatar
  • 27
-3 votes
2 answers
172 views

Recursion + Stack/Queue usage in practical life implementation [closed]

I am very new to Data Structures and Algorithms. I want to use recursion + stack/queue in a grocery store inventory program that I am making. However, I can't come up with any good ways of using ...
potatoooooooooo's user avatar
0 votes
1 answer
92 views

Recursive speculative display list engine - computing text length across stack boundaries

Well, I've been hammering away on this for about a week now with no practical progress because I can't find mental fluidity with the concepts I'm trying to wrangle. I'm Officially Stumped, and would ...
i336_'s user avatar
  • 289
-2 votes
1 answer
2k views

Iterative Sorts vs. Recursive Sorts

Naive sorts like Bubble Sort and Insertion Sort are inefficient and hence we use more efficient algorithms such as Quicksort and Merge Sort. But then, these two sorts are recursive in nature, and ...
user avatar
5 votes
6 answers
2k views

Making recursion optional: Bad practice?

Let's say I have a function like this: /* Mode is a bool that determines whether the function uses it's recursive mode or not */ public static int func(int n, boolean mode) { if (!mode) ...
JohnnyApplesauce's user avatar
0 votes
2 answers
331 views

Representing a recursive Structure in OOP

I want to represent an Edifact message in an OOP Language. An Edifact message has the following structure: message := [ ( segment | segmentgroup ) ] segmentgroup : = [ ( segment | segmentgroup ) ...
Martin Böschen's user avatar
0 votes
1 answer
903 views

Walking a graph without recursion

I'm working on a class that receives a relational EDM/data model (e.g. a SQL DB or OData API manifest) and performs a couple tasks on them (not necessarily at the same time, could be two separate runs)...
Josh's user avatar
  • 170
1 vote
6 answers
1k views

If the whole point of recursion is to break the problem into multiple smaller problems, what if those problems were solved in parallel?

So I was studying here and I was thinking if the whole point of recursion is to break the problem into multiple smaller problems, what if those problems were solved in parallel? A quick search lead me ...
João Areias's user avatar
-1 votes
1 answer
980 views

What happens when loops are compiled or interpreted?

I have came across a concept in recursion which says that when loops are compiled or interpreted then they get converted to recursive functions. If it is true how it takes place ?
Ashwani Sharma's user avatar
2 votes
1 answer
3k views

How to optimize reusing a large std::unordered_map as a temporary in a frequently called function?

Simplified question with a working example: I want to reuse a std::unordered_map (let's call it umap) multiple times, similar to the following dummy code (which does not do anything meaningful). How ...
Abaris's user avatar
  • 31
1 vote
2 answers
3k views

Pass-Through parameters in recursive code

When writing large amounts of recursive code (for valid reasons), I have come across many parameters that are not used in specific functions, but are still needed for a subset of all of the functions. ...
Yurihaia's user avatar
-1 votes
1 answer
658 views

True or false about recursion

I am working on a quiz for a computer science course. I would like to check that the following statement is false: A recursive call may never generate more than one recursive call for the ...
Niklas Rosencrantz's user avatar
0 votes
1 answer
118 views

Express unique recursive task system

I would like to express a task as either itself or a container for other tasks (recursively). The problem is that each task has to be one of two fundamental types: a goal or a routine. And, children ...
clabe45's user avatar
  • 103
2 votes
2 answers
2k views

Patterns for tracking state in recursive Haskell code

A frequent pattern in my Haskell code is element-wise recursion for transformation of a list with some carried state generated using the data in the list. Usually, this looks something like this: ...
TheEnvironmentalist's user avatar
0 votes
1 answer
143 views

Generating combinations without getting stuck in recursive calls

This question is about figuring the design of a recursive function that changes the state of a group of elements by processing one of them at a time, with the goal of reaching a desired state. The ...
dabadaba's user avatar
  • 2,256
7 votes
0 answers
263 views

Why does GHC represent recursion in Haskell with recursive binders instead of a fixpoint operator?

GHC's Core data type represents recursion with recursive binders in the Let constructor; as I understand it, all let expressions in Haskell are effectively let rec expressions. Why does GHC use this ...
DylanSp's user avatar
  • 275
3 votes
1 answer
327 views

What is best practice for handling mapping arbitrary depth in arrays?

I have a set of data: id | name | parentid ------------------------ 1 | parent | 0 2 | child | 1 3 | child | 1 4 | parent | 0 5 | child | 4 6 | subchild | 5 7 | child | 4 ...
amflare's user avatar
  • 241
0 votes
1 answer
55 views

Question about memory handling of trees and certain sorts on large data sets.

If data structures such as trees and certain sorts(quick sort, merge sort) work using recursive algorithms and recursive algorithms take up a lot of memory space in the stack and can only work on a ...
Angel's user avatar
  • 21
-1 votes
1 answer
120 views

Inserting at head for a recursively defined linked list

This article states However, this design does run into problems with some of the methods of the MutableSequence ABC. Most notably, insert and __ delitem __ can't operate on position 0, because ...
Trent Di's user avatar
0 votes
1 answer
1k views

An elegant way to detect the end of an asynchronous recursive file search?

Given a recursive subroutine in single threaded environment which starts numerous asynchronous I/O operations and registers callback functions for each of them. This callbacks will be called on the ...
atevm's user avatar
  • 111
0 votes
1 answer
527 views

Recursion explanation

I am not able to understand this basic recursion example. When I executed this code. The output was 43210. Should not the output be 44444, as the value of num is updated to 4 to the latest recursive ...
penta's user avatar
  • 135
0 votes
1 answer
203 views

Memoization in case of recursive interdefined functions in Haskell/Functional Programming?

I was reading Memoization with recursion which tells how for a recursively defined function fun we can do memoization by: -- Memoization memoize f = (map f [0 ..] !!) -- Base cases g f 0 = 0 g f 1 = ...
RE60K's user avatar
  • 267
10 votes
4 answers
1k views

What are the considerations to determine whether you can use recursion to solve a problem?

Sometimes in interviews, I may use recursion to solve a problem (such as adding 1 to an infinite precision integer), or when the problem presents itself suitable to use recursion. Sometimes, it might ...
nonopolarity's user avatar
  • 1,827
0 votes
1 answer
2k views

Eliminating recursion

It is easy to eliminate tail recursion. There are few curious cases where the not-tail recursion can also be eliminated. Exhibit 1: Fibonacci numbers. A naive recursive solution fib(n) if (n &...
user58697's user avatar
  • 129
2 votes
1 answer
3k views

How do I represent a recursive process down a tree in a sequence diagramm?

I'm working on a sequence diagram for a layered system that has a tree hierarchy. Now I have a process that works itself recursively down the tree. Meaning calling the same function on a child object. ...
Herr Derb's user avatar
  • 429
2 votes
2 answers
3k views

Efficiency considerations: nested loop vs recursion

I would consider myself an intermediate Python programmer. One of my recent challenges was creating a list of all possible solutions to a given Countdown problem. Without getting into too much detail,...
IliaK's user avatar
  • 23
0 votes
2 answers
1k views

How do I write an algorithm to solve a set of 3 symbolic equations

Replace each symbol (letter) with a number so that the equations hold across all 3 equations. Solution should be able to solve the general case of any 3 equations. Can assume 2 terms summed to an ...
Atomix's user avatar
  • 679
0 votes
1 answer
82 views

Why isn't this combinatorial solution equivalent to the recursive solution for finding the number of "paths"?

Here's the problem: Given an m x n array, get the number of different paths from the top left corner to the bottom right corner, if you can only move down, right, and diagonally down & right. ...
Neel's user avatar
  • 105
7 votes
5 answers
15k views

Why does recursion return the first call in the stack and not the last?

I cant for the life of me figure out why this returns 0 rather than 5. i keeps getting incremented before it hits the last return statement, however it always returns 0, from the first call in the ...
NightSkyCode's user avatar
5 votes
1 answer
2k views

How does K&R's qsort work?

In the recursion section of K&R's ANSI C book, they demonstrate a version of quicksort [that] is not the fastest possible, but it's one of the simplest. --The C Programming Language (ANSI ...
user1717828's user avatar
1 vote
2 answers
584 views

How to decide how to build a recursive function

Sometimes when you're coding you're on a problem which can be solved with some recursive method. What is for you the best way to detect when the recursion is a good way to solve a problem and how to ...
toto's user avatar
  • 21
2 votes
2 answers
2k views

Designing the recursive solution

I understand the recursion and find it useful and intuitive while solving problems on trees but for many other problems recursion never fails me to leave puzzled. Recently I was solving the following ...
CodeYogi's user avatar
  • 2,176
3 votes
1 answer
416 views

Are recursions intrinsically less safe than iterations?

Java doesn't have a predefined recursion depth limit. As a result the recursion below (a dummy method that returns the value) throws java.lang.StackOverflowError after 62844 (with static) and 14002 (...
sixtytrees's user avatar
3 votes
1 answer
12k views

how is stack and heap are assigned to each processes?

How multiples processes are stored in the main memory , i understand every process will be divided into the equal size pages and will be stored in the frames of main memory. if whole main memory is ...
navs4me's user avatar
  • 39
46 votes
11 answers
30k views

Is a while loop intrinsically a recursion?

I wondered whether a while loop is intrinsically a recursion? I think it is because a while loop can be seen as a function that calls itself at the end. If it is not recursion, then what is the ...
badbye's user avatar
  • 585
3 votes
3 answers
2k views

How to mentally keep track of recursion

I have great trouble doing recursion, especially trying to visualize it. A great example is the aging wine problem described in the top answer of this link: https://www.quora.com/Are-there-any-good-...
mrQWERTY's user avatar
  • 243
5 votes
6 answers
21k views

Recursion in Merge Sort algorithm. How is it obvious to use this type of recursion?

I dont want to put too much code so I'll just put the code that involves recursion. This algorithm is fairly well known so I think everybody knows the basic code. void mergeSort(int array[], int l, ...
DLV's user avatar
  • 301
0 votes
1 answer
81 views

Reflexive calls of objects in the same hierarchy

I am not sure how to phrase this. I believe this should have been asked somewhere, but I am unable to find it because I don't know the keywords. Basically, I have some types like this: interface Foo ...
SOFe's user avatar
  • 708
-2 votes
1 answer
5k views

How does this recursive function exit? [closed]

In the merge_sort part, there are multiple calls to the same function within the recursive. How are the other two executed when the definition holds that till a condition is false, the recursion does ...
Harsha Vardhan K's user avatar
0 votes
2 answers
3k views

Implementing map with tail recursion

I am trying to solve this exercise. It is about reimplementing the map function in haskell for learning purpose. I found a solution which doesn't browse all the elements of the list (simple linked ...
Moebius's user avatar
  • 103
3 votes
0 answers
225 views

String Pattern Matching from Lookup Table - Non-Exponential Solution?

Given the problem... Given a String comprising of non-alhpabetical symbols, and a Lookup Table where a subset of those symbols may equate to a single alphabetical character, output all possible ...
Kevin's user avatar
  • 131