Contest Python: ACSL › Unit 2 — Recursive Functions
Exercises: Unit 2 — Recursive Functions
There are two kinds of exercises here, just as on an ACSL contest.
- Short-answer: a recursive definition (or a short program) is given. Work out the value by hand with a call table, and write down one exact answer. Do not type it into Python until you have committed to an answer; working it by hand is the skill the contest tests.
- Programming: write a complete program that reads the input with
input()and prints exactly the output described. Every programming exercise gives you the definition: your job is to turn it into a recursive Python function. Save it as a.pyfile and run it from a terminal, for examplepython my_solution.py < my_input.txt. Print nothing extra.
The definitions use the notation from the lesson: * for times, x mod 3 for the remainder, floor(x / 2) for division rounded down, and abs(x) for the size of x without its sign.
Each exercise is marked with the lowest ACSL division it belongs to: Junior, Intermediate or Senior. Do every exercise at or below your division. Exercises marked Challenge are extra practice for when you want more.
Exercise 1: Step Down by Two
f(x) = { f(x - 2) + 3 if x > 4
{ x * x - 1 if x <= 4Find f(11).
Give your answer as a plain whole number, like 42 or -7.
How this is checked: Checked by comparing your answer with the expected answer.
Answer format: a number
Exercise 2: Odd, Even and Threes
f(x) = { x + 1 if x < 5
{ f(x - 2) + x if x >= 5 and x mod 3 = 0
{ 2 * f(x - 1) if x >= 5 and x mod 3 != 0Find f(10).
Give your answer as a plain whole number, like 42 or -7.
How this is checked: Checked by comparing your answer with the expected answer.
Answer format: a number
Exercise 3: Two Travellers
f(x, y) = { f(x - y, y + 1) + 2 if x > y
{ x * y if x <= yFind f(20, 2).
Give your answer as a plain whole number, like 42 or -7.
How this is checked: Checked by comparing your answer with the expected answer.
Answer format: a number
Exercise 4: Branching Out
f(x) = { f(x - 1) + f(x - 2) - 1 if x > 2
{ x + 1 if x <= 2Find f(7).
Give your answer as a plain whole number, like 42 or -7.
How this is checked: Checked by comparing your answer with the expected answer.
Answer format: a number
Exercise 5: Implement the Definition
Write a program that reads one whole number x and prints g(x), where
g(x) = { g(x - 5) + x if x > 8
{ 3 * x - 1 if x <= 8Write g as a recursive Python function.
Input. One line holding the integer x.
Output. One line holding g(x).
Constraints
-100 <= x <= 2000
Sample Input
20Sample Output
59The calls go g(20), g(15), g(10), g(5); g(5) = 14, so g(10) = 24, g(15) = 39 and g(20) = 59.
How this is checked: Checked by running your program on 5 test inputs (1 sample, 4 hidden) and comparing its output line by line.
Exercise 6: Divide by Three
f(x) = { f(floor(x / 3)) + (x mod 3) if x >= 3
{ x if x < 3Find f(50).
Give your answer as a plain whole number, like 42 or -7.
How this is checked: Checked by comparing your answer with the expected answer.
Answer format: a number
Exercise 7: Trace the Python Function
def digits(n):
if n < 10:
return n
return digits(n // 10) + 2 * (n % 10)
print(digits(4071))What exactly does the program print? Work it out by hand first.
How this is checked: Checked by comparing your answer with the expected answer.
Answer format: a number
Exercise 8: Three Before
Write a program that reads one whole number n and prints t(n), where
t(n) = { t(n - 1) + t(n - 2) + t(n - 3) if n > 2
{ n if n <= 2Write t as a recursive Python function.
Input. One line holding the integer n.
Output. One line holding t(n).
Constraints
0 <= n <= 20
Sample Input
6Sample Output
20Working upward: t(0) = 0, t(1) = 1, t(2) = 2, t(3) = 3, t(4) = 6, t(5) = 11, t(6) = 20.
How this is checked: Checked by running your program on 5 test inputs (1 sample, 4 hidden) and comparing its output line by line.
Exercise 9: Two Numbers Meet
Write a program that reads two whole numbers x and y and prints f(x, y), where
f(x, y) = { x + y if x <= 0 or y <= 0
{ f(x - 2, y - 1) + 3 if x > 0 and y > 0 and x > y
{ f(x - 1, y - 3) + x if x > 0 and y > 0 and x <= yWrite f as a recursive Python function with two parameters.
Input. One line holding x and y, separated by one space.
Output. One line holding f(x, y).
Constraints
1 <= x <= 1001 <= y <= 100
Sample Input
10 6Sample Output
14The calls go f(10, 6), f(8, 5), f(6, 4), f(4, 3), f(2, 2), f(1, -1).
f(1, -1) = 0, so f(2, 2) = 0 + 2 = 2, and each call above it adds 3, giving 14.
How this is checked: Checked by running your program on 5 test inputs (1 sample, 4 hidden) and comparing its output line by line.
Exercise 10: Back and Forth
f(x) = { g(x - 1) + 2 if x > 0
{ 1 if x <= 0
g(x) = { 2 * f(x - 2) if x > 1
{ x + 3 if x <= 1Find f(9).
Give your answer as a plain whole number, like 42 or -7.
How this is checked: Checked by comparing your answer with the expected answer.
Answer format: a number
Exercise 11: Ping and Pong
Write a program that reads one whole number x and prints p(x), where
p(x) = { q(floor(x / 2)) + x if x > 1
{ 1 if x <= 1
q(x) = { p(x - 1) - 1 if x > 0
{ 0 if x <= 0Write p and q as two Python functions that call each other.
Input. One line holding the integer x.
Output. One line holding p(x).
Constraints
0 <= x <= 1000000
Sample Input
20Sample Output
30The calls go p(20), q(10), p(9), q(4), p(3), q(1), p(0).
How this is checked: Checked by running your program on 5 test inputs (1 sample, 4 hidden) and comparing its output line by line.
Exercise 12: Around Zero
f(x) = { f(abs(x) - 7) + 2 if abs(x) > 5
{ x + 4 if abs(x) <= 5Find f(-20).
Give your answer as a plain whole number, like 42 or -7.
How this is checked: Checked by comparing your answer with the expected answer.
Answer format: a number
Exercise 13: Counting the Calls
f(x) = { f(x - 1) + f(x - 2) if x > 1
{ x if x <= 1When f(6) is worked out by following the definition exactly, f is called many times: f(6) itself, then f(5) and f(4), and so on, with the same argument often called more than once.
How many calls to f are made in total, counting the first call f(6)?
Give your answer as a plain whole number.
How this is checked: Checked by comparing your answer with the expected answer.
Answer format: a number
Exercise 14: Many Questions
The function f is defined for whole numbers x >= 0:
f(x) = { x if x < 10
{ f(floor(x / 2)) + 1 if x >= 10 and x mod 2 = 0
{ f(x - 3) + 2 if x >= 10 and x mod 2 = 1The first line of the input holds N, the number of questions.
Each of the next N lines holds one whole number x.
For each x, in order, print f(x) on its own line.
Constraints
1 <= N <= 1000 <= x <= 1000000000
Sample Input
3
7
40
99Sample Output
7
8
12For 40: f(40) = f(20) + 1, f(20) = f(10) + 1, f(10) = f(5) + 1, and f(5) = 5, so f(40) = 8.
How this is checked: Checked by running your program on 4 test inputs (1 sample, 3 hidden) and comparing its output line by line.
Exercise 15: Three Ways Down
f(x, y) = { f(x - 1, y) + f(x, y - 1) + f(x - 1, y - 1) if x > 0 and y > 0
{ 1 if x = 0 or y = 0Find f(3, 4).
Hint: build a table with one row for each x from 0 to 3 and one column for each y from 0 to 4, and fill it in from the base cases.
Give your answer as a plain whole number, like 42 or -7.
How this is checked: Checked by comparing your answer with the expected answer.
Answer format: a number
Exercise 16: Value and Calls
The function f is defined for whole numbers x >= 0:
f(x) = { f(x - 1) + f(x - 3) if x >= 3
{ x + 1 if x < 3Read one whole number x.
Print two numbers separated by one space: the value f(x), and the total number of calls to f made when f(x) is worked out by following the definition exactly, counting the first call f(x) itself.
Write f as a recursive function that returns a tuple (value, calls).
Constraints
0 <= x <= 25
Sample Input
6Sample Output
13 11f(6) calls f(5) and f(3); f(5) calls f(4) and f(2); and so on down to calls with x < 3, which make no further calls.
How this is checked: Checked by running your program on 5 test inputs (1 sample, 4 hidden) and comparing its output line by line.