Loops and Repeated Function Calls

The 3N+1 rule depends on one decision: if the current number is odd, the next number is 3 times the current number plus 1; if it is even, the next number is half of the current number.

Programming

Starting From a Single Question

This article looks at one function from the function examples in this chapter. The function is named nextN, and it takes a whole number and returns the next number in the 3N+1 sequence. The chapter is about return values, so the goal is to see exactly what a function hands back to its caller and how the function decides what to hand back. We start with the code itself and work outward from it, rather than starting with a definition of the sequence.

Keep one idea in mind as you read: nextN never tries to produce the whole sequence. It answers one question per call, namely given this number, what comes next? Everything that follows is about how it answers that question and how a caller can use the answers to build a longer chain.

Predict Before You Read the Rule

Before reading the explanation of the branches, try the function on paper. Pick an input, apply the odd-or-even test, and decide what the function should return. Work out the value before you look at the answer.

What do you think happens?

If nextN is called with 7, what value does it return?

Reveal answer

Answer:

7 is odd, so the function takes the odd branch and returns 3 times 7 plus 1, which is 22. The even branch is never reached on this call.

The One Decision Behind 3N+1

The 3N+1 rule depends on one decision: is the current number odd or even? Everything else follows from that choice. Each step produces exactly one new number, and that number becomes the input to the next step. This is why the sequence can be produced one value at a time by a function that only needs to know the current value.

Rule

Notice that the rule has exactly two outcomes. An odd number is always sent upward to three times itself plus one, and an even number is always halved. The rule does not depend on any history of earlier values, so a function that receives only the current number has all the information it needs to choose the next one.

Inside the nextN Function

The function tests currentN % 2 == 1 and returns one of two expressions, so each call produces exactly one return value. The code below is an original example written to show that structure. It follows the rule above and is not a copy of a listing from the source.

Code walkthrough

def nextN(currentN):
    if currentN % 2 == 1:
        return 3 * currentN + 1
    else:
        return currentN // 2

1
Line 1 defines the function, which accepts one whole number.
2
Line 2 applies the test. The remainder after dividing by 2 is 1 only for odd numbers.
3
Line 3 runs only when the test is true, and the return statement sends back 3 times the input plus 1.
4
Line 4 handles every other case, which for whole numbers means the input is even.
5
Line 5 returns half the input. Because a return ends the function, the even branch never runs on an odd input.

The parameter currentN receives the current value of the sequence.
currentN % 2 == 1 is the single decision: it is true only when the number is odd.
The odd branch returns 3 times currentN plus 1.
The even branch returns half of currentN; the // operator keeps the result a whole number.

Given an input, which condition is checked first, and which of the two expressions does the function take and return?

Read the diagram from the top. The input enters, the odd-or-even test is applied, and exactly one of the two expressions produces the value that the function returns. The return keyword does two things at once: it supplies the value the caller receives, and it ends the function's execution. That is why only one branch runs per call.

Tracing a Single Call Step by Step

Worked example

Tracing nextN(5)

What does nextN return when called with 5, and which branch runs?

1
Apply the test
5 % 2 is 1, so the condition currentN % 2 == 1 is true.
2
Choose the branch
The odd branch runs. The else branch is skipped entirely.
3
Compute the expression
3 times 5 is 15, and 15 plus 1 is 16.
4
Return and stop
The return statement sends 16 back to the caller and ends the function.

Result

nextN(5) returns 16. One call produced one step.

From One Step to a Whole Sequence

A single call to nextN gives one step. To see the full sequence, you feed each returned value back in as the next input. Because nextN returns one value per call, a caller that wants the full sequence needs a loop. The loop passes each returned value back into nextN and stops when the value reaches 1.

How does the caller feed each returned value back in as the next input, and how does the cycle end once the sequence reaches 1?

Each arrow in the diagram is one call to nextN. The caller takes the value that came back, passes it in as the next input, and repeats. The output of one call is the input of the next, so the chain continues until the stopping condition is met.

A Loop That Collects the Sequence

The loop below is an original example written to show the caller's side of the pattern. It passes each returned value back into nextN, collects the values in a list, and stops when the value reaches 1. The function nextN itself is unchanged.

python

def build_sequence(start):
    values = [start]
    current = start
    while current != 1:
        current = nextN(current)
        values.append(current)
    return values

print(build_sequence(6))

def build_sequence(start):
    values = [start]
    current = start
    while current != 1:
        current = nextN(current)
        values.append(current)
    return values

print(build_sequence(6))

Output (expected)

[6, 3, 10, 5, 16, 8, 4, 2, 1]

Notes on the code

The while loop keeps calling nextN until current reaches 1.
Each returned value is stored in values, so the caller, not nextN, keeps the whole sequence.
The loop starts from 6, which is the example traced in the source.

Notice what nextN does not do in this arrangement. It never prints the sequence, never stores a list, and never checks whether it has reached 1. Those jobs belong to the caller. This division of work keeps nextN small and correct for one question, while the caller decides how many times to ask it and what to do with each answer.

Single Call Versus Full Sequence

Aspect	One call to nextN	Caller with a loop
What it returns	One next value	A collection of every value produced
Branches run	Exactly one per call	One branch per iteration
Knows about 1	No	Yes, through the loop condition
Stores history	No	Yes, in the list
Typical input	One whole number	A starting number

Division of work between the function and its caller

Mistakes Beginners Make With Repeated Calls

Common mistake
Expecting one call to produce the whole sequence
What it looks like
```
nextN(6) is treated as if it returns 6, 3, 10, 5, 16, 8, 4, 2, 1.
```
Why it fails
A single call returns one value because the return statement ends the function.
Do this instead
Call nextN repeatedly, passing each result back in, usually inside a loop.
Common mistake
Running both branches on the same call
What it looks like
Assuming nextN(5) computes 16 and also computes 2 from the even expression.
Why it fails
The return in the odd branch ends the function, so the even branch is never reached on that call.
Do this instead
Decide which branch applies first, then compute only that expression.
Common mistake
Reading the test as checking the result instead of the input
What it looks like
Testing whether 16 is odd before calling nextN(16).
Why it fails
The condition currentN % 2 == 1 is applied to the input passed to the function.
Do this instead
Apply the odd-or-even test to the current number that is being passed in.
Common mistake
Forgetting that a loop needs a stopping condition, so the caller never finishes the sequence

Practice Tracing and Predicting

EASY

Without running any code, work out nextN(10), then nextN of that result, then nextN of that second result. Write down which branch runs at each step and the value that is returned.

Hints

Start by asking whether 10 is odd or even.
The even branch returns half the input, so the first result is 5.
Then ask the same question about 5, which is odd, and apply the odd branch.

Your attempt (not saved)

MEDIUM

Predict how many calls to nextN are needed to go from 6 to 1 in the traced sequence, then check your count against the list [6, 3, 10, 5, 16, 8, 4, 2, 1].