# 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.

942 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 ...
80k 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: ...
60k 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 ...
12k 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. ...
22k 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

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 ...
261 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 (...
2k 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 ...
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:...
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 ...
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. ...
43k 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'...
320 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 ...
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 ...
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 ...
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 ...
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 ...
35k 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)...
21k 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, ...
679 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 ...
6k 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 ...
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, ...
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 ...
9k 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: ...
578 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 ...
352 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: ...
638 views

### Trampoline Interceptor

Aim In C#, the following method will cause a StackOverFlowException if called with parameter 0: ...
149 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 ...
2k 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 ...
21k 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: ...
695 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. ...
3k 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 ...
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 ...
238 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 ...