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.

81 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
18
votes
0answers
271 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
712 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
139 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
736 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 ...
6
votes
0answers
415 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
199 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
377 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
244 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 ...
5
votes
0answers
157 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
85 views

This recursive function encrypts a string

Is there a way to rewrite these last 2 recursive functions with fewer arguments (preferably 2) while keeping them recursive? The entire code can be seen here: https://github.com/GirkovArpa/hutton-...
4
votes
0answers
109 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
994 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
136 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 ...
4
votes
0answers
383 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 ...
4
votes
0answers
246 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 ...
3
votes
0answers
23 views

Approximation search source reconstruction localization algorithm

Goal To determine the coordinates of some signal source in a 3D space, given the coordinates of four observers and the time at which each saw the signal, as well as the velocity of the signal. ...
3
votes
0answers
78 views

A valid Sudoku Generator without backtracking in JavaScript

I am new to programming. I tried to write a valid Sudoku solver with backtracking, the performance is disappointing. So, I tried to generate a valid Sudoku generator without backtracking. The white ...
3
votes
0answers
33 views

Noughts and Crosses Terminal Game with AI

I created a game which can play tic-tac-toe with: 0 players (AI vs AI), 1 player (human vs AI) or 2 player (human vs human). Here is the AI function which wraps around my innermost function. This ...
3
votes
0answers
62 views

Simulating the orbits of the Earth, Moon and Sun together in Fortran

This has been racking my brain for hours now. I will try to explain as much as I can. I'm aware this code is horrendously ungraceful, but I'm new to Fortran and making things more efficient is not ...
3
votes
0answers
122 views

N-Queens Puzzle

The N-Queens puzzle can be solved in many ways. One is by a depth-first-search backtracking algorithm. Below is my generalized version using mutual recursion: ...
3
votes
0answers
127 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 ...
3
votes
0answers
70 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
125 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
0answers
46 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
344 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
159 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
100 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
65 views

Enabling parents and dependencies of selected items recursively

I have a class Feature as such: ...
3
votes
0answers
605 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 ...
3
votes
0answers
526 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
341 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
268 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
475 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
48 views

Linked tree built from (n) leaves

Firstly, here is the relevant code. It is written in kotlin. ...
2
votes
0answers
150 views

generic implementation approaches for a recursive function

Let's take the famous fibonacci problem as an example but this is a generic problem. Also, taking scala as the language as it's rather feature-rich. I want to know which solution you'd prefer. we all ...
2
votes
0answers
57 views

Kadanes algorithm implementation

I just wanted to ask the following question. I have solved Kadanes algorithm using the recursive approach as shown below. The implementation works ...
2
votes
0answers
28 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
48 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
36 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
40 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
986 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
0answers
275 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
450 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
543 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
106 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
321 views

Find the most efficient combination that equals target number in ArrayList

I want to implement the following function: Given a target sum, return the combination that equals the target sum and is the most efficiënt combination in the array of an ...
1
vote
0answers
40 views

Tree kind of Object. Adding and Removing children

I am trying to work with a list of Person objects where the Person object has a property called "children" which is an array of same type. I idea is to have methods called “addChildrenToMain”...