This activity extends the **“Teaching Foundations of Computer Science With Python on TI-Nspire™ Technology” ** workshop to study additional topics from computer science with the support of the TI-Nspire™ CX II graphing calculator with Python coding technology. We will explore **recursion**, a form of iteration that includes repeated, nested calls of a function.

In this activity, we will:

- Define a function using explicit notation
- Define a function using recursive notation
- Use return to send values to another function

## Materials for learning

Work along with this blog post by downloading the following materials:

Unit 5, Activity 1: Recursion Recursion notes page

Also, you’ll want to have the following handy:

- TI-Nspire™ CX II graphing calculator (with updated OS)

## Unit 5, Activity 1: Recursion

A great introduction to recursion can be found in Unit 5 Activity 1: Recursion. Start by working through that activity, then read through the following discussion of main ideas from the activity.

### Explicit notation

How does the line of code **print(“f(x) equals ”,f(x_user))** work?

This print statement prints the text “f(x) equals” then calls the function **f(x)** and passes the value of the variable **x_user **into** f(x)**. The function **f()** returns the value of **f(x_user)** to the print statement, which then displays it after the “f(x) equals” text.

For example, if the user enters an input of 3, then **x_user** would have a value of 3 stored to it. The print statement would print **f(x) equals** and then would call f(x) and send the value of **x_user** into the **f(x)** function. Within **f(x)**, the program would multiply the x-value of 3 times 3 then subtract 1. The program would return the value 3*3 – 1 = 9 -1 = 8 to the print statement, resulting in a printed output of **f(x) equals 8**.

### Recursive notation

How would the program **g(x)** evaluate * g*(3)? Explain this aloud to yourself or a colleague first, then read on for a possible explanation.

When **g(3)** is called, the value of 3 is passed into the program **g(x)** for **x**. Since 3 > 0, the program returns **2*g(2)** for **g(3)**. (Do you see why?)

This results in a method call for **g(2)**. The program then runs **g(2)**, which returns as **2*g(1)**.

This results in a method call for **g(1)**. The program then runs **g(1)**, which returns **2*g(0)**.

This results in a method call for **g(0)**. The program then runs **g(0)**, which returns 3 since x = 0. (Do you see why?)

Here what has happened so far:

**g(3)** = **2*g(2)**

*But what is g(2)?*

**g(2)** = **2*g(1)**

*But what is g(1)?*

**g(1)** = **2*g(0) **

*But what is g(0)?*

**g(0)** = **3 **

*Okay, great!*

So, what happens next? Does **g(3)** return 3? No, because that is the value of **g(0)**, not **g(3)**.

However, we can use the value of **g(0)** to find the value of **g(1)** to find the value of **g(2)** to (finally!) find the value of **g(3)**. This is recursion.

Here’s what that would look like: So, **g(0)** = 3, which then feeds into **g(1)** **= 2*g(0)** = 2*3 = 6, which then feeds into** g(2) = 2*g(1)** = 2*6 = 12, when then feeds into **g(3) = 2*g(2)** = 2*12 = 24. The function then returns **g(3) = 24**. This is an example of a recursive call in programming.

Tech tip:Return is found inMenu > Built-Ins > Function.

**Extensions:**

- How could the
**g**(x) function incorporate an**if…else…**(or**if…elif…else…**) structure instead of two**if**statements? - How could the function effectively respond to invalid entries such as
*x*= -4?

### Comparing explicit and recursive notation

Consider the two example functions we explored in **Unit 1, Activity 5: Recursion** and unpacked above in this blog. How are these methods similar? How are they different?

Both **f(x)** and **g(x)** determine a function value for a specific x-value. Also, they both include user input and resulting output.

However, **f(x)** directly calculates the output value of **f(x)** for a specific x-value using an explicit function rule. **g(x)** recursively determines the value of **g(x)** by first determining the value of **g(x-1)**, then **g(x-2)**, etc., until the function calls arrive at g(0); then, these values are fed back into the previously called **g()** functions until you arrive back at the **g(x)** value that was requested.

**g(x)** defined recursively is less efficient than the explicit function **f(x)**. However, recursion allows us to do some things that we *cannot do* with explicit rules.

## Recursion notes page

Let’s use an interactive notes page to formalize **recursion** and how it works.

Here are two pictures of the recursion notes page designed to capture our important learnings about **recursion**. This notes page uses a program **f(x)** that is different than the one we studied previously in this blog post.

### Recursion overview

Here we see a brief overview of what recursion is and what it looks like. Recursion involves a method that calls itself and involves a **base case** that will eventually stop the cycle of recursive calls. (In our previous discussion **g(0) = 3** resulted from running into the **base case**.)

Because recursion is inefficient and involves multiple, iterative method calls, it is a memory hog.

A recursive function includes at least two cases:

- Recursive Case — Where the function calls itself again but with a different input; this function call should be moving the function closer to the
**base case**. In the example above, this is the**else: return x + f(x-2)**part of the function. - Base Case — The terminating situation in a recursive program that does not use recursion to return an answer. In the example above, this is the
**if x<1: return 2**part of the function.

Predict the output for this recursive function if it is called with a method call of **f(5)**. Then read on to check your prediction.

This part of the interactive notes page showcases one way we can keep track of a method call for a recursive program.

When **f(5)** is called, an x-value of 5 passes into **f(x)**. This activates the **else** command (since 5 is not less than 1), which returns **x + f(x-2)**, which in this case is **5 + f(3)**.

But what is **f(3)**? This involves a method call of **f(3)**, which again returns **x + f(x-2)** since 3 is not less than 1. Specifically, this is returned as **3 + f(1)**.

But what is **f(1)**? (Can you feel how we’re in the **recursive call** part of the program?) A method call of **f(1)** also returns **x + f(x-2)** since 1 is not *less than* 1. Specifically, this is returned as **1 + f(-1)**.

But what is **f(-1)**? (Up until this point, we’ve been in the **recursive call**, but can you see the light of the **base case**?) A method call of **f(-1)** returns 2 — wahoo! No more recursive calls! We’ve reached the base case.

Our combined notations so far might look like this:

**f(5) = 5 + f(3)**

**f(3) = 3 + f(1)**

**f(1) = 1 + f(-1)**

**f(-1) = 2**

Don’t forget, though, that **we’re not done**! **f(5)** doesn’t return a value of 2; **f(-1)** does. We need to plug this value of **f(-1)** into **f(1)** so we can plug that into **f(3)** so we can plug that into **f(5)**. Phew! Doing that produces **f(5) = 11** as shown in the image above.

Code this program into your TI-Nspire^{TM} CX II graphing calculator, and evaluate **f(5)** using your program. Does it match our work above?

## Recursion examples

Here are three additional recursion examples to practice our recursion tracking skills. Explain your thinking aloud as you track your recursive progress on paper.

Use words such as *recursive case, base case, *and* method call* in your explanation. Work through these three examples on paper, then enter each recursive function into your TI-Nspire™ CX II graphing calculator to check your answers.

What value will be returned by the method call **f(16)** for the function **f(x)** shown below?

What value will be returned by the method call **f(2)** for the function **f(x)** shown below?

What value will be returned by the method call **f(5,20)** for the function **f(x,y)** shown below?

This program is a nice extension of the recursion topics we’ve explored here. Now there are two formal parameters **x** and **y** in the method header. No problem! Take your time and track through this recursion example on paper before testing it in your calculator.

## Reflecting on recursion

In this activity, we explored **recursion**, a form of iteration that includes repeated, nested calls of a function.

**Consider: **

- Recursion is a form of iteration. How does recursion compare to the other forms of iteration we have studied so far (namely,
**For**loops,**While**loops, and**Do While**loops)?

The next activity in this series will explore programming using lists (or arrays).

This series includes:

Do While Loops
Counters, Accumulators, and Comparing Loop Types
Recursion
Programming With Lists
Operating on Lists