Log in / Register

Home arrow Computer Science arrow Data Structures and Algorithms with Python
< Prev   CONTENTS   Next >

3 Recursion

Don't think too hard! That's one of the central themes of this chapter. It's not often that you tell computer programmers not to think too hard, but this is one time when it is appropriate. You need to read this chapter if you have not written recursive functions before. Most computer science students start by learning to program in a style called imperative programming. This simply means that you are likely used to thinking about creating variables, storing values, and updating those values as a program proceeds. In this chapter you are going to begin learning a different style of programming called functional programming. When you program in the functional style, you think much more about the definition of what you are programming than how you are going to program it. Some say that writing recursive functions is a declarative approach rather than an imperative approach. You'll start to learn what that means for you very soon. When you start to get good at writing recursive functions you'll be surprised how easy it can be!

Python programs are executed by an interpreter. An interpreter is a program that reads another program as its input and does what it says. The Python interpreter, usually called python, was written in a language called C. That C program reads a Python program and does what the Python program says to do in its statements. An interpreter interprets a program by running or executing what is written within it. The interpreter interacts with the operating system of the computer to use the network, the keyboard, the mouse, the monitor, the hard drive, and any other I/O device that it needs to complete the work that is described in the program it is interpreting. The picture in Fig. 3.1 shows you how all these pieces fit together.

In this chapter we'll introduce you to scope, the run-time stack, and the heap so you understand how the interpreter calls functions and where local variables are stored. Then we'll provide several examples of recursive functions so you can begin to see how they are written. There will be a number of recursive functions for you to practice writing and we'll apply recursion to drawing pictures as well.

One thing you will not do in the homework for this chapter is write code that uses a for loop or a while loop. If you find yourself trying to write code that uses either kind of loop you are trying to write a function imperatively rather than functionally.

Fig. 3.1 The Python Interpreter

Recursion is the way we will repeat code in this chapter. A recursive function has no need for a for or while loop.

3.1 Chapter Goals

By the end of this chapter, you should be able to answer these questions.

• How does Python determine the meaning of an identifier in a program?

• What happens to the run-time stack when a function is called?

• What happens to the run-time stack when a function returns from a call?

• What are the two important parts to a recursive function and which part comes first?

• Exactly what happens when a return statement is executed?

• Why should we write recursive functions?

• What are the computational complexities of various recursive functions?

You should also be able to write some simple recursive functions yourself without thinking too hard about how they work. In addition, you should be able to use a debugger to examine the contents of the run-time stack for a recursive function.

Found a mistake? Please highlight the word and press Shift + Enter  
< Prev   CONTENTS   Next >
Business & Finance
Computer Science
Language & Literature
Political science