The Art of Recursion

A second helping. New patterns, new traps. Read each program carefully and write what you believe it will print.

Name

Roll No.

Date

Part One

Warm-up — Plain functions

Three short programs without recursion. Trace them on paper before reaching for the answer.

01 What does this program print?

def reverse_num(n):
    rev = 0
    while n > 0:
        rev = rev * 10 + n % 10
        n = n // 10
    return rev

print(reverse_num(1234))

Output

02 What does this program print?

def grade(marks):
    if marks >= 90:
        return "A"
    elif marks >= 75:
        return "B"
    elif marks >= 60:
        return "C"
    else:
        return "F"

print(grade(82))
print(grade(58))
print(grade(95))

Output

03 What does this program print?

def cube(x):
    return x * x * x

def diff(a, b):
    return cube(a) - cube(b)

print(diff(3, 2))

Output

II.

Part Two

Recursion — Trace the output

Each function calls itself, but the way it shrinks the problem is different every time. Watch carefully.

01 What does this program print? Notice the step size.

def fun(n):
    if n <= 0:
        return
    print(n, end=" ")
    fun(n - 2)

fun(7)

Output

02 What does this program print? The print is conditional.

def fun(n):
    if n == 0:
        return
    fun(n - 1)
    if n % 2 == 0:
        print(n, end=" ")

fun(6)

Output

03 What does this program print?

def count(n):
    if n == 0:
        return 0
    return 1 + count(n // 10)

print(count(78912))

Output

04 What does this program print?

def digit_sum(n):
    if n == 0:
        return 0
    return (n % 10) + digit_sum(n // 10)

print(digit_sum(1234))

Output

05 What does this program print?

def mult(a, b):
    if b == 0:
        return 0
    return a + mult(a, b - 1)

print(mult(5, 4))

Output

06 What does this program print? The function calls itself twice, with a print between.

def fun(n):
    if n == 0:
        return
    fun(n - 1)
    print(n, end=" ")
    fun(n - 1)

fun(3)

Output

07 What does this program print? Both arguments change each call.

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

print(gcd(48, 18))

Output