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

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.

85 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
23 votes
0 answers
611 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 (...
Sep Roland's user avatar
  • 4,438
9 votes
0 answers
1k views

Tree for PowerShell

For anyone reading this old question, this module has evolved and improved a lot since then. It has been fully rewritten in C# and uploaded to the PowerShell Gallery! If you would like to try it out: <...
Santiago Squarzon's user avatar
9 votes
1 answer
1k 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 ...
Programmer's user avatar
7 votes
0 answers
155 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 ...
Guillermo Subiran's user avatar
6 votes
0 answers
1k 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 ...
Joelius's user avatar
  • 355
6 votes
0 answers
446 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....
Xīcò's user avatar
  • 161
5 votes
0 answers
152 views

Hutton cipher implemented using recursive functions

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-...
GirkovArpa's user avatar
5 votes
0 answers
1k 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 ...
Joey Hunt's user avatar
5 votes
0 answers
176 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: ...
Tomáš Hübelbauer's user avatar
4 votes
0 answers
148 views

Find the longest "common sequence" in two lists

In short, the algorithm must find the longest sequence that joins together common sequences from two lists (a more formal specification is given in the code's header). The lists are assumed to contain ...
user266319's user avatar
4 votes
0 answers
125 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 ...
Chocolate's user avatar
  • 948
4 votes
0 answers
133 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 ...
Rick's user avatar
  • 586
4 votes
0 answers
2k 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 ...
nodakai's user avatar
  • 141
4 votes
0 answers
197 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 ...
Yulan van Oppen's user avatar
4 votes
0 answers
490 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 ...
Pankaj Jaju's user avatar
4 votes
0 answers
274 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 ...
nponeccop's user avatar
  • 1,084
3 votes
0 answers
149 views

Finding the number of possible paths in a cave system (Python)

I've finally come up with working solution for day 12 of AdventOfCode, where you have to find the number of possible paths in a cave system following a given set of rules (described below). My ...
Oleg Shevchenko's user avatar
3 votes
0 answers
292 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" ...
David542's user avatar
  • 409
3 votes
0 answers
309 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 ...
Gilad's user avatar
  • 5,311
3 votes
0 answers
66 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 ...
JimmyHu's user avatar
  • 5,020
3 votes
0 answers
159 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, ...
JimmyHu's user avatar
  • 5,020
3 votes
0 answers
148 views

A recursive_print Function For Various Type Arbitrary Nested Iterable Implementation in C++

This is a follow-up question for A recursive_transform for std::vector with various return type and A recursive_transform for std::array with various return type. Based on these discussion about the ...
JimmyHu's user avatar
  • 5,020
3 votes
0 answers
237 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 ...
Jason Rich Darmawan's user avatar
3 votes
0 answers
286 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 ...
RelativelyUnique's user avatar
3 votes
0 answers
174 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: ...
user avatar
3 votes
0 answers
200 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 ...
Alfredo's user avatar
  • 31
3 votes
0 answers
327 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 ...
Juneyoung Oh's user avatar
3 votes
0 answers
399 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 ...
NinjaG's user avatar
  • 2,469
3 votes
0 answers
53 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 ...
Jacob Regan's user avatar
3 votes
0 answers
2k 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 <...
Igor Soloydenko's user avatar
3 votes
0 answers
440 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? <...
Eli's user avatar
  • 31
3 votes
0 answers
313 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 ...
user avatar
3 votes
0 answers
71 views

Enabling parents and dependencies of selected items recursively

I have a class Feature as such: ...
cogumel0's user avatar
  • 181
3 votes
0 answers
729 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 ...
SachiDangalla's user avatar
3 votes
0 answers
564 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, ...
1252748's user avatar
  • 187
3 votes
0 answers
410 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 ...
Slyvain's user avatar
  • 131
3 votes
0 answers
301 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 ...
Sagar D's user avatar
  • 31
3 votes
1 answer
571 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 ...
jotadepicas's user avatar
2 votes
0 answers
45 views

A recursive_fold_right_all Template Function Implementation in C++

This is a follow-up question for A recursive_fold_left_all Template Function Implementation in C++. Besides recursive_fold_left_all function, I am trying to ...
JimmyHu's user avatar
  • 5,020
2 votes
0 answers
53 views

A recursive_depth Function Implementation with Target Type Parameter in C++

This is a follow-up question for A recursive_depth function for calculating depth of nested types implementation in C++. I am rethinking about the proposed ...
JimmyHu's user avatar
  • 5,020
2 votes
0 answers
63 views

Recursive path drawing in Latex

I have some diagrams I'm drawing using tikz and I'd like to make a macro to draw them for me. I will describe it fully but here are some examples so you can follow along: The diagram has a number of ...
Sriotchilism O'Zaic's user avatar
2 votes
0 answers
55 views

Linked tree built from (n) leaves

Firstly, here is the relevant code. It is written in kotlin. ...
Emery Tanghanwaye's user avatar
2 votes
0 answers
187 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 ...
Maths noob's user avatar
2 votes
0 answers
87 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 ...
log N's user avatar
  • 121
2 votes
0 answers
47 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/...
Joelius's user avatar
  • 355
2 votes
0 answers
99 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 ...
KshitijV97's user avatar
2 votes
0 answers
94 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 ...
HoneyBadger's user avatar
2 votes
0 answers
50 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 ...
Eric's user avatar
  • 181
2 votes
0 answers
368 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 ...
Philipp Doerner's user avatar
2 votes
0 answers
2k 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 ...
Matt's user avatar
  • 339