A Function That Calls Itself

Name: A Function That Calls Itself
Author: StemPy Lab

Recursion is a function that calls itself on a smaller problem. It sounds strange at first, but it is how we naturally think about problems that contain smaller copies of themselves: a folder inside a folder, a word whose last part is a shorter word, a tower of discs that holds a smaller tower. In this course you find the base case that stops the calls, write countdowns, sums, factorials, powers and Fibonacci numbers, follow the call stack going down and coming back up, and see why the simple Fibonacci function is slow. You use recursion on text and lists, and you finish with a project that walks through folders inside folders. The practice runs your functions on many inputs and tells you which ones fail.

5 lessons, about 2 h 30 min5 simulations14 problems10 practice questionsPython in every lesson

Created by StemPy Lab

Course outline (5 lessons)

Lesson 1about 35 min
A function that calls itself
A recursive function calls itself on a smaller problem. Every recursive function has two parts: a base case, a problem so small that the answer is known, which stops the calls, and a recursive case, where the function calls itself with a problem that is one step closer to the base case. Without a base case, or with a call that does not get closer, the function calls itself for ever, and Python stops it with a RecursionError. A line before the recursive call runs on the way down, and a line after it runs on the way back.
1 simulation2 practice questions3 Python programs3 problems1 Python lab1 question set
Read the lesson
Lesson 2about 25 min
Factorials and the call stack
The factorial is the famous example: n factorial is n times the factorial of n minus 1, and the factorial of 1 is 1, which is the base case. The calls go down to the base case, and the answers come back up, each call multiplying the answer it receives. While the base case runs, all the calls above it are waiting, each holding its own n, and Python keeps them in a pile called the call stack. A function that prints its calls with indents shows the calls going down and the answers coming back.
1 simulation2 practice questions1 Python program3 problems1 Python lab
Read the lesson
Lesson 3about 30 min
More recursion, and its cost
Many problems fit recursion: the sum of 1 to n, a power, the digits of a number and the Fibonacci numbers. Each has a base case and a smaller problem. The simple Fibonacci function calls itself twice, and the same small values are worked out again and again, so the number of calls grows very fast: 177 calls for n equal to 10, and 21891 for n equal to 20. A loop is often faster and uses less memory, while recursion is often clearer, especially for problems that break into smaller copies of themselves. Anything that can be done with recursion can be done with a loop.
1 simulation2 practice questions2 Python programs7 problems2 Python labs
Read the lesson
Lesson 4about 30 min
Recursion on text and lists
Recursion on text and lists uses the first item and the rest. The smaller problem is the text or the list without its first item, or without both ends. The base case is an empty text or list, or one with a single item. A palindrome test compares the first and last letters and then asks the same question about the middle. A recursive sum, length, search or count of a list takes the first item and adds the answer for the rest. Slicing makes a new copy at every call, so for long data a loop is better. Use recursion on lists when the idea is clearer, or when the structure itself has lists inside lists.
1 simulation2 practice questions2 Python programs1 problem1 Python lab
Read the lesson
Lesson 5about 30 min
Project: folders inside folders
In this project we walk through folders inside folders. A folder is a dictionary, and a file is a number that is its size, so a folder can hold folders to any depth. A loop cannot easily handle a depth that is not known, but a recursive function can: for each item, if it is a folder, ask the same question inside it, and if it is a file, use its size. We write functions for the total size, the number of files, a printed tree with indents, and a search that gives the path of a file. We plan the expected answers by hand, test the empty folder and a folder with only folders, and extend the project with the biggest file and the depth.
1 simulation2 practice questions1 Python program1 Python lab1 note
Read the lesson

Test Your Learning

Recursion: Predict the Output

10 questions · 15 min

Not started

Your teacher

StemPy Lab

← All Courses

← Find It and Put It in OrderNext →

More onPython Essentials › Recursion

Discussion (0)

Loading…

A Function That Calls Itself

Course outline (5 lessons)