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.
2
votes
2answers
81 views
Non-Contiguous Substrings
Problem:
A non-contiguous substring of string \$s\$ is a sequence of \$k \geq 0\$ characters in \$s\$, in the order in which they occur in \$s\$. For instance, the set of all non-contiguous ...
0
votes
0answers
26 views
trying to make a Sudoku Solver with the recursive backtracking method [on hold]
I am a complete beginner, and Im just trying to learn general coding skills. I picked a sudoku solver as an intro project to get a grasp of java programming, but I cannot quite get it to work. Could ...
6
votes
4answers
196 views
Add one to a very large integer
I was asked to implement this in an interview a while back. I didn't pass the interview, mostly likely because it took me far too long to do. However, I'm interested to know how well implemented the ...
1
vote
1answer
116 views
Binary tree from given Inorder and Preorder traversal
Below is code which builds a Binary Tree from given Inorder and Preorder lists.
...
5
votes
1answer
37 views
Report with Subtotals — In Search Of An Abstraction
High Level Explanation of Code's Purpose
I wrote a class to create sectioned reports, where each section has a subtotal. It allows these reports to be nested within each other, to create multiple ...
4
votes
2answers
55 views
Calculating the number of elements of an underlying data structure
I read many comments on this question that one really shouldn't use local classes for functionality like which my code provides, but I couldn't really put things into perspective and decide what ...
1
vote
1answer
219 views
1
vote
1answer
43 views
Reversing a linked list recursively
This appears to work. Are there any edge cases I am missing? What are your thoughts on the algorithm and implementation?
...
3
votes
1answer
65 views
Merge Sort - Using Ruby and Recursion
I am implementing the algorithms of Course: Coursera Algorithm I.
I implemented the Merge-Sort using recursion and although it sorts correctly I am not sure if it is a correct implementation of this ...
6
votes
4answers
107 views
Java Recursive Depth First Search
I've created a recursive depth-first search implementation in Java as an example for an article I am writing on my website. It needs to be concise in order to fit on the page easily (independent of ...
2
votes
1answer
30 views
Lattice traversal functional algorithm
I have the following code which returned the solution I was wanting after running for 1 hour. Are there any techniques I could use to improve run-time?
If I were using imperative programming I would ...
4
votes
5answers
163 views
DFS in Binary Tree
I have written this code for DFS in a binary tree and would like improvements on it.
...
5
votes
1answer
101 views
Find maximum element in bitonic array
An array is bitonic if it is composed of an increasing sequence of integers followed immediately by a decreasing sequence of integers. Write a program that, given a bitonic array of N distinct ...
4
votes
3answers
134 views
Creating number pattern (triangle numbers) in C++ with minimum loops
We were asked to make a triangular number pattern in C++ with minimum loops:
____1_____
___2__3____
__4__5__6__
7__8__9__10
Code:
...
7
votes
1answer
66 views
Recursive search for combinations of words that have a specified MD5 hash
This code solves a challenge problem that a local company is hosting to attract/screen applicants. The link to the challenge is here.
In brief, we are given a wordlist containing approximately ...
5
votes
4answers
124 views
Recursive binary search in Python
I have implemented a recursive binary search in Python and tried to implement some verification to my code. Other than that, is there any optimization I am missing?
...
4
votes
2answers
76 views
Infinite list of strings containing 'a'
I was assigned to write a piece of Haskell code that makes an infinite list containing increasing numbers of 'a's.
My first thought was to write it as a list comprehension like this:
...
8
votes
3answers
110 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?
...
16
votes
3answers
639 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
66 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
70 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
54 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
49 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 ...
4
votes
1answer
161 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
126 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
207 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
311 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
77 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
223 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
152 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
521 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
208 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
864 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, ...
-2
votes
1answer
46 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
28 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
66 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
64 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
99 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
137 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
942 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
578 views
Fibonacci sum with memoization
Problem:
Using the recursion approach, find a Fibonacci sum without repetition of computation.
...
4
votes
3answers
303 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
303 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
146 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
124 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
596 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
129 views
Adjacency list with array data
I came through a question on Stack Overflow, which shows this array structure:
...
2
votes
2answers
124 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
31 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
208 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 ...
