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,073
questions
40
votes
4answers
7k views
Rainfall challenge
About a year ago when I was applying to jobs for the first time, I had an interview at a company and they posed the following problem to me, which I preceded to bomb.
A year later I actually came up ...
30
votes
3answers
82k views
Find all subsets of an int array whose sums equal a given target
I am trying to implement a function below:
Given a target sum, populate all subsets, whose sum is equal to the target sum, from an int array.
For example:
...
29
votes
2answers
62k views
Recursion vs iteration of tree structure
Some recursive code is part of a particularly slow path of a project. Out of curiosity I was playing around with reimplementing the code using stack context iteration instead of recursion. Below are ...
28
votes
4answers
15k views
Repeatedly multiplying digits until a single digit is obtained
I've written code that solves a problem from codewars.com. My code passes all the tests on the codewars site. It's a simple enough problem to solve naïvely, but I would love to improve the structure.
...
27
votes
2answers
3k views
Sudoku using 'exact cover' solver
1. Introduction
This is a solution to Weekend Challenge #3: a Sudoku solver in Python. It works by translating a Sudoku puzzle into an exact cover problem, and then solving the exact cover problem ...
21
votes
4answers
24k views
Any way to make this recursive function better/faster?
Is there anything that can be done differently for this function? Any way to make it faster?
...
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 (...
20
votes
4answers
6k views
Print the Twelve Days of Christmas without loops or conditionals
For my AP Computer Science class, I am required to write a program that prints the Twelve Days of Christmas without loops or conditionals using static methods.
...
20
votes
3answers
4k views
Loading military units into ships optimally, using backtracking
I solved the following problem using backtracking:
We are given a list of military units, their weight and their
(numerical) strength. We have a number of ships with a limited
carrying capacity....
19
votes
4answers
31k views
Displaying each number of an integer in a sequence
One of the books I'm currently reading to learn C# asked me to write a method that takes an integer between 1 and 99999 and displays each number in that integer in a sequence, separating each digit by ...
18
votes
2answers
4k views
Simple recursive Sudoku solver
My Sudoku solver is fast enough and good with small data (4*4 and 9*9 Sudoku). But with a 16*16 board it takes too long and doesn't solve 25*25 Sudoku at all. How can I improve my program in order to ...
17
votes
4answers
2k views
Recursive and iterative Euclidean algorithms
Is this code too cryptic? Simple yes or no question. Feedback is optional.
...
17
votes
4answers
55k views
Get value from dictionary given a list of nested keys
I would like to get a deeply-nested value, for example {"a":{"b":{"c":"myValue"}} by providing the keys to traverse. I tried chaining together .get() but that didn'...
17
votes
3answers
4k views
Knapsack branch and bound: forward filter
I've coded branch and bound to solve the knapsack problem, and use a greedy linear relaxation to find an upper bound on a node I'm currently exploring. What I mean by this is that I first sort the ...
17
votes
2answers
2k views
A KenKen puzzle/solver in Python
I've written a simple KenKen puzzle/solver in Python. I'd love some feedback on the design of the puzzle, as well as the architecture for the solver.
To model the puzzle, I have the following classes:...
15
votes
3answers
3k views
Project Euler Problem #8: Largest product in a series
The four adjacent digits in the 1000-digit number that have the greatest product are 9 × 9 × 8 × 9 = 5832.
...
15
votes
3answers
3k views
N-Queens - Brute force - bit by bit
A discussion in The 2nd Monitor made me realize I had never 'solved' the N-Queens problem. Additionally, as I read up on it, I realized that the 64-squares in a chess board would work well if ...
15
votes
2answers
326 views
My recursive parser is wet behind the ears (well, it's not DRY at least)
I have an issue opened on GitHub since mid-November, to refactor & DRY up the Rubberduck Parser module (the idea is to model the code in a VBA project or code ...
14
votes
6answers
5k views
Identifying first negative number in array of doubles
I was asked to create a function that checks if an array of doubles has all negative numbers or none. If these 2 (all negative, all positive) are false, check the ...
14
votes
1answer
4k views
Sudoku Week-End Challenge - Brute-Force Recursive solver
This is part of my attempt at the Week-End Challenge #3. The overall problem is larger than will fit in one question. This is a well-contained subset of my larger program.
The goal of this part is to ...
13
votes
5answers
5k views
Simple Fibonacci using recursion
The sole purpose of this post is to see how a production quality developer would approach this very simple problem. I am a fresh graduate and do not have a professional development experience. What ...
13
votes
3answers
38k views
GCD using Euclid algorithm
Below is the problem taken from here.
Question 10: GCD*
The greatest common divisor of two positive integers a and b is the largest integer which evenly divides both numbers (with no remainder)...
13
votes
3answers
23k views
Math expression solver
I've recently stumbled upon an interesting challenge for me:
You should develop C application, that solves math expressions. Operations such as (+,-,*,/) should be supported, as well as (cos, sin, ...
13
votes
2answers
815 views
N-Queens, bitwise approach
I've recently solved the famous N-Queens problem:
Can you place \$N\$ chess queens on a \$N × N\$ board in such a way that no one
attacks another queen?
The idea here is based on the ideas from ...
12
votes
5answers
15k views
Brute-Force algorithm in C++
I wrote a brute-force algorithm which shall find all possible combinations of ASCII-values that can sum up to a specific value (int hashval).
The algorithm is ...
12
votes
3answers
17k views
List all possible numbers from a given array that sums up to a given number
I have to solve the following problem: Given an array of integers and given an integer value, list all possible numbers frm the array that sums up to the given value.
Example:
Input: array = {1, 2, ...
12
votes
6answers
4k views
Python 3 - Fibonacci Implementation
I wrote a function returning the n-th Fibonacci number in Python 3:
...
12
votes
4answers
3k views
To understand what recursion is, you must first understand recursion
This is the second assignment for my CS2 course:
Write a recursive C++ function writeLine() that writes a character repeatedly to form a line of n ...
12
votes
4answers
1k views
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 ...
12
votes
4answers
10k views
Calculating longest increasing sub-sequence recursively
I have trouble understanding recursion, so I'm trying to implement algorithms using it. I wrote this code that calculates the length of the longest increasing sub-sequence. How can I improve this?
<...
12
votes
3answers
7k views
Implementing an algorithm that walks the DOM without recursion
Here's a simple algorithm that walks the DOM given a node:
...
12
votes
4answers
888 views
Deletable primes
I came across this problem and I was wondering if you could help me to improve my solution.
Problem:
Count the number of ways you can reduce a deletable prime to a one
digit number.
A "...
12
votes
2answers
3k views
Sudoku solver using simple deductions and brute-force guessing
Here's my attempt at Weekend Challenge #3.
Key characteristics of this Python entry are:
The strategy is to alternate between "auto-complete" (making simple deductions such as naked singles and ...
12
votes
1answer
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 ...
12
votes
2answers
4k views
Validating a Binary Search Tree
This is an implementation of a function to check the property of a Binary Search Tree, that is:
the key in any node is larger than the keys in all nodes in that
node's left subtree and smaller ...
12
votes
1answer
387 views
PLZ HELP MEH IMPROVA MEH LOLCAT CODEZ, WHUCH CALCULUTS FAWCTORIALS
SUNCE MEH BEEN WRUTEN CODEZ IN MUNY DIFFRNT PROGRAMMING LANGUAGES, MEH THOUGHTZ THAT ME TRY TO WRITE CODEZ IN AN ESOTERIC LANGUAGE. MEH CODEZ CALCULUTS A FAWCTORIAL OF UH USR INPUTTED NUMBAH IN ...
12
votes
2answers
1k views
Object storing and retrieving using wildcard identifier
I'm writing an interpreter for a scripting language which allows objects to:
Have an alias
Be referenced using a wildcard
Contain child objects
Combination of all three above
For example:
...
12
votes
1answer
670 views
Trampoline Interceptor
Aim
In C#, the following method will cause a StackOverFlowException if called with parameter 0:
...
12
votes
1answer
176 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 ...
11
votes
5answers
3k views
Python: pass "mutable integer" in recursion
I'm working on some code to find the max depth/height in a tree. I came up with a recursive solution, and I find myself needing to pass an integer "by reference". Currently, I'm using a mutable ...
11
votes
3answers
23k views
Recursive, nested list traversal
Given a nested list of strings (which may contain other nested lists), print the contents of the list and the corresponding depth.
Here is my solution:
...
11
votes
5answers
699 views
Selection sorter
Reference: Is this a faithful rendition of the selection sort algorithm?
I'm working through an elementary book on sort and search algorithms, and writing some sample code to test my understanding. ...
11
votes
2answers
12k views
Recursive maze solver
Up for review today is some C++11 code to recursively search a maze for a path to a specified goal. This one shows dead-ends it explored on the way to finding the solution.
...
11
votes
3answers
918 views
Sudoku solver program written in modern c++
This is a simple program that solves a given Sudoku puzzle recursively. The input is provided as a file that contains the cells, 0 if empty, delimited by a , ...
11
votes
2answers
5k views
Lovely Lucky LAMBs
I am trying to solve this question from google's foobar. However, my code exceeds the time limit, even though when I tested it I got correct answers. How can I make my code more efficient?
Lovely ...
11
votes
3answers
1k views
Algorithm to calculate semi perfect integers, lack of efficiency
I'm working on an algorithm to calculate weird numbers, and to do so there are several properties that needs to be calculated, one of them being, if it is NOT a semi-perfect/pseudoperfect number.
My ...
11
votes
1answer
5k views
Recursive calculator in C
This is a calculator I wrote for a student's project.
It still has a problem (one that I know of), where it can't handle inputs of the form 2*2*2... (more than one ...
11
votes
2answers
414 views
Finding acronyms with >=1 letters at the start of each consecutive word
Problem
I'm seeking a clean and efficient way to determine whether one string is an initialism/acronym of another.
Example: IBM => International Business Machines
However, a key condition for my ...
11
votes
2answers
248 views
Let's Break Down the Party by Breaking the Party Down Recursively
This is a rags-to-riches an overdue alternative implementation on my previous question: Let's Break Down the Party
This alternative uses the int internal ...
