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.

101 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
21
votes
0answers
385 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
842 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
1k 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 ...
7
votes
0answers
144 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
726 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 ...
6
votes
0answers
425 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
563 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
168 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
63 views

Word finder using pygame

I made a word searching app that allows the user to inout words into a text box, and parts of the word grid will be highlighted to show the location of the words. The letters of the grid can be edited ...
4
votes
1answer
57 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. ...
4
votes
0answers
96 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
114 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
1k 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
146 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
157 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 ...
4
votes
0answers
432 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
258 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
25 views

Recursively Copy Dotfiles from Git Repo to New System's Home Directory

I manage my dotfiles in a github repo. The idea would be that I could clone the repo if I ever have to develop on a new system and symlink them to the home ...
3
votes
0answers
43 views

Order guaranteed recursive_transform template function implementation with execution policy in C++

This is a follow-up question for A recursive_transform Template Function with Execution Policy, A recursive_transform Template Function Implementation with std::invocable Concept and Execution Policy ...
3
votes
0answers
65 views

Lisp expression parser

I'm building a very simple Lisp interpreter. Similar to the the one from here. Here is what I have so far for the parsing part, that is, everything from "text is passed to the the program" ...
3
votes
0answers
89 views

A recursive_transform Template Function with Unwrap Level for Various Type Arbitrary Nested Iterable Implementation in C++

This is a follow-up question for A recursive_transform Template Function Implementation with std::invocable concept in C++ and A recursive_transform Template Function Implementation with ...
3
votes
0answers
216 views

LeetCode: Stone Game C#

https://leetcode.com/problems/stone-game/ Alex and Lee play a game with piles of stones. There are an even number of piles arranged in a row, and each pile has a positive integer number of stones ...
3
votes
0answers
90 views

An Add/Minus Operator For Boost.MultiArray in C++

This is a follow-up question for An element_wise_add Function For Boost.MultiArray in C++. The following code is the improved version based on G. Sliepen's answer. On the other hand, the built-in ...
3
votes
0answers
126 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
157 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
103 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
144 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
179 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
230 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
217 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
1k 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 <...
3
votes
0answers
382 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
211 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
66 views

Enabling parents and dependencies of selected items recursively

I have a class Feature as such: ...
3
votes
0answers
635 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
539 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
354 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
284 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
523 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
51 views

Tree for PowerShell

This Module started as a fun coding exercise designed to emulate the tree command and also calculate the size of each folder based of the files size of that folder (...
2
votes
0answers
57 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 ...
2
votes
0answers
90 views

An element_wise_multiplication and an element_wise_division Function For Boost.MultiArray in C++

This is a follow-up question for An element_wise_add Function For Boost.MultiArray in C++ and An Add/Minus Operator For Boost.MultiArray in C++. Besides the basic element-wise add / minus operations, ...
2
votes
0answers
53 views

Linked tree built from (n) leaves

Firstly, here is the relevant code. It is written in kotlin. ...
2
votes
0answers
172 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
62 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
36 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
67 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
41 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
44 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 ...