Algorithms For Dummies

 

»

The conditions for ending recursion haven’t been met, so the function must 

call itself again.

 

»

The conditions for ending recursion have been met, so the function returns a 

final value that is used to calculate the ending result.

FIGURE 5-1: 

In the recursion 

process, a 

function 

continuously calls 

itself until it 

meets a 

condition.

---

CHAPTER 5

  Performing Essential Data Manipulations Using Python 

     105

When a function calls itself, it doesn’t use the same arguments that were passed 

to  it.  If  it  continuously  used  the  same  arguments,  the  condition  would  never 

change and the recursion would never end. Consequently, recursion requires that 

subsequent calls to the function must change the call arguments in order to bring 

the function closer to an ending solution.

One of the most common examples of recursion for all programming languages is 

the calculation of a factorial. A factorial is the multiplication of a series of numbers 

between a starting point and an ending point in which each number in the series 

is one less than the number before it. For example, to calculate 5! (read as five 

factorial) you multiple 5 * 4 * 3 * 2 * 1. The calculation represents a perfect and 

simple example of recursion. Here’s the Python code you can use to perform the 

calculation. (You can find this code in the 

A4D; 05; Recursion.ipynb

 file on the 

Dummies site as part of the downloadable code; see the Introduction for details.)

def factorial(n):

    print("factorial called with n = ", str(n))

    if n == 1 or n == 0:

        print("Ending condition met.")

        return 1

    else:

        return n * factorial(n-1)

  

print(factorial(5))

  

factorial called with n =  5

factorial called with n =  4

factorial called with n =  3

factorial called with n =  2

factorial called with n =  1

Ending condition met.

120

The  code  meets  the  ending  condition  when 

n == 1

.  Each  successive  call  to 

factorial

 uses 

factorial(n-1)

, which reduces the starting argument by 1. The 

output  shows  each  successive  call  to  factorial  and  the  meeting  of  the  final 

condition. The result, 120, equals 5! (five factorial).

It’s important to realize that there isn’t just one method for using recursion to solve 

a problem. As with any other programming technique, you can find all sorts of ways 

to accomplish the same thing. For example, here’s another version of the factorial 

recursion that uses fewer lines of code but effectively performs the same task:

def factorial(n):

    print("factorial called with n = ", str(n))

---

106

 

   

  PART 1