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.

learn more… | top users | synonyms

14
votes
3answers
554 views

Enigma machine simulator - improving recursive algorithm performance

I'm new to Haskell and am confused by why my code seems to preform so poorly, and wonder if there's something I've not grasped about the coding philosophy behind the language, or the best way to take ...
5
votes
1answer
52 views

Permutation algorithm of N unique elements with low memory footprint

I actually had a real life need (outside work, no less) to come up with every single permutation of N elements (the N in my case being 12, so a total of ...
5
votes
1answer
39 views

Recursive Fibonacci generator

I decided to write a function that would generate an index of the Fibonacci sequence making use of Python's mutable default parameter. It's inspired by a question I answered on Stack Overflow where ...
6
votes
1answer
43 views

Getting all public constants from the main and nested classes

I wrote this recursive function to get all constants from a class and its subclasses. Can it be simplified? ...
1
vote
2answers
40 views

Finding difference between adjacent integers in an array - recursive Implementation

I'm trying to do a recursive implementation of the problem mentioned below. The code works, and takes care of a corner case with only 1 element in array (in which case I should return ...
3
votes
1answer
155 views

Magic numbers recursive solver

I wrote a program to solve a magic numbers puzzle. The puzzle works like this: You have an NxN square where each row, column, and diagonals add up to ...
3
votes
3answers
118 views

Resolving multiple “paths” in nested attributes

I need to resolve "multiple paths" specified like so: p1 = 'item.element.[compact|fullsize].documents.[note|invoice]' A list like this is expected: ...
3
votes
1answer
89 views

Maximum contiguous subarray with recursion

I've implemented the algorithm below for the maximum contiguous subarray problem and would like a review on three specific things: Making the code shorter Making the code faster Any other algorithms ...
6
votes
2answers
240 views

Finding binary combinations based on substitute wildcards

I am given a string containing the possible characters of : 0, 1, and ?, iterating over ...
2
votes
1answer
48 views

Insertion sort via recursion

I'm learning about algorithms and have been recently experimenting with insertion sort via recursion in Python. My code works fine, but I was wondering if there are any possible improvements that ...
10
votes
2answers
206 views

You need to diversify your strings

Challenge: Write a program which prints all the permutations of a string in alphabetical order. Specifications: Your program should accept a file as its first argument. The file contains ...
5
votes
3answers
114 views

Recursive and iterative approach for mergesort

Problem: Question 8: * Mergesort is a type of sorting algorithm. It follows a naturally recursive procedure: Break the input list into equally-sized halves Recursively sort both ...
6
votes
2answers
345 views

“Deep length” of a list

A list that contains one or more lists as elements is called a deep list. For example, [1, [2, 3], 4] is a deep list. Write a function ...
10
votes
2answers
207 views

Undo format when format disappears

I was posed a question as follows: Given a sentence like "John is a bad man", lets say all the formatting disappears and you are left with one string "johnisabadman". Given a dictionary of words, ...
4
votes
4answers
843 views

Calculating the factorial of any number

I have created what was a rather simple piece of code to calculate the factorial of a number, although I wanted to ensure that my program could calculate the factorial of any given number. To do this, ...
-1
votes
1answer
45 views

Checking whether the some of two ranges falls within a lower and upper bound

Problem 4 As per the given link, this exercise is part of recursion lab. Printer A prints a random x copies 50 ≤ x ≤ 60, and Printer B prints a random y ...
1
vote
1answer
25 views

Getting a table from an Excel worksheet

I need to get a table from an Excel worksheet. Sometimes I know the worksheet that contains the table, other times I might know it's going to be in one of a handful of worksheets, and still other ...
1
vote
1answer
63 views

Decomposing a number as a sum of two products using tree recursion

Below is the problem taken from page6 here. The TAs want to print handouts for their students. However, for some unfathomable reason, both the printers are broken; the first printer only prints ...
1
vote
2answers
62 views

Function to sort items with an array of keys

I'm working on a function to sort two elements using several properties. I want to know if the function is well structured. ...
-2
votes
2answers
74 views

Pascal's triangle with memoization

Problem: Pascal’s triangle is a useful recursive definition that tells us the coefficients in the expansion of the polynomial (x + a)^n. Each element in the triangle has a coordinate, given by ...
0
votes
1answer
65 views

Pascal's triangle - Recursion

Problem: Pascal’s triangle is a useful recursive definition that tells us the coefficients in the expansion of the polynomial (x + a)^n. Each element in the triangle has a coordinate, given by the ...
4
votes
4answers
878 views

Staircase problem solved using recursion

Problem Question taken from here. I want to go up a flight of stairs that has n steps. I can either take 1 or 2 steps each time. How many different ways can I go up this flight of stairs? Write a ...
2
votes
3answers
547 views

Fibonacci sum with memoization

Problem: Using the recursion approach, find a Fibonacci sum without repetition of computation. ...
4
votes
3answers
291 views

Inverse cascade challenge - Recursion

Print the following pattern, when you invoke inverse_cascade(1234) 1 12 123 1234 123 12 1 Solution: ...
7
votes
1answer
168 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 ...
1
vote
0answers
139 views

Using recursion schemes to avoid explicit corecursive unfolding

The code is self-contained and self-explaining. I want to improve the goal function. You can change everything below the ...
1
vote
1answer
113 views

Insect combinatorics challenge

Below is the problem taken from Berkeley's Cs61A page here Question 9: Insect Combinatorics* Consider an insect in an M by N grid. The insect starts at the bottom left corner, (0, 0), and ...
0
votes
4answers
594 views

Percentage of digits in n that are even

Question 7 from Lab 3 of Berkeley's CS61A course says: The following examples of recursive functions show some examples of common recursion mistakes. Fix them so that they work as intended. [...] ...
5
votes
2answers
99 views

Adjacency list with array data

I came through a question on Stack Overflow, which shows this array structure: ...
2
votes
2answers
92 views

Count the number of combinations with gap-restriction for every pair of values

A lottery draw consists of choosing 6 different values from 1 to 50. I want to calculate the number of combinations with gaps of at least 3 between every pair of values. I have used the following ...
2
votes
2answers
30 views

Incremental accumulator by subvectoring

The purpose of the following code is to, given a vector, compute the two accumulators: 1. head-till-nth element, 2. (n+1)th element-till-last (where n, and this is the catch, iterates from 1 till ...
3
votes
2answers
122 views

Recursive permutation of an array

Basically, this is a recursive function to generate all of the permutations of an array. The idea is this: recursive case: start at the specified array index, and make a case for starting the next ...
4
votes
1answer
78 views

Recursive Tic-Tac-Toe Solver in Python

I'm implementing a Tic-Tac-Toe solver in Python. It contains two functions: assess to determine whether a given board position is a win for either side, and ...
6
votes
2answers
76 views

Counting Increasing Subsequences of size K recursive

The original description of the problem can be found here, its input here and its expected output here. The problem: Given a integer sequence a1 ... an (-10000 \$\leq\$ ai \$\leq\$ 10000). ...
1
vote
2answers
52 views

Simple recursive function to find missing number in a permutation

This is a short and simple Python written to help me sharpen my dulling recursion skills. It expects a sorted permutation of integers n1..n2 in list format, with a single step missing (e.g., ...
3
votes
3answers
154 views

Reversing strings using recursion

I'm trying to solve exercises where I am required to use recursion. I wrote this: ...
2
votes
2answers
103 views

Beginner implementation of Merge Sort

This is my first time implementing a merge sort (just getting started with algorithms & data structures). Are there any obvious things I have done wrong? I am also worried that I have overused ...
4
votes
1answer
79 views

Merge sort implementation in JS

Just for learning and practicing I've created a completely recursive version of the merge sort algorithm. I've tested it a little bit and it seems working, but I'm quite sure that it can be largely ...
4
votes
5answers
167 views

Permutation of n lists

I have code which gives permutations for 10 lists. The code works fine for small number of lists with small number of values. Result : It should return all possible permutations. I have to store the ...
2
votes
1answer
83 views

Practicing recursion with getElementsByClassName

I'm trying to get a good grasp on recursion by implementing document.getElementsByClassName. I've made something that works but I'd like to know if there is some ...
1
vote
2answers
33 views

Inserting new Node in a Binary Search Tree

I wrote this method to recursively insert a new node at the proper position in a BST. Is it good enough? Can it be improved? It went through a couple of revisions and I still am not very confident in ...
4
votes
0answers
49 views

Selecting subset of size k using recursion

Sometimes I need to implement recursive algorithms that pass a certain state from one recursive call to another. For example, a greedy subset selection: we have a set of candidate objects, and we ...
3
votes
2answers
130 views

Generate URLs from a complex JSON object using recursion

My task is here as follows : Input : A complex/nested JSON object with nested arrays as well objects Output : A JSON object that contains a set of URLs with their titles: ( key,value ) ...
3
votes
1answer
70 views

Recursive Sudoku Solver

I just finished up a program which takes a byte[9][9] as input and recursively does a DFS to find any solutions (including multiple solutions). I'm pretty happy ...
3
votes
1answer
52 views

Recursively delete empty folders in Lua

I have written a script that run in WingFTP Server which has a Lua scripting engine built in. The script recursively deletes empty folders except the specified root folder. ...
7
votes
2answers
69 views

Recursively evaluate neighbors in a two dimensional grid

I'm creating a puzzle mini game where there is a board of gems, varying in color, and chosen at random. This is what my code generates: When you click on a gem the game should traverse the board ...
1
vote
1answer
120 views

Combining two sorted lists

I'm just hoping if there's a way to simplify this recursive code that takes 2 sorted lists and combines the two together in a sorted manner (without actually having to re-sort them). ...
5
votes
2answers
609 views

Recursively insert a node in an ordered Linked List

I've written this and it works great. Is there any shorter or simpler way to achieve the same result without distinguish between cases? ...
0
votes
0answers
86 views

Find the most efficient combination that equals target number in ArrayList

I want to implement the following function: Given a target sum, return the combination that equals the target sum and is the most efficiënt combination in the array of an ...
3
votes
1answer
213 views

Creating a menu as nested unordered lists from JSON data

I have a JSON input using which I have written below function to recursively create an unordered list. Is there more precise way to achieve it? ...