Questions tagged [recursion]
Recursion in computer science is a method of problem solving where the solution to a problem depends on solutions to smaller instances of the same problem.
78
questions
39
votes
4answers
6k views
Rainfall challenge
About a year ago when I was applying to jobs for the first time, I had an interview at a company and they posed the following problem to me, which I preceded to bomb.
A year later I actually came up ...
3
votes
1answer
76 views
A recursive_transform Template Function with Execution Policy
This is a follow-up question for A recursive_transform for std::vector with various return type, A recursive_transform Function For Various Type Nested Iterable With std::variant Implementation in C++ ...
14
votes
3answers
3k views
N-Queens - Brute force - bit by bit
A discussion in The 2nd Monitor made me realize I had never 'solved' the N-Queens problem. Additionally, as I read up on it, I realized that the 64-squares in a chess board would work well if ...
27
votes
2answers
3k views
Sudoku using 'exact cover' solver
1. Introduction
This is a solution to Weekend Challenge #3: a Sudoku solver in Python. It works by translating a Sudoku puzzle into an exact cover problem, and then solving the exact cover problem ...
12
votes
6answers
4k views
Python 3 - Fibonacci Implementation
I wrote a function returning the n-th Fibonacci number in Python 3:
...
5
votes
1answer
121 views
A recursive_transform for std::vector with various return type
This is the follow-up question for A recursive_transform Function For Various Type Nested Iterable With std::variant Implementation in C++ and A get_from_variant function in C++. Thanks to G. Sliepen ...
8
votes
2answers
2k views
Recursive flattening of Swift sequences
In Flatten to get all child controls of certain type in a UIView, methods were discussed to
recursively flatten a tree-like structure in Swift, resulting in an array
of all elements.
Motivated by ...
7
votes
1answer
116 views
Non-nested std::deque and std::list Generator Function for arithmetic_mean Function Testing in C++
This is a follow-up question for A non-nested test_vectors_generator Function for arithmetic_mean Function Testing in C++ and An arithmetic_mean Function For Various Type Arbitrary Nested Iterable ...
4
votes
3answers
2k views
(Re)Creating a tree from a flat collection (or “unflatten” a tree)
I need to create a tree from a flat collection. The order of elements is defined in a specification so it's rather impossible that it will ever change... but I want the whole algorithm to be ...
4
votes
1answer
271 views
Counting ways to fit bottles in crates
I'm calculating how many possibilities there are to fit \$n\$ identical bottles inside \$k\$ crates of various capacities.
n = Number of bottles
k = Number of crates
K = List of the number of bottles ...
4
votes
1answer
104 views
A Summation Function For Various Type Arbitrary Nested Iterable Implementation in C++
This is the follow-up question for A Summation Function For Arbitrary Nested Vector Implementation in C++. The following code is the improved version based on Zeta's answer. I am trying to enhance ...
3
votes
1answer
79 views
An arithmetic_mean Function For Various Type Arbitrary Nested Iterable Implementation in C++
This is a follow-up question for A recursive_count Function For Various Type Arbitrary Nested Iterable Implementation in C++ and A Summation Function For Boost.MultiArray in C++. I am trying to ...
17
votes
2answers
2k views
A KenKen puzzle/solver in Python
I've written a simple KenKen puzzle/solver in Python. I'd love some feedback on the design of the puzzle, as well as the architecture for the solver.
To model the puzzle, I have the following classes:...
12
votes
1answer
2k views
Flatten an array of integers in Python
The goal is to flatten an array of nested arrays of integers.
For example [1, [2], [3, [4]]] should return [1, 2, 3, 4]
I'm ...
7
votes
4answers
19k views
Fibonacci sum with memoization
Problem:
Using the recursion approach, find a Fibonacci sum without repetition of computation.
...
5
votes
5answers
11k views
DFS in Binary Tree
I have written this code for DFS in a binary tree and would like improvements on it.
...
11
votes
2answers
35k views
How can I avoid unchecked cast warning in my generic recursive Iterator?
It's somewhat odd that Java's collection framework has no iterator for recursive data structures. Since I needed something like this, I wrote my own. First off, I need recursive elements:
...
8
votes
3answers
2k views
Stock Pipe Cutting using Recursion
This problem is from the Stanford Open Course CS106B Programming Abstractions Assignment #3
Problem number 6 here.
"You are charged with buying the plumbing pipes for a construction project. Your ...
9
votes
2answers
246 views
8
votes
3answers
201 views
A Summation Function For Arbitrary Nested Vector Implementation In C++
I am trying to deal with some calculations on nested vector data in C++. The nested vector data may be like std::vector<long double>, ...
6
votes
1answer
358 views
Recursive implementation of merge sort
Information about my code:
I am following this MIT OCW algorithms course. The first lecture described insertion sort and merge sort. I implemented merge sort in C.
The algorithm is structured as a ...
6
votes
2answers
147 views
A recursive program that attempts to solve an extremely large number
This is my recursive program for the following function:
\$F(x) = G(x) - W(x)\$
\$G(x) = [G(x-1)+G(x-2)]^2\$
\$W(x) = [W(x-1)]^2 + [W(x-2)]^2\$
If x == 0 in either function G or function W, then ...
5
votes
1answer
263 views
Knights Tour - Improved Refactored Recursive Breadth First Search for
The development and testing was performed on a Dell M6400 Laptop (Intel Core 2 Duo) running Centos 7, g++ compiler version 4.8.5, compiler switches -O3 -std=c++0x -D__cplusplus=201103L. (machine ...
5
votes
2answers
8k views
Numeric expression parser - calculator
In particular, if someone could describe a better way to go from the tokenized list to the Expression tree, it would be super helpful. I would like to get rid of the casting in the parser but am not ...
4
votes
1answer
106 views
A Summation Function For Boost.MultiArray in C++
This is a follow-up question for
A Summation Function For Arbitrary Nested Vector Implementation In C++ and A Summation Function For Various Type Arbitrary Nested Iterable Implementation in C++. I am ...
4
votes
3answers
9k views
Finding objects with even references tidier
As the title says, I'm trying to make my code less horrible looking! For a university practical, I've to use recursive methods to return the even references in a collection of Integer objects stored ...
4
votes
1answer
591 views
CLRS Exercise 2.3-4: Recursive Insertion Sort
I'm going through CLRS 3e and executing exercises to obtain a better understanding of CS fundamentals.
Below is my solution to the following exercise from chapter 2:
We can express insertion sort ...
3
votes
1answer
72 views
An element_wise_add Function For Boost.MultiArray in C++
This is a follow-up question for A Summation Function For Boost.MultiArray in C++. Besides the summation operation of all elements, I am trying to focus on the element-wise operation here. The main ...
2
votes
2answers
917 views
A set of names and a request with asterisks
I have a set of names and a request with asterisks. An asterisk can be replaced with any letter.
For example, there is a set of names: hasad, ahmed, fizo. And there are a few sample requests: hasad, ...
2
votes
1answer
79 views
A recursive_transform Function For Various Type Nested Iterable With std::variant Implementation in C++
This is a follow-up question for A TransformAll Function For Various Type Arbitrary Nested Iterable Implementation in C++. The following code is the improved version based on G. Sliepen's answer. In ...
1
vote
0answers
51 views
A recursive_count_if Function with Specified value_type for Various Type Arbitrary Nested Iterable Implementation in C++
This is a follow-up question for A recursive_count_if Function For Various Type Arbitrary Nested Iterable Implementation in C++. Thanks to Quuxplusone's answer and G. Sliepen's comments. Based on the ...
19
votes
0answers
295 views
Multiplying big numbers using Karatsuba's method
The Karatsuba algorithm, first published in 1962, aims to speed up the multiplication of big numbers by reducing the number of 'single-digit-multiplications' involved.
Because of its complexity (...
15
votes
2answers
322 views
My recursive parser is wet behind the ears (well, it's not DRY at least)
I have an issue opened on GitHub since mid-November, to refactor & DRY up the Rubberduck Parser module (the idea is to model the code in a VBA project or code ...
11
votes
2answers
244 views
Let's Break Down the Party by Breaking the Party Down Recursively
This is a rags-to-riches an overdue alternative implementation on my previous question: Let's Break Down the Party
This alternative uses the int internal ...
8
votes
2answers
3k views
Is this non-recursive mergesort efficient and a good way to simulate the recursive version?
My teacher assigned us to do the recursive version of mergesort, yet I heard that the non-recursive version (bottom up) is a bit tougher, so I decided to this one as well. My main concerns are:
...
7
votes
1answer
7k views
Maximum Subarray Problem - Recursive O(n log n) algorithm
I have implemented a recursive O(n log n) algorithm for solving the maximum sub-array problem. I would like a general review for it.
Here the ...
6
votes
1answer
474 views
Change tracking POCO entities
Description
In a time where thin clients, web browsers, web services and micro services are prevalent, we tend to forget we still have to deal with thick and smart clients. Many applications in B2B ...
6
votes
2answers
377 views
Selection Sort Algorithm (Node.js)
I wanted to implement a selection sort and wanted to make sure that I'm doing it correctly. I wanted to do it in a way that's efficient and use recursion. Please let me know if I am doing this ...
6
votes
3answers
7k views
Tree structure with support for inorder and preorder traversal
I am learning Tree Data Structures and came up with this code for implementing basic Tree Node using class and performing various Tree based operations like Traversals and others. The code works ...
6
votes
3answers
1k views
Deep/recursive join, all, any, sum, len
I keep forgetting that the standard join() can only take a single iterable, so I made a few functions that act recursively on any passed arguments. Somewhat ...
6
votes
2answers
2k views
Consecutive Primes challenge at CodeEval.com and memory allocation issue
I finally solved this challenge with using recursion and figured out why the automatic scorer wasn't passing my previous solutions. I was using NSMutableArray to ...
6
votes
1answer
105 views
'Tis the season for gift-wrapping
When reviewing a Graham scan convex hull algorithm implementation, I wrote the following function in an answer:
...
5
votes
1answer
777 views
A recursive Boggle solver
`Boggle is a word game in which letters are randomly placed in a 4x4 grid
e.g:
A D Q P
N L E M
O S R T
V K J H
Words can be started from any letter and are ...
5
votes
0answers
446 views
Recursive conversion from ExpandoObject to Dictionary<string, object> #2
Because my original question was lacking many details, I have been advised to ask a new question.
I will repeat the important parts of the original question and add examples etc to hopefully make it ...
5
votes
2answers
3k views
Knight's Tour with Heuristics
When someone suggested that I solve Knight's Tour, I did so with heuristics and recursion.
It takes a lot of time to solve even a 8x8 board:
N-A1
N-C2
N-E1
...
N-E6
N-F4
Time used to solve: 5417011 ...
5
votes
2answers
436 views
BF interpreter in Python that uses recursion to handle loops
I wrote a Brainfuck interpreter in Python and I'm wondering how to simplify it.
I handle separately loop commands and the others. A recursive function deals with loops.
...
4
votes
4answers
2k views
Recursive conversion from ExpandoObject to Dictionary<string, object>
For my blazor library which is a modification of this awesome library I have to convert an ExpandoObject into a ...
4
votes
2answers
280 views
Importing different type of files into Lists
I am using a recursive directory scan to find all objects inside a Unity3D project. After that, I wish to move all these files to a sorted List. Is there a cleaner ...
4
votes
3answers
683 views
Java Magic square program
Here is my improved version of my Magic square program from following this earlier version.
I also added a few comments.
Any help for improvements would be really appreciated.
...
4
votes
3answers
1k views
