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.

69 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
15
votes
0answers
183 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 (...
8
votes
1answer
627 views

Function that recursively downloads entire directory is slow

I created this function to recursively copy an entire directory from an FTP server. It works just fine except that it is about 4 times slower than using FileZilla to do the same operation. It takes ...
7
votes
0answers
137 views

Modeling tabular structure in MSSQL to store data like Excel sheet applying Column inheritance

I've created this database structure to store tabular information (it's a simplification of my real structure but enough to show the point). In it I have Sheets and ...
6
votes
0answers
409 views

Implementing recursive filters with Haskell/Repa

I recently learned Haskell, and I am trying to apply it to the code I use in order to get a feeling for the language. I really like the Repa library since I manipulate a lot of multi-dimensional data....
5
votes
0answers
70 views

Mahjong hand completeness checking algorithm

As a summer project, I have been working on a small-scale, console-based version of Mahjong (the Rummy-like hand completion game, and not the solitaire version). While having prior knowledge of the ...
5
votes
0answers
37 views

JS deep merging of objects- removing empty keys

I've written a helper for combining objects (deep merge). It works, and is flexible to add options (like uniq and replace). ...
5
votes
0answers
164 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
0answers
508 views

Codewars: N-dimensional Von Neumann Neighborhood in a matrix

Task: For creating this challenge on Codewars I need a very performant function that calculates Von Neumann Neighborhood in a N-dimensional array. This function will be called about 2000 times The ...
5
votes
0answers
153 views

Assembling and traversing a graph, given a list of items and parent pointers

I've written a function which takes input such as this: ...
4
votes
0answers
101 views

All the paths from the root to the leaves

Given a binary tree, return all root-to-leaf paths. Example: -- 1 / \ 2 3 \ 5 Output should be: ["1->2->5", "1->3"] My approach: I walk the branches ...
4
votes
0answers
751 views

AWS EC2 metadata fetcher in Python

Update https://docs.aws.amazon.com/AWSEC2/latest/UserGuide/ec2-instance-metadata.html This seems to be the schema for the instance metadata, though the way they describe it isn't really handy for ...
4
votes
0answers
130 views

Given a string of letters, output all English words formable using only those letters

As an introduction to Python classes and an exercise in recursion / tree-traversal, I wrote a small script that forms all English words using only the letters in an input string. Useful for things ...
3
votes
0answers
42 views

reverse recursive search on an object with javascript - like tree search

I implemented a tree search with JavaScript. It has below basic rules. It will search over an array of objects which has recursive(like fractal) If it found a according data in a leaf(the final ...
3
votes
0answers
58 views

Shortest Cell Path In a given grid

I was given this problem in a mock interview. I would appreciate a review of my implementation. Shortest Cell Path In a given grid of 0s and 1s, we have some starting row and column sr, sc and a ...
3
votes
1answer
127 views

React.js Nested Nav Bar

This was written for a coding challenge for a company I recently starting working for. I'm looking for any suggestions on how to clean up the code, as well as any issues anyone thinks may occur as it ...
3
votes
0answers
43 views

Creating a series of relationship hierarchies from a list of nodes and connections

I have put together some code that creates a tree structure from a large list of nodes (entities) and connections and am looking to speed it up. HierarchyWorker: Converts the list data into the tree ...
3
votes
0answers
288 views

Recursive solution for Longest Substring Without Repeating Characters written in Elixir

Here's my recursive implementation of a sliding window algorithm to find the longest substring of a given string without repeating characters. Is there a more idiomatic-Elixir way to write this? <...
3
votes
0answers
115 views

Merging bin-data via a bin count threshold

When performing a chi-squared test, one takes the square of the differences of the expected counts per bin and observed counts per bin, and divides these per-bin differences by the expected counts per ...
3
votes
0answers
78 views

Minimum number of basic operations to convert str1 into str2

I am to convert a given string into another using only three basic operations, that is by deleting, inserting or replacing a character. Changes can only be made to string 1 and it is given that the ...
3
votes
0answers
196 views

Recursive JavaScript Permutations Function

I have a recursive function that calculates the permutations of a given list/array list. Although a similar implementation works great in Python, this JavaScript ...
3
votes
0answers
300 views

Recursive function to compare XML files using MSXML DOM

I have put together this function which compares two XMLs. On debugging, I found out that there are lot of useless loops which might cause performance problems for me if the files to compare are very ...
3
votes
0answers
63 views

Enabling parents and dependencies of selected items recursively

I have a class Feature as such: ...
3
votes
0answers
505 views

Recursively list files in provided directory in the style of `npm ls`

I've written a small CLI node program to list the contents of a directory with an output similar to that provided by npm ls but listing both files and directories, ...
3
votes
0answers
325 views

CodeEval - Lucky Tickets challenge

This a solution to the CodeEval's challenge "Lucky Tickets". After a failed attempt with brute-force calculations (no surprise here), I have tried to implement an algorithm that I found on ...
3
votes
0answers
265 views

Print the nodes of binary tree column-wise, using recursion and iteration

I am trying to code for both recursive and iterative approach to a problem. Below is a recursive code to print the nodes of binarytree column wise. Basically I have count of root as 0 and if I move ...
3
votes
1answer
407 views

Recursion into git diff tree using nodegit

I'm using nodegit to develop the backend for a nodejs app that uses a mix of mongodb and git for persistence. The app has to version documents and be able to present diffs between versions, thus the ...
2
votes
0answers
20 views

File and folder filter for a “last-updated explorer”

Sometimes I save a file somewhere but can't find it after or I install something and want to see what files were added. For this reason, I created a winforms app which only displayes files created/...
2
votes
0answers
33 views

Leetcode Finding Maximum Area of Island Solution

Given a non-empty 2D array grid of 0's and 1's, an island is a group of 1's (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are ...
2
votes
0answers
46 views

JSON flattening with object duplication on array property for CSV generation

I am looking for a way to transform JSON data into a flat "csv-like" data object. In some way, I am looking to "sqlirize" a mongodb collection. I have already check some json flat libraries in NPM ...
2
votes
1answer
33 views

Performing an action which may return other actions to be performed, concurrently

I have a program which, at its core, involves repeatedly performing an action on some value, and based on that action also returning a list of new values to perform that action on. The pure version of ...
2
votes
2answers
46 views

Listing ordered components, recursively

I am trying to get ordered components of an interface properly without having a local variable orderedComponents outside, and here is my current code. Reason is because orderedComponents will be in ...
2
votes
0answers
32 views

Finding first duplicated value from “circular” list with a recursive function

Background This year I've taken on the challenge of Advent of Code. The second challenge of the first day is to calculate a frequency for a special device based on a series of numbers. Here's a quote ...
2
votes
0answers
34 views

Flatten Hierarchical Categories

I have an XLSX file that contains a hierarchical list of categories. Each category has a basic query associated with it. I need to flatten these categories which involves combining the categories. I ...
2
votes
0answers
595 views

Robot on a Grid: Find a path between two corners with forbidden cells on the road

Problem statement The problem is defined in the book as following: 8.2 Robot in a Grid Imagine a robot sitting on the upper left corner of grid with r rows and <...
2
votes
1answer
192 views

Check the equality for each subset of a string S against the target T and return a count

I wrote the following code to solve this leetcode problem: ...
2
votes
0answers
243 views

Follow-up 1: Compare 2 unordered, rooted trees for shape-isomorphism

The previous post can be found here. In the previous post I tried to solve an exercise but found through the answer of Peilonrayz a bug in the code and 2 more while fixing it. These have now been ...
2
votes
0answers
1k views

Recursive matrix multiplication in C++

I'm working through CLRS, and I'm hoping to get some pointers (ha!) on my C++ coding style and the way I've implemented recursive matrix multiplication. The code right now seems a bit complex for ...
2
votes
0answers
39 views

Generalizing work orders

I am working on designing tables for work orders. The problem: There is different work order models (from now on called WOM) The WOMs share some attributes (Num, Date, Description, ... etc) The WOMs ...
2
votes
0answers
396 views

HackerRank university codesprint array construction

Problem statement Professor GukiZ has hobby — constructing different arrays. His best student, Nenad, gave him the following task that he just can't manage to solve: Construct an \$n\$-...
2
votes
0answers
540 views

JSON schema visualizer

I have the following backbone function to read a JSON schema and draw the tree structure (as in the screenshot below). I want to make sure if checking against the type as object/array is alright or if ...
2
votes
0answers
513 views

Recursive implementation of integer partition without re-arrangement

Problem: Integer partition without re-arrangement Input: An arrangement S of nonnegative numbers {s1, . . . , sn} and an integer ...
2
votes
0answers
48 views

Recursively merge objects with corresponding property names

I have such objects that I need to merge: ...
2
votes
0answers
101 views

Parallel Multiplier: an implementation of `RecursiveTask<V>`

This class is my attempt at creating a re-usable class that simplifies the parallel calculation of products. I would appreciate hints on all aspects especially the value of the threshold for which the ...
2
votes
0answers
239 views

Using recursion schemes to avoid explicit corecursive unfolding

The code is self-contained and self-explaining. I want to improve the goal function. You can change everything below the ...
1
vote
0answers
139 views

Bin-packing-problem solution using recursion

I needed to make a freight calculator and had to solve a bin packing problem. I utilized a github package. Basically with the help of my stack overflow question I made a class Method that Splits an ...
1
vote
0answers
461 views

Recursive object/array filter by key

I have some code that takes some JSON, parses it, and given an optional filter, will attempt to find any key (or nested key) that includes the filter (partial matching - it does not match values). The ...
1
vote
0answers
332 views

Filling values for nested dictionaries

I have a text file where any name followed with sequence word is considered a dictionary. The task is to go through the keys and values of a particular dictionary, which is already identified, and see ...
1
vote
0answers
36 views

Own implementation of Euclid sub algorithm in Lisp

...
1
vote
0answers
578 views

Sudoku solver using NumPy

I come from the R language and I gradually switch to Python (Numpy and Pandas). I coded this python code for fun to solve a Sudoku grid. Could you tell me if my code is pythonic enough? For example, ...
1
vote
0answers
74 views

Recursive Generator Exceeds Call Stack

I have this recursive generator that fetches 100 messages from an API and gets the next 100 until there are no more messages to get: ...