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.

877 questions
Filter by
Sorted by
Tagged with
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 ...
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: ...
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 ...
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. ...
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 ...
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. ...
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? ...
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....
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 ...
1k views

Recursive and iterative Euclidean algorithms

Is this code too cryptic? Simple yes or no question. Feedback is optional. ...
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 ...
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 ...
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:...
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. ...
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 ...
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 (...
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 ...
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 ...
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 ...
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)...
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, ...
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 ...
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 ...
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, ...
3k views

Python 3 - Fibonacci Implementation

I wrote a function returning the n-th Fibonacci number in Python 3: ...
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 ...
1k views

...
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 ...
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'...
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? <...
6k views

Implementing an algorithm that walks the DOM without recursion

Here's a simple algorithm that walks the DOM given a node: ...
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 "...
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 ...
1k views

Flatten an array of integers in Python

The goal is to flatten an array of nested arrays of integers. For example [1, , [3, ]] should return [1, 2, 3, 4] I'm ...
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 ...
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 ...
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: ...
622 views

Trampoline Interceptor

Aim In C#, the following method will cause a StackOverFlowException if called with parameter 0: ...
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 ...
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: ...
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. ...
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. ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...