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.
3
votes
2answers
273 views
Insert a number in a sorted list and return the list with the number at the correct index
I feel like the title is a bit wordy. What I have defined here is a function that takes two parameters:
a list that contains valued sorted from smallest to biggest
a number to insert at the right ...
3
votes
1answer
54 views
Pouring water between two jugs to get a certain amount in one of the jugs (2)
I have been practicing recursion lately and I came up with this code to solve the water jug problem, given two jugs of volume jug1 and ...
5
votes
3answers
198 views
Picking the smallest value in a list using recursion
This is the code I wrote in order to find the smallest value in a list using recursion.However I feel like there would be a better way to do this?
...
-5
votes
0answers
34 views
Scala sorting comparator [on hold]
I'm following this tutorial on functional programming in Scala.
Exercise 2.2 features a sorting algorithm which takes an array, and a sorting function, and returns true or false if the array is ...
1
vote
1answer
42 views
Check if list contains a pair which adds up to a given sum
Kindly review this scala code for given problem and suggest improvements.
Problem - Given an array of integers and a target sum, check if array contains a pair which adds up to sum.
Example -
<...
3
votes
3answers
181 views
Password generator with multiple charset
This is just straight bruteforce with the ability to select multiple character sets for one word.
[Edit] I switched back to c on https://github.com/e2002e/zhou, and fixed the special algorithm; ...
-1
votes
2answers
65 views
Fibonacci Nth term using tail recursion [closed]
I have created a program that prints the Nth term of the Fibonacci sequence. The fib function needs to use tail recursion. If what I have coded isn't tail recursion, I would like to know how to change ...
3
votes
2answers
103 views
Simple recursive transformation solution in Python
This simple Python code I wrote for a problem asked during an interview. The problem statement is:
Given a tuple (a, b), transform this into (c, d) by applying any of the two below operations ...
0
votes
0answers
74 views
Better way to do Matrix Multiplication using fork and join
I have this assignment to employ what I have learnt about fork and join. I have heard some rumours that it is possible to achieve a 60x optimisation to this problem. However, I have only managed to ...
2
votes
0answers
29 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
4answers
81 views
K&R Exercise 1-19. Reverse program input one line at a time
Intro
I'm going through the K&R book (2nd edition, ANSI C ver.) and want to get the most from it: learn (outdated) C and practice problem-solving at the same time. For that reason, I'm trying to ...
2
votes
2answers
60 views
Collect members from custom tree nodes
In my program, I have a tree of Group nodes, each identified by their ImportId.
Each group has zero or more members, that I ...
12
votes
2answers
2k views
Tower of Hanoi Recursive Implementation using Python with OOP
I have just finished a small program for Tower of Hanoi using recursion. I did it to practice OOP which I recently learnt. It took me about 2 hours to research about the recursive algorithm and write ...
1
vote
1answer
63 views
C++ heap CPS: Continuation Passing Style with Recursion
I am willing to see how to write readable and efficient continuations on the heap in c++. I am not quite satisfied.
The following is just an exercise: it is coded for fun. I post the code here ...
6
votes
1answer
186 views
Tower of Hanoi in NASM Win64 Assembly
This program is an implementation of the classic puzzle Tower of Hanoi! This is my first mostly recursive Assembly program. Any advice and all topical comments on code optimization and conventions is ...
1
vote
0answers
43 views
Recursive object/array filter by key
I have some code that takes some JSON, parses it, and given an optional filter, will attempt to find any key (or nested key) that includes the filter (partial matching - it does not match values). The ...
4
votes
1answer
60 views
Recursive Fibonacci in Rust with memoization
I'm trying to come up with an "elegant" way of calculating Fibonacci for number in Rust, using recursion and memoization (self-imposed requirements).
This is what I have so far:
...
1
vote
2answers
57 views
When given 7 letters, find all possible words with length 3 to 7
I am writing a program in JavaScript to find all possible words given 7 letters. The words have to be 3 or more characters, and for right now I am limiting it to 7 characters long. The code below ...
1
vote
1answer
36 views
Scheme function to duplicate every element of a list a specified number of times
This code takes a list and a integer and duplicates every element in the list the specified number of times.
...
5
votes
2answers
141 views
Finding all possible letter combinations from an inputted phone number
Prompt:
Given a string containing digits from 2-9 inclusive, return all
possible letter combinations that the number could represent.
A mapping of digit to letters (just like on the ...
3
votes
1answer
134 views
Find the kth-to-last element of a singly linked list
I wrote this code for finding the \$k\$th-to-last element in a singly linked list.
...
1
vote
0answers
182 views
Filling values for nested dictionaries
I have a text file where any name followed with sequence word is considered a dictionary. The task is to go through the keys and values of a particular dictionary, which is already identified, and see ...
1
vote
2answers
25 views
Extract and divide algorithm implementation in Elixir
I just started learning Elixir and stumbled upon this challenge over on Programming Puzzles & Code Golf. It is a well-suited task for beginners, so I chose to give it a go (to be clear, give it a ...
1
vote
1answer
51 views
Rearrange an array in place such that the first and last halves are interleaved
Given an array of n elements in the following format { a1, a2, a3, a4,
….., an/2, b1, b2, b3, b4, …., bn/2 }. The task is shuffle the array
to {a1, b1, a2, b2, a3, b3, ……, an/2, bn/2 } without ...
3
votes
0answers
83 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 ...
2
votes
2answers
87 views
NxN Sudoku Solver
I have written a Sudoku solver which can solve arbitrary NxN grids via backtracking.
Since I'm relativly new to C any feedback is welcome.
Code:
...
4
votes
3answers
691 views
Recursion: Count from x until n and backwards
I wrote this recursive function to print a number sequence from x to n and n to x back.
Here is one of the ideas I had to improve it, but it didn't work out (use another ternary operator at the end ...
1
vote
1answer
49 views
Recursive function to find the number of ways a number can be generated out of a set of numbers
I had a job interview test and the question I got was about making a function which would return the number of ways a number could be generated by adding numbers from a certain set, where any number ...
1
vote
1answer
124 views
Count number of islands 2d grid
This is a recursive approach using DFS to counting the number of islands. However, I would like to improve performance, while keeping the code clean concise and readable. Better yet can this be solved ...
1
vote
0answers
26 views
0
votes
0answers
36 views
Is this a good way of retrying operations using recursion?
This is in context of a springboot application. I considered using Spring @Retryable too but found that it didn't work with function with return types. Is this approach considered good?
...
1
vote
0answers
25 views
Searching through a TreeView by expanding found results and collapsing others [closed]
I have a WPF TreeView which is populated with many child controls. All of them with children themselves are ...
4
votes
1answer
204 views
Recursive implementation of power set in Python
I was doing a recursion problem called power set, and would like to get code review. Here's the problem.
...
3
votes
1answer
78 views
Recursively generating the look-and-say sequence
I have a pattern where every number is counted by the number of repetitions. A new resulting number is formed by adding that repetition to the front of that value. The resulting pattern would look ...
3
votes
3answers
233 views
Find k-distinct partitions which contain at least two perfect squares
Problem Statement:
A k-distinct-partition of a number \$n\$ is a set of \$k\$ distinct positive integers that add up to \$n\$. For example, the 3-distinct partitions of 10 are
\$1+2+7\$
\$...
2
votes
0answers
32 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
...
1
vote
0answers
102 views
Sudoku solver using NumPy
I come from the R language and I gradually switch to Python (Numpy and Pandas). I coded this python code for fun to solve a Sudoku grid. Could you tell me if my code is pythonic enough? For example, ...
5
votes
0answers
197 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 ...
2
votes
2answers
72 views
Finding the closest pair of points divide-and-conquer speed improvement
This is a follow up to a previously asked Finding the closest pair of points divide-and-conquer question . The original code changed significantly based on answers from @AJNeufeld therefore I created ...
0
votes
1answer
72 views
Counting contiguous subarrays with a negative sum
I'm doing a coding challenge that asks to count the number of contiguous subarrays that have a negative sum:
A subarray of an n-element array is an array composed from a contiguous block of the ...
4
votes
2answers
572 views
Finding the closest pair of points divide-and-conquer
Here is my code for the famous "finding the closest pair of points" problem from CLRS book section 33.4 using a divide-and-conquer approach (this code returns the minimum distance between pair of ...
6
votes
2answers
178 views
Find the second largest number in an array with at most n + log2 n - 2 comparisons
This exercise is from Roughgarden's (excellent) course on algorithms on Coursera:
You are given as input an unsorted array of n distinct numbers, where
n is a power of 2. Give an algorithm that ...
1
vote
1answer
51 views
Possible letter combinations of a dial pad in linear time using a recursive approach
Time complexity: I walk the initial unzipped array of keys representing the number O(N) backwards. I then do an inner walk of the proceeding array of letters *O(L^2), mapping it to every value in the ...
3
votes
2answers
112 views
Memoized solution to Count number of ways to climb n steps
Problem statement : A Child is climbing up n steps with either 1 , 2, 3 hops ..how many ways can the child climb up the stairs?
source: cracking the coding interview book.
I have two solutions the ...
1
vote
1answer
405 views
All subsets of a String in java using recursion
I wrote this code for printing all sets of a String. It also prints the empty subset. Is this the right approach
...
1
vote
2answers
158 views
Find all N-Queens solution
This code is a multi-threading recursive backtracking DFS algorithm to find all solutions to the N-Queens problem. The board size is indicated by BOARD_SIZE. ...
1
vote
0answers
32 views
Recursive Generator Exceeds Call Stack
I have this recursive generator that fetches 100 messages from an API and gets the next 100 until there are no more messages to get:
...
1
vote
4answers
104 views
Hackerrank Day 9: Recursion
Write a factorial function that takes a positive integer, N as a parameter and prints the result of N! (N factorial).
Note: If you fail to use recursion or fail to name your recursive function ...
2
votes
1answer
76 views
Determine all ways a string can be split into valid words, given a dictionary of all words
This function word_break(s, dictionary) receives a string s and a set of all valid words ...
1
vote
2answers
139 views
Find all root to leaf paths in binary tree
Description:
Given a binary tree, return all root-to-leaf paths.
Leetcode
...
