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.

Filter by
Sorted by
Tagged with
7 votes
1 answer
63 views

Apply arbitrary action during recursive generator function

I've got this recursive generator function. It will traverse an object looking for "leafs", any keys that don't point to sub-objects. Then it applies one of two actions on the leaf and yields it. Any ...
Letharion's user avatar
  • 618
2 votes
1 answer
230 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: ...
Fahd Ahmed's user avatar
2 votes
1 answer
63 views

Make a given number by adding given numbers

I have created a code that checks if a number can be made by adding different quantities of given numbers and if so returns the quantities. Is this the best way to do this or is there a more efficient ...
Anonymous Coder's user avatar
3 votes
1 answer
116 views

Recursion memorization table

The following code is for this problem. Input The input consists of a single line with three integers n , s , and k (1 ≤ n ≤ 10,000, 1≤ k ≤ s ≤ 500 ). n is the number of throws, k ...
Andy's user avatar
  • 33
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
0 votes
1 answer
92 views

Maze maker for game using recursive method

I wold like some feedback on this mazefactory, it creatse a maze in a 2D array starting in the middle (the treasure room) and creating new rooms until it reaches the outside of the maze. The maze is ...
Erkki's user avatar
  • 73
6 votes
3 answers
728 views

Recursive function challenge

Problem statement Given a list of float numbers, and four operators +, -, *, / with flat preference, find the maximum value by inserting operator between each consecutive pair of numbers. For ...
Jianmin Chen's user avatar
  • 2,396
1 vote
4 answers
2k views

Improving Fibonacci recursion with BigIntegers

I've been tasked with making a fast Fibonacci recursive method that uses BigInteger to calculate REALLY big numbers. However, to calculate numbers past 30 it takes ...
Ozymandias's user avatar
4 votes
1 answer
993 views

Recursive grid traveling algorithm

I'm trying to come up with a solution to a coding challenge on Kattis, where there is a 2D grid filled with x's and o's, and the goal is to figure out whether or not a given starting coordinate can ...
Archie Gertsman's user avatar
3 votes
3 answers
2k views

Tower Hopper problem recursive approach

The Tower Hopper problem gives us an array of values representing heights that express how far we can jump from a certain tower, and asks whether there's a way to get from ...
jeremy radcliff's user avatar
1 vote
1 answer
459 views

Recursive matrix multiplication

I've just written a recursive matrix multiplication and I want to know my mistakes or problems. Is there a better way doing this? ...
KooKoo's user avatar
  • 235
0 votes
1 answer
452 views

Maximum sub array sum equal to k

Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k. For example: Input: nums = [1,1,1], k = 2 Output: 2 ...
MrKickass's user avatar
1 vote
1 answer
475 views

Reinterpreting a string, treating < as a backspace character

I've come up with a solution to this coding challenge using recursion. In summary, the input is a string where the < symbol represents a backspace (up to 1 ...
Archie Gertsman's user avatar
3 votes
1 answer
232 views

Advent of Code 2017, Day 7 - Recursive Circus

This is my solution to Advent of Code 2017, Day 7 – Recursive Circus (both parts, you might not be able to see the second part unless you're logged in and solved the first part, but I'll summarize it ...
mkrieger1's user avatar
  • 1,694
2 votes
3 answers
102 views

Program that should output nth arrangement of paintings

I'm currently practicing for the British informatics olympiad by doing past papers. I'm on question 3 of the 2015 paper and trying to use recursion to solve it. I'm pretty new to using recursion but ...
Jordan Bates's user avatar
8 votes
1 answer
155 views

AoC Day 24 2017: Electromagnetic Moat

This year's AoC has a puzzle for day 24 that was (supposedly) intended to be solved with recursion. Here is the description: --- Day 24: Electromagnetic Moat --- The CPU itself is a large, ...
Digika's user avatar
  • 113
8 votes
1 answer
2k views

Fibonacci in linear time by using an extra pointer

I have a function to find the nth number in a Fibonacci sequence, in which I am recursively calling the function. The sum is stored in a class variable and I have an extra pointer I increment every ...
paddy's user avatar
  • 83
12 votes
6 answers
4k views

Python 3 - Fibonacci Implementation

I wrote a function returning the n-th Fibonacci number in Python 3: ...
user7802048's user avatar
7 votes
1 answer
942 views

Finding Second Largest Element in an Array

Here's my implementation using divide and conquer in C++. What do you think of this implementation regarding running time ? ...
Ahmed Karaman's user avatar
10 votes
6 answers
11k views

Base 26 (letters) and Base 10 using recursion

I was messing around with base conversion between decimal and Base26 (alphabet) with no 0th case because I needed it for the Google Sheets API in order to find specific cell values from a 3 ...
WCTech's user avatar
  • 103
1 vote
1 answer
1k views

Recursive quicksort in Python

I want to find a more elegant way to build a recursive sorting function. The function randomly selects one of the numbers from a given list, k, and splits the list ...
user avatar
12 votes
1 answer
210 views

Solving alethic modal logic formulas using truth trees

Disclaimer: this first section is about alethic modal logic and truth trees. It's important to the question but significant parts of the code can probably be reviewed without it. You're welcome to ...
overactor's user avatar
  • 654
3 votes
1 answer
6k views

Recursive BFS solution for tree traversal

I'm somewhat new to the wonderful world of Python, outside of simple codecademy-like challenges online. This function was part of a project for school. It's tested and works, but I'm looking for some ...
wanderbread's user avatar
0 votes
1 answer
179 views

Ruby Linked List implementation

I've made a Ruby linked list data structure class and a lookup method. I know that lookup will only fetch the first occurrence ...
vinibrsl's user avatar
  • 647
3 votes
2 answers
279 views

Segementing a recursive tree in haskell

Could somebody help me work out how to abstract the recursion from this code for me please? I'm trying to write something that takes a pandoc structure, and subdivides the tree whenever it finds a ...
danbroooks's user avatar
8 votes
7 answers
1k views

Function to build a string based on the recursion depth

I was doing a JavaScript challenge to test myself and I succeeded in finding a solution but the code is very ugly. I was hoping to get some opinions on what a better solution would look like. The ...
Sachin Kainth's user avatar
7 votes
1 answer
200 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. This is useful for ...
Lux's user avatar
  • 171
1 vote
0 answers
985 views

C# MVC Generic Custom Model Binder

I recently created a custom model binder as a training exercise and wanted to see how I could improve it. It currently uses recursion and works great, but I was wondering how I could convert this to ...
MattyMc's user avatar
  • 33
3 votes
2 answers
2k views

Python - Knight's tour recursive function [closed]

I realize that there're many implementations of Knight's tour problem suggested across webs, without jumping to those suggested solutions (most in Java, I'm not proficient in Java), I managed to ...
Logan's user avatar
  • 291
3 votes
1 answer
425 views

Find the maximum possible summation of differences of consecutive elements

Array A contains the elements, \$A_1,A_2, \ldots, A_N\$. And array B contains the elements, \$B_1,B_2, \ldots, B_N\$. There is a relationship between \$A_i\$ and \$B_i\$: any element \$A_i\$ ...
kumarmo2's user avatar
  • 271
1 vote
2 answers
205 views

Binary Tree Maximum Turns

Given any binary tree, what is the maximum number of turns possible in any path from root to any leaf? A turn is when the path involves moving from left branch to right or vice-versa; i.e. the number ...
modeeb's user avatar
  • 156
4 votes
1 answer
5k views

Find maximum number in a nested array using recursion

Here is my code: ...
CppLearner's user avatar
2 votes
1 answer
89 views

dynamic programming solution for a string ending with 0, 1 or 2

A string that contains only 0s, 1s, and 2s is called a ternary string. Find a total ternary ...
noman pouigt's user avatar
3 votes
1 answer
98 views

Recursion function subtracting accumulated percentage with <<-

I have a file with percentage of presence of micro-organisms but each category has the accumulation of percentages of the child categories. I designed a recursive function to subtract the proportion ...
llrs's user avatar
  • 273
2 votes
1 answer
5k views

Searching JSON recursively for an item with a "selected" attribute

I have the following function, which I believe could be improved with functional-programming. ...
Sarawut Positwinyu's user avatar
3 votes
1 answer
62 views

Generating a list of powers in Elm up to some limit

I'm looking to generate a list of powers in Elm, up to a certain limit. I've written the following tests: ...
Ray Toal's user avatar
  • 765
0 votes
2 answers
552 views

Print every line of file, last to first, with recursion

Had a discussion with a friend to solve this extra credit problem, and we came up with two separate solutions. What are the differences between these two? Is one better than the other? How can I make ...
cody.codes's user avatar
  • 1,935
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
12 votes
1 answer
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 ...
Nikolay Derkach's user avatar
2 votes
1 answer
2k views

Given a binary tree, find the maximum path sum

This is a leetcode.com problem. For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must ...
Stack crashed's user avatar
2 votes
1 answer
9k views

Computing the powerset of a list

I've written the following code for computing the powerset of a list (we consider the list has all distinct elements, although it doesn't really matter). Can this function be further optimized? <...
Hisoka Moroh's user avatar
10 votes
4 answers
11k views

Format an integer with thousands separator (recursive implementation)

The function accepts a number n and displays it recursively with commas. As well as a general code review, I'm interested in suggestions for alternatives to ...
Nick Pavini's user avatar
2 votes
3 answers
17k views

Generate all permutations of a list in Python

This is my solution to the "Permutations" problem from Leetcode: Given a collection of distinct numbers, return all possible permutations. I know this is a common routine that can be done much ...
grayQuant's user avatar
  • 232
10 votes
2 answers
3k views

xml is XML is xml is XML

I had to write some code for an interview, to print out the name attribute of each node. I started off going in the wrong direction, so I didn't get to finish. I wanted to finish writing the code, so ...
Malachi's user avatar
  • 28.6k
3 votes
2 answers
604 views

Finding the nth Fibonacci number using recursive technique

EDIT So I've been working on this according to the challenge @PeterTaylor gave me. I'm not very good at math, so I've been doing a lot of reading and found this link on the Binet form. Fibonacci ...
Nathan's user avatar
  • 165
3 votes
2 answers
1k views

Algorithm that generate all possible strings from N Tuples. Found Brute Force version, Recursive Version uses a Tree?

I am trying to figure out a solution for a problem. Consider the following tuples (it could be any number of tuples, I am using four in this example): {A, B, C, D}...
Frankg26's user avatar
  • 105
5 votes
1 answer
581 views

Compute all valid configuration of eight queens on a 8x8 chess board

Write an algorithm to print all valid ways of arranging eight queens on an 8x8 chess board so that none of them attack any other. Following is my code for this. Do you see any performance or coding ...
Stack crashed's user avatar
1 vote
1 answer
832 views

Compute the number of ways a given amount (cents) can be changed

Given an infinite number of different coin types (such as pennies, nickels, dimes, quarters) find out how many ways n cents can be represented. My code appears to work (although I am curious to ...
Stack crashed's user avatar
10 votes
2 answers
4k views

Generate all valid combinations of n pair of parentheses

Implement an algorithm to print all valid (e.g. properly opened and closed) combinations of n pair of parentheses. Following is my implementation and I think it works. Is the algorithm efficient? ...
Stack crashed's user avatar
5 votes
1 answer
444 views

Haskell limit number of recursions

I want to create a monad which will prevent more than 10 instances of recursion (which I am implementing by preventing more than 10 instances of >>=). My <...
Xodarap's user avatar
  • 153

1
8 9
10
11 12
23