Algorithms For Dummies

Explaining recursion

Many people have a problem using recursion because they can’t easily visualize 

how it works. In most cases, you call a Python function, it does something, and 

---

104

 

   

  PART 1 

 Getting Started

then it stops. However, in recursion, you call a Python function, it does some-

thing,  and  then  it  calls  itself  repeatedly  until  the  task  reaches  a  specific 

 condition — but all those previous calls are still active. The calls unwind them-

selves one at a time until the first call finally ends with the correct answer, and 

this  unwinding  process  is  where  most  people  encounter  a  problem.  Figure  5-1 

shows how recursion looks when using a flow chart.

Notice the conditional in the center. To make recursion work, the function must 

have such a conditional or it could become an endless loop. The conditional deter-

mines one of two things: