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.
1,138
questions
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 ...
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:
...
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 ...
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
...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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?
...
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
...
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 ...
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 ...
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 ...
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, ...
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 ...
12
votes
6
answers
4k
views
Python 3 - Fibonacci Implementation
I wrote a function returning the n-th Fibonacci number in Python 3:
...
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 ?
...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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\$ ...
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 ...
4
votes
1
answer
5k
views
Find maximum number in a nested array using recursion
Here is my code:
...
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 ...
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 ...
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.
...
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:
...
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 ...
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 ...
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 ...
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 ...
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?
<...
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 ...
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 ...
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 ...
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 ...
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}...
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 ...
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 ...
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? ...
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 <...