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
Filter by
Sorted by
Tagged with
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 ...
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: ...
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 ...
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. ...
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 ...
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? ...
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 (...
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. ...
4k views

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....
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 ...
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 ...
2k views

Recursive and iterative Euclidean algorithms

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

Implementing an algorithm that walks the DOM without recursion

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

Trampoline Interceptor

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