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)
```