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
36
votes
4answers
6k 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 ...
28
votes
3answers
79k 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: ...
28
votes
2answers
58k 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 ...
26
votes
4answers
9k 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. ...
23
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 ...
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. ...
19
votes
4answers
20k 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? ...
19
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....
18
votes
4answers
30k 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 ...
17
votes
4answers
1k views

Recursive and iterative Euclidean algorithms

Is this code too cryptic? Simple yes or no question. Feedback is optional. ...
17
votes
2answers
3k 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 ...
16
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 ...
16
votes
2answers
1k 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
2k 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
2answers
315 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 ...
15
votes
0answers
183 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 (...
14
votes
6answers
4k 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
3answers
2k 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 ...
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
3answers
31k 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
20k 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
568 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
4k 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 ...
12
votes
3answers
16k 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
3k 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

Short Java FizzBuzz using recursion and parameters

...
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
30k 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'...
12
votes
4answers
8k 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
6k 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
376 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
1k 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
301 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
915 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
622 views

Trampoline Interceptor

Aim In C#, the following method will cause a StackOverFlowException if called with parameter 0: ...
12
votes
1answer
133 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
3answers
19k 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
691 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
11k 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
981 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
4k 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
234 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 ...
11
votes
1answer
106 views

Recursive code to generate a parametric sweep of input values

I generate a set of data based off every combination of inputs. The source range that's inputs requires headers to identify the parameters. In its present state I'm not content as it's not as ...
10
votes
4answers
10k views

Recursive implementation of palindrome string checker

I've tried to refactor my program to single return statement at the end of the program, however, it ruins the end statements of the recursion because I want to return from function in specific line ...
10
votes
2answers
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 ...
10
votes
5answers
15k views

Pair matching elements from two lists

Here is a method that takes two lists (l1 and l2) and pairs up elements that "match". As you can see at the end of the code ...
10
votes
2answers
2k 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 ...