Worksheet · No. 01 · Recursion

The Art of Recursion

Read each program carefully. Trace through it line by line on paper. Then write what you believe the program will print in the box provided.

Name

Roll No.

Date

Part One

Warm-up — Plain functions

Three short programs without recursion. Get into the rhythm of tracing before things get interesting.

01 What does this program print?

def process(n):
    result = 0
    while n > 0:
        result = result + n % 10
        n = n // 10
    return result

print(process(234))

Output

02 What does this program print?

def check(a, b):
    if a > b:
        return a - b
    else:
        return b - a + 1

print(check(5, 3))
print(check(2, 7))

Output

03 What does this program print?

def square(x):
    return x * x

def compute(a, b):
    return square(a) + square(b)

print(compute(3, 4))

Output

II.

Part Two

A function that calls itself. Pay close attention to when work happens — before the recursive call, or after it.

01 What does this program print?

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

fun(4)

Output

02 What does this program print? Look closely — only one line moved.

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

fun(4)

Output

03 What does this program print?

def total(n):
    if n == 0:
        return 0
    return n + total(n - 1)

print(total(5))

Output

04 What does this program print?

def fact(n):
    if n == 1:
        return 1
    return n * fact(n - 1)

print(fact(5))

Output

05 What does this program print? There are two print statements now.

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

fun(3)

Output

06 What does this program print?

def power(a, b):
    if b == 0:
        return 1
    return a * power(a, b - 1)

print(power(2, 4))

Output

07 What does this program print? The function calls itself twice.

def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(5))

Output