Home > IB Computer Science 2017, Other stuff > Recursion practice

Recursion practice

Recursion is a common topic on the new syllabus and it has feature in every exam since 2014. To get you to think about recursion, here are some simple tasks.

Write the following recursive functions (in Java because the IB’s pseudocode doesn’t have a return statement – doh!):

  • A function that takes an int array argument and returns the maximum int in the list.
  • A function that takes a string and returns true if it is a palindrome.
  • A binary search function to find an int n in an int array.
  • A function that takes an int n and return n factorial.
  • A function that takes an in n and returns the nth Fibonacci number.
  • A function that takes an int n and prints the Fibonacci sequence up to n.
  • A routine in Logo or Python that creates a Koch snowflake.
  • A routine in Logo or Python that creates a Sierpinski triangle.

Look at the following Python code. The “left”, “right” and “forward” commands are just like there are in Logo. Sketch the pattern that the following calls will make:

koch(t, 0, 100)
koch(t, 1, 100)
koch(t, 2, 100)
import turtle

def koch(t, order, size):
    if order == 0:
        t.forward(size)
    else:
        koch(t, order-1, size/3)
        t.left(60)
        koch(t, order-1, size/3)
        t.right(120)
        koch(t, order-1, size/3)
        t.left(60)
        koch(t, order-1, size/3)

# EXECUTION STARTS HERE
t = turtle.Turtle()
koch(t, 3, 300)
Advertisements
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s