Introduction

Overview

Teaching: 5 min
Exercises: 0 min

Questions

• Why do we bother learning about recursion?

Objectives

• To set out the objectives of this lesson.

In this lesson you will learn about a very powerful programming technique called recursion. In a nutshell, recursion is a technique by which a function makes (direct or indirect) calls to itself during its execution.

In computing, recursion provides a powerful technique for problem solving. It is a different way of thinking about problems which often leads to elegant solutions.

In programming, it often leads to much shorter code to solve difficult problems. Recursion is also an important technique in the study of Data structures and Algorithms. Moreover, recursion (in a more Mathematical sense) is studied in the theory of computation as well.

Objective

I will use a number of illustrative examples throughout this lesson to introduce you to the idea of recursion. More concretely, I will teach you about:

• Recursive definition (Factorial function) and recurrence relation (Fibonacci sequence)
• How we implement recursion and how python handle recursion.
• Algorithms that use recursion (Greatest Common Divisor)
• Recursive thinking and problem solving (Towers of Hanoi)

Goals

By the end of this lesson, I hoped that you

• become more comfortable writing recursive algorithms.
• discover the relationship and difference between recursion and iteration.
• can convert between iterative and recursive algorithms.
• can describe how a python implements recursion.
• can draw a recursion tree for a recursive algorithm.

Key Points

• Recursion is a very powerful programming and problem solving technique.