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
8
votes
2answers
731 views

Tic-Tac-Toe Recursive Solver

I am attempting to create a Tic-Tac-Toe game that uses a recursively checks every possible game board, and finds which boards result in a victory for X. (I ultimately plan to turn this into an AI ...
2
votes
2answers
4k views

Find the minimum number of coin change

Description: You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that ...
3
votes
0answers
271 views

Recursive solution for Longest Substring Without Repeating Characters written in Elixir

Here's my recursive implementation of a sliding window algorithm to find the longest substring of a given string without repeating characters. Is there a more idiomatic-Elixir way to write this? <...
3
votes
0answers
109 views

Merging bin-data via a bin count threshold

When performing a chi-squared test, one takes the square of the differences of the expected counts per bin and observed counts per bin, and divides these per-bin differences by the expected counts per ...
1
vote
2answers
290 views

Find subsets of size K in N set

The question is: There is a set An, and it consists of integers from 1 to n. ...
1
vote
1answer
301 views

Recursive Fibonacci in Java

I just started learning recursion and memoization, so I decided to give a simple implementation a shot. Works with some simple test cases I came up with. Is there anything I can add to make this more ...
4
votes
3answers
1k views

Sum numbers represented as linked lists

Problem Description: You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add ...
1
vote
2answers
762 views

Eight Queens Recursive

I am working on a Java textbook chapter on recursion, and I am to implement an Eight Queens solution using recursion. Though I know that I am to post working code in Code Review, I do believe this ...
5
votes
2answers
115 views

Finding non-self-intersecting paths of certain moves that touch all points in a grid

The problem I'm trying to solve is the following: You have a 10x10 grid and starting from the upper-left point you have to touch all the points, without passing through the points that have already ...
2
votes
1answer
485 views

Python Converting numbers to words, using Recursive

My function recursively calls itself until it decodes every numbers. rec_ntw face_value_count -> (Incremental variable) denotes ones, tens, hundreds and thousands face_value -> (Dictionary) denotes ...
4
votes
1answer
742 views

Max Sum of Nodes in Each Path in Binary Tree

I wanted to get a review on an algorithm I wrote for a binary tree problem. The problem is the following. Return the maximum sum between all branches in a binary tree. A branch is defined as all ...
8
votes
2answers
4k views

A beautiful and easy way of permutation with recursion

I want to share a better version of permutation with you. Yesterday, when I was reading Horowitz's Fundamentals of Data Structures In C++, and I noticed that the result of the code, at page 32, in ...
1
vote
1answer
55 views

Reverse a string recursively

I just finished this exercise where i should reverse a string with a recursive function. First of all, i created a separate function called swap to swap the chars, should i write it as function ...
0
votes
2answers
55 views

CTE Query and DateTime Matching

I have two tables (they are defined below and you can use the SQL below to build them) ...
2
votes
3answers
878 views

Find the longest path in a matrix where each step has entries that differ by 1

Given an N*N matrix that all numbers are distinct in it, the function should find the maximum length path (starting from any cell) such that all the cells along the path are in increasing order with a ...
2
votes
1answer
125 views

Ackermann function in Rust

Using the algorithm at the end of this research paper, I've written an extremely fast 1 Ackermann function in Rust. Can the implementation be made faster? Thoughts: Using a struct makes a lot of ...
1
vote
1answer
60 views

Simple backtracking code

Is this good or can it be improved? The program should backtrack the two variables until this logic operation is true: a & b. ...
6
votes
1answer
2k views

C# recursive backtracker labyrinth generation & game

So for over a weekend I decided to write something rather simple. For maze generation I've followed this algorithm and aside from that I've made a little game, to go from A to B. Everything works fine ...
4
votes
0answers
37 views

Apply arbitrary action during recursive generator function

I've got this recursive generator function. It will traverse an object looking for "leafs", any keys that don't point to sub-objects. Then it applies one of two actions on the leaf and yields it. Any ...
2
votes
1answer
192 views

Check the equality for each subset of a string S against the target T and return a count

I wrote the following code to solve this leetcode problem: ...
2
votes
1answer
56 views

Make a given number by adding given numbers

I have created a code that checks if a number can be made by adding different quantities of given numbers and if so returns the quantities. Is this the best way to do this or is there a more efficient ...
3
votes
1answer
92 views

Recursion memorization table

The following code is for this problem. Input The input consists of a single line with three integers n , s , and k (1 ≤ n ≤ 10,000, 1≤ k ≤ s ≤ 500 ). n is the number of throws, k ...
4
votes
0answers
730 views

AWS EC2 metadata fetcher in Python

Update https://docs.aws.amazon.com/AWSEC2/latest/UserGuide/ec2-instance-metadata.html This seems to be the schema for the instance metadata, though the way they describe it isn't really handy for ...
0
votes
1answer
76 views

Maze maker for game using recursive method

I wold like some feedback on this mazefactory, it creatse a maze in a 2D array starting in the middle (the treasure room) and creating new rooms until it reaches the outside of the maze. The maze is ...
6
votes
3answers
473 views

Recursive function challenge

Problem statement Given a list of float numbers, and four operators +, -, *, / with flat preference, find the maximum value by inserting operator between each consecutive pair of numbers. For ...
1
vote
4answers
1k views

Improving Fibonacci recursion with BigIntegers

I've been tasked with making a fast Fibonacci recursive method that uses BigInteger to calculate REALLY big numbers. However, to calculate numbers past 30 it takes ...
4
votes
1answer
294 views

Recursive grid traveling algorithm

I'm trying to come up with a solution to a coding challenge on Kattis, where there is a 2D grid filled with x's and o's, and the goal is to figure out whether or not a given starting coordinate can ...
3
votes
3answers
1k views

Tower Hopper problem recursive approach

The Tower Hopper problem gives us an array of values representing heights that express how far we can jump from a certain tower, and asks whether there's a way to get from ...
1
vote
1answer
287 views

Recursive matrix multiplication

I've just written a recursive matrix multiplication and I want to know my mistakes or problems. Is there a better way doing this? ...
0
votes
1answer
114 views

Maximum sub array sum equal to k

Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k. For example: Input: nums = [1,1,1], k = 2 Output: 2 ...
1
vote
0answers
194 views

Insertion Sort Algorithm

Here is my insertion sort algorithm: Note: Insertion sort works by starting off with the first item in the list and then inserting the next item in the original list into the correct place in the ...
1
vote
1answer
230 views

Reinterpreting a string, treating < as a backspace character

I've come up with a solution to this coding challenge using recursion. In summary, the input is a string where the < symbol represents a backspace (up to 1 ...
3
votes
1answer
176 views

Advent of Code 2017, Day 7 - Recursive Circus

This is my solution to Advent of Code 2017, Day 7 – Recursive Circus (both parts, you might not be able to see the second part unless you're logged in and solved the first part, but I'll summarize it ...
2
votes
3answers
96 views

Program that should output nth arrangement of paintings

I'm currently practicing for the British informatics olympiad by doing past papers. I'm on question 3 of the 2015 paper and trying to use recursion to solve it. I'm pretty new to using recursion but ...
8
votes
1answer
138 views

AoC Day 24 2017: Electromagnetic Moat

This year's AoC has a puzzle for day 24 that was (supposedly) intended to be solved with recursion. Here is the description: --- Day 24: Electromagnetic Moat --- The CPU itself is a large, ...
8
votes
1answer
1k views

Fibonacci in linear time by using an extra pointer

I have a function to find the nth number in a Fibonacci sequence, in which I am recursively calling the function. The sum is stored in a class variable and I have an extra pointer I increment every ...
1
vote
0answers
468 views

binary search tree Inorder successor to test candidate confidence

Problem statement Given the root node and a node in the binary search tree, find the inorder successor of the given node. Here is the example of binary search tree, Given the node with ...
12
votes
6answers
3k views

Python 3 - Fibonacci Implementation

I wrote a function returning the n-th Fibonacci number in Python 3: ...
7
votes
1answer
744 views

Finding Second Largest Element in an Array

Here's my implementation using divide and conquer in C++. What do you think of this implementation regarding running time ? ...
8
votes
6answers
3k views

Base 26 (letters) and Base 10 using recursion

I was messing around with base conversion between decimal and Base26 (alphabet) with no 0th case because I needed it for the Google Sheets API in order to find specific cell values from a 3 ...
1
vote
1answer
944 views

Recursive quicksort in Python

I want to find a more elegant way to build a recursive sorting function. The function randomly selects one of the numbers from a given list, k, and splits the list ...
12
votes
1answer
132 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 ...
2
votes
1answer
4k views

Recursive BFS solution for tree traversal

I'm somewhat new to the wonderful world of Python, outside of simple codecademy-like challenges online. This function was part of a project for school. It's tested and works, but I'm looking for some ...
0
votes
1answer
151 views

Ruby Linked List implementation

I've made a Ruby linked list data structure class and a lookup method. I know that lookup will only fetch the first occurrence ...
3
votes
2answers
186 views

Segementing a recursive tree in haskell

Could somebody help me work out how to abstract the recursion from this code for me please? I'm trying to write something that takes a pandoc structure, and subdivides the tree whenever it finds a ...
1
vote
0answers
154 views

Buying Apples - SPOJ

THIS is the link to the problem on SPOJ. I thought it would be better to give the link to the problem instead of me trying to explain as the question is not very clear at first sight. I was able to ...
8
votes
7answers
699 views

Function to build a string based on the recursion depth

I was doing a JavaScript challenge to test myself and I succeeded in finding a solution but the code is very ugly. I was hoping to get some opinions on what a better solution would look like. The ...
4
votes
0answers
127 views

Given a string of letters, output all English words formable using only those letters

As an introduction to Python classes and an exercise in recursion / tree-traversal, I wrote a small script that forms all English words using only the letters in an input string. Useful for things ...
1
vote
0answers
577 views

C# MVC Generic Custom Model Binder

I recently created a custom model binder as a training exercise and wanted to see how I could improve it. It currently uses recursion and works great, but I was wondering how I could convert this to ...
2
votes
2answers
1k views

Python - Knight's tour recursive function [closed]

I realize that there're many implementations of Knight's tour problem suggested across webs, without jumping to those suggested solutions (most in Java, I'm not proficient in Java), I managed to ...