Recursion in Python

Hello students, welcome to Kwickprep. Can a function call itself? It sounds strange, but yes, it can. Today we will learn recursion, the call stack, and the base case. We will write factorial, Fibonacci and sum of digits, and see why efficiency matters.

First, a new word. Recursion means a function that calls itself. Each call works on a smaller copy of the same problem. The calls must stop when the problem becomes very simple. Think of a set of nesting dolls, where each doll has a smaller doll inside, until the tiniest one.

Here is a rocket launch countdown. Double equals asks, is n equal to zero? If not, the function prints n, then calls itself with n minus one. So countdown of three prints three and calls countdown of two. That prints two and calls countdown of one. Finally n is zero, so it prints Go and returns, which means it stops.

How does Python remember all these calls? It uses the call stack. A stack is a pile, like plates at a wedding buffet, where the last plate added is the first one taken. Every function call puts a new frame on top of the stack. A frame is a small box that keeps that call's own values, like its own n. When a call returns, its frame is removed from the top.

Our first program is factorial. The factorial of five is five times four times three times two times one, which is one hundred twenty. The base case is the simplest case, where we know the answer without calling again. Here it says, if n is less than or equal to one, return one. Otherwise, return n times the factorial of n minus one. Pause and predict. What is fact of zero? One, because zero is less than or equal to one, and zero factorial is one in maths too.

Let us watch the stack for fact of three. Each new row is a new plate placed on top. In row one, fact of three starts, so one frame is on the stack, waiting for three times fact of two. In row two, fact of two goes on top, so there are two frames, waiting for two times fact of one. In row three, fact of one goes on top, making three frames. It is the base case, so it answers at once.

Now the plates come off from the top, newest first, and the answers travel back. First, fact of one returns one, and its frame is removed, so two frames are left. Next, fact of two gets that one, returns two times one, which is two, and leaves one frame. Last, fact of three returns three times two, which is six, and zero frames are left, so the stack is empty.

Here is the same idea as a flowchart. Every call of fact starts at the top. The diamond asks, is n less than or equal to one? If yes, this is the base case, and we return one without calling again. If no, we are in the recursive case, so the function calls itself with n minus one. Then it multiplies n by that answer and returns it.

Remember these rules. The base case is where the answer is already known, so there are no more calls. The recursive case calls the same function with a smaller value. Every call must move closer to the base case, or the calls never end. If there is no base case, Python stops with a recursion error, saying the maximum depth was exceeded.

Second, the Fibonacci series. Each term is the sum of the two terms before it. The first two terms are zero and one, so the base case returns n itself when n is zero or one. The recursive case adds fib of n minus one and fib of n minus two. The loop prints the first eight terms. End equals a space keeps them on one line.

Third, add the digits of a number. We need two operators here. The percent sign is modulus, which gives the remainder, so n modulus ten gives the last digit. Double slash is floor division, which drops the last digit, so two zero two six becomes two zero two. The base case is a single digit, less than ten. So two plus two plus zero plus six gives ten.

Recursion depth means how many calls are waiting on the stack at the same time. Every frame uses memory, so Python sets a limit. Get recursion limit shows the limit, and one thousand is the typical default. Down uses a one line if else, so it returns zero when n is zero, or else calls down of n minus one. Down of nine hundred works, because it stays under the limit. But down of five thousand would stop with a recursion error.

Recursion can also be slow. Here calls counts how many times fib runs. The global keyword lets the function change the calls variable outside it. Plus equals adds one each time. Fib of twenty needs over twenty one thousand calls, because it solves the same small terms again and again. Fib of forty would need hundreds of millions of calls.

One fix is to remember answers we already found. The cache tool comes from the functools module in the standard library. The line with the at sign, called a decorator, wraps fib so each answer is saved. Now fib of eighty finishes instantly, because each term is worked out only once. A simple loop is also a great choice for Fibonacci.

Let us revise what we learned today. Recursion is a function that calls itself. The call stack adds a frame for each call and removes it when the call returns. The base case stops the calls, and the recursive case moves closer to it. We wrote factorial, Fibonacci and sum of digits. And always keep the depth limit and repeated work in mind. Try tracing the stack for fact of four on paper.