Questions tagged [recursion]
For challenges involving recursive functions, or functions or programs calling itself, directly or indirectly.
41 questions
21
votes
12
answers
1k
views
What's left after repeatedly removing palindromes
Sometimes a string has buried palindromes in it:
hallolilah contains lol.
And if we took out ...
- 8,078
7
votes
2
answers
595
views
Situations when recursion helps [closed]
Recursion is actually quite powerful, sometimes its doesn't look like that child problem of itself exist, but recursion is just helpful.
One case per answer.
- 32.4k
-3
votes
8
answers
1k
views
Number of cigarettes that can be made from a given number of butts
Assumption
A cigarette can be made by combining four cigarette butts. Cigarette butts last infinitely until smoked.
Explanation
Say you have 31 butts. That means, you can make 7 cigarettes from 28 ...
- 135
18
votes
7
answers
2k
views
The TAK function
The TAK function is defined as follows for integers \$x\$, \$y\$, \$z\$:
$$
t(x, y, z) = \begin{cases}
y, & \text{if $x \le y$} \\
t(t(x-1,y,z), t(y-1,z,x), t(z-1,x,y)), & \text{otherwise}
\...
- 79.3k
1
vote
0
answers
229
views
DP approach gives TLE [closed]
There is a question to basically find the largest sum in an array, such that no two elements are chosen adjacent to each other. The concept is to recursively calculate the sum, while considering and ...
- 11
13
votes
25
answers
2k
views
Output the length of (the length plus a message) [duplicate]
The task is simple. You're given an arbitrary string message. Return that message prefixed with a number, such that the length of that number plus the message equals the number. In other words, the ...
- 499
5
votes
6
answers
394
views
AoCG2021 Leftover: Recursive Combat
This challenge is one of the two challenges which were planned for Advent of Code Golf 2021, but didn't fit into the 25-day schedule.
Related to AoC2020 Day 22, Part 2.
Combat is a simple two-player ...
- 79.3k
17
votes
31
answers
2k
views
Nesting list with a value repeated `n` amount of times
Given the input of n and value. The code is supposed to nest the single element list with ...
- 2,031
22
votes
9
answers
1k
views
Unicode T-square
Challenge
Create a function or program that, when given an integer size, behaves the following way:
If size is equal to 1, ...
- 785
-8
votes
3
answers
362
views
Generate a RecursionError [closed]
Write the shortest possible code cause an error due to recursion too deep
Example error in python
RecursionError: maximum recursion depth exceeded
Example error in ...
- 773
9
votes
1
answer
304
views
Branch Out - Monkey Edition
The Monkey has swung home to find his tree all in pieces.
He likes order and scoops up all his 'tree-parts' and sets them out in 3 groups.
The Monkey's ...
- 261
18
votes
14
answers
3k
views
Visualize a Recursive Acronym
Background
Famously, the acronym GNU stands for GNU's Not Unix. 1
It's recursive because, after expanding it once, it still ...
- 34.1k
47
votes
76
answers
8k
views
Pointlessly make your way down the alphabet
Disclaimer: This challenge inspired by me spending the morning debugging recursive functions, which have been frying my brain a little.
Here's an example of recursion, from a letter, we keep going to ...
- 11.8k
32
votes
31
answers
9k
views
1, 2, 4, 8, 16, ... 33?
Challenge
Write a function/program that outputs either the n'th element, or the first n elements, in the well known number ...
- 46.8k
5
votes
2
answers
463
views
Golf my iteration function
Here is my ungolfed Ruby code for a function I want to try and golf:
...
- 2,496
3
votes
2
answers
360
views
Algorithm to print the Minimum number of adjacent character swaps necessary to remove all instances of "VK" in a given string?
For example, how many adjacent swaps are at least needed to convert some string such as BVVKCV to one without any instances of VK...
- 39
9
votes
12
answers
1k
views
Different combinations possible
Problem
Given a value n, imagine a mountain landscape inscribed in a reference (0, 0) to (2n, 0).
There musn't be white spaces between slopes and also the mountain musn't descend below the x axis.
...
8
votes
14
answers
7k
views
Recursively count lines of code, excluding empty lines and comments
Requirement: Write a program (in any language) that counts the number of lines of code in files matching *.sh in the directory tree starting from the directory that ...
- 207
17
votes
12
answers
712
views
Generalized Cantor set segment lengths
Problem
Let's define a generalized Cantor set by iteratively deleting some rational length segments from the middle of all intervals that haven't yet been deleted, starting from a single continuous ...
- 5,017
23
votes
17
answers
5k
views
One More Program and I'm Out!
Given a positive integer nesting level n and string s of printable ascii characters( to <...
- 16.4k
28
votes
16
answers
3k
views
Многочлены Чебышёва (Chebyshev Polynomials)
Chebyshev Polynomials are a family of orthogonal polynomials that pop up in all kinds of places in math, and they have a lot of quite interesting properties. One characterization of them is that they ...
- 44.1k
11
votes
15
answers
931
views
Repeated reciprocal
What you need to do is create a function/program that takes a decimal as input, and outputs the result of repeatedly taking the reciprocal of the fractional part of the number, until the number ...
- 349
44
votes
26
answers
6k
views
The best base is 10... Let's reach it!
Input:
A positive integer n consisting of digits in the range 0-9.
Challenge:
If d is the highest digit in the integer, assume the base of the number is d+1. E.g. if the integer is 1256 then you ...
- 46.8k
19
votes
2
answers
1k
views
Are these lists equal?
As you may very well know python has lists. As you might not know these lists can contain themselves.
a = []
a.append(a)
Python 2
Python 3
These are cool and ...
- 103k
58
votes
45
answers
5k
views
Arbitrary-length currying
Write a function, f, that takes in a positive integer and returns a function.
The new function returned should be identical to f...
11
votes
4
answers
2k
views
Output subdivisions of international standard paper sizes
ISO Paper Sizes Defined:
The A series paper sizes are defined by the following requirements:
...
- 1,345
61
votes
26
answers
6k
views
Cantor's unspeakable numbers
An unspeakable number is a number which is divisible by seven or has seven as one of its digits. A children game is to count skipping unspeakable numbers
...
- 1,762
24
votes
3
answers
577
views
Peel the potato
This is a potato:
@@
@@@@
@@@@@@
@@@@@@
@@@@
@@
More generally, a size N potato is defined as the following shape:
If N is even, it is 2 centered ...
- 341
117
votes
8
answers
5k
views
Exponentially Slimy Programming: Stacking Minecraft Slimes
Slimes are cube shaped enemies in Minecraft that break into multiple smaller versions of themselves when killed. For the purposes of this challenge we'll depict them as an 8×8 pixel image with 3 ...
- 90.7k
15
votes
2
answers
2k
views
Is there a way of shortening fat-arrow functions?
From what I've seen throughout my time here on PPCG, most JavaScript entries involving fat arrow functions tend to be one of two camps:
The simple ones that are capable of running as a single ...
- 7,619
20
votes
38
answers
3k
views
Hofstadter H-sequence
Definition
\$a(0) = 0\$
\$a(n) = n-a(a(a(n-1)))\$ for integer \$n > 0\$
Task
Given non-negative integer \$n\$, output \$a(n)\$.
Testcases
...
- 50.6k
11
votes
6
answers
487
views
Binary Recurrence Sequences
A binary recurrence sequence is a recursively-defined sequence of the following form:
$$F(1) = a_1 \\ \vdots \\ F(y) = a_y \\
F(n) = \alpha F(n-x) + \beta F(n-y), n > y$$
This is a generalization ...
user45941
13
votes
2
answers
1k
views
Recursive Steiner Chains
Steiner Chains are a set of N circles where each circle is tangent to 2 other non-intersecting circles as well as the the previous and next circles of the chain, as seen in the below images:
In ...
- 2,512
60
votes
55
answers
5k
views
Alex-style Addition
Inspired by Alex's glorious Learn you an R for great good, we are going to humbly recreate Alex's "one true R program" -- but with a twist.
Alex-style Addition works like this -- it has a 90% chance ...
- 11.3k
44
votes
7
answers
5k
views
Tiny Lisp, tiny interpreter
Lisp programmers boast that Lisp is a powerful language which can be built up from a very small set of primitive operations. Let's put that idea into practice by golfing an interpreter for a dialect ...
- 40.7k
13
votes
7
answers
702
views
Prefix Tree Traversal
Write a program that takes in (via stdin or command line) a string with the recursive form
PREFIX[SUFFIXES]
where
PREFIX may ...
- 90.7k
38
votes
13
answers
2k
views
Print, Increment, Decrement, Alias - Interpret Prindeal
Prindeal (pronounced prin-dee-al) is a new esoteric programming language that only has four commands: print, increment, decrement, and alias. Despite its minimalism, complex mathematical operations ...
- 90.7k
20
votes
12
answers
2k
views
Evaluating Parentheses and Brackets as Integers
Write a program that takes in a string of the four characters ()[] that satisfies these points:
Every left parenthesis ( has a ...
- 90.7k
8
votes
9
answers
4k
views
Ways to arrange the integers 1 to 9 with operators so that the result is 100
Prelude:
This task is taken from Five Problems Every Software Engineer Should Be Able to Solve in Less Than an Hour, which I really recommend.
The task:
Write a program that outputs all possibilities ...
- 2,083
6
votes
2
answers
903
views
Coding a recursive function for highest possible input
Challenge
You are given the following function:- which is the same as:-
with the base cases q(r, b, L) = 1 whenever r ≤ L, q(r, 0, L) = 0, if r > L and q(r, 0, L) = 1, if r ≤ L.
Your task is to ...
- 163
49
votes
46
answers
10k
views
The Ackermann function
The Ackermann function is notable for being the one of the simplest examples of a total, computable function that isn't primitive recursive.
We will use the definition of \$A(m,n)\$ taking in two ...
- 8,925