Recursion in C

Hello students, welcome to Kwickprep. Can a function call itself? It can, and it is called recursion. But if it never stops, the program crashes. Today we learn how recursion works and why it needs a base case. Then we write factorial and Fibonacci, and compare recursion with loops.

Recursion is simpler than it sounds. A function that calls itself is called a recursive function. Each call solves a smaller version of the problem, like asking the person ahead in a ticket queue for their position. And it must stop at the simplest case, when the first person in the queue simply says, my position is one.

Here is our first recursive function. Main calls count of three. Count prints three, then calls itself with n minus one, which is two. That call prints two and calls count of one, which prints one. Then count of zero is called. Now n double equals zero is true, so it returns without calling again.

Every recursive function has two parts. The base case is the simple case that gives an answer without calling again. In our countdown, it was n equals zero. The recursive case is where the function calls itself, with a smaller value. Each call must move closer to the base case. If there is no base case, the calls never stop, memory runs out, and the program crashes with a stack overflow.

To understand recursion, you must know the call stack. A stack is like a pile of plates, where you add and remove only at the top. Every function call gets its own stack frame, a small block of memory. That frame holds its own copy of the parameters and local variables. A new call is pushed on top of the pile. When a call returns, its frame is popped off, and the call below it continues.

Factorial of n means n into n minus one, into n minus two, and so on down to one. Factorial of five is one hundred twenty. Notice that factorial of n is n into factorial of n minus one. That is our recursive case. The base case is, if n is one or less, return one. So fact of five prints one hundred twenty.

Let us watch the stack for fact of three. First, the frame for fact of three is pushed, and it waits for three into fact of two. Next, fact of two is pushed on top, and it waits for two into fact of one. Then fact of one hits the base case and returns one. Now frames pop in reverse order. Fact of two returns two, and fact of three returns six.

Time to pause and predict. What does fact of zero return? It returns one, because zero is less than or equal to one, so the base case runs at once. This matches mathematics, where factorial of zero is defined as one. One more warning. Factorial of thirteen is more than six billion, which is too big for an int, so the answer comes out wrong.

In the Fibonacci series, each number is the sum of the two numbers before it. It starts with zero and one. So the function fib of n returns fib of n minus one, plus fib of n minus two. There are two base cases, fib of zero is zero and fib of one is one, and the line return n handles both. The loop in main prints the first seven terms, zero, one, one, two, three, five, eight.

But this Fibonacci function has a hidden problem. Fib of five calls fib of four and fib of three. Then fib of four calls fib of three again, so the same work is done twice. As n grows, the number of calls grows very fast. Fib of forty makes hundreds of millions of calls, and you can feel the delay.

Any recursive function can also be written with a loop, and this is called iteration. Here f starts at one. The loop multiplies f by one, two, three, four and five. It prints one hundred twenty, the same answer. There is only one variable f, and no new stack frames.

Board exams often ask you to compare recursion and iteration. Recursion stops at the base case, while a loop stops when its condition becomes false. Recursion uses a new stack frame for every call, while a loop reuses the same variables. So recursion is usually slower, because calls take extra time. But recursive code can be shorter and closer to the maths. A missing base case causes a stack overflow, while a wrong loop condition causes an infinite loop.

So when should you use each one? For simple counting, sums and factorial in real programs, a loop is simpler and faster. Recursion suits problems that are made of smaller copies of themselves. Good examples are the Tower of Hanoi puzzle, and folders inside folders on your computer. When you do use recursion, write and test the base case first.

Let us revise what we learned today. Recursion means a function calls itself. The base case stops it, and every call must move closer to that base case. Each call gets its own stack frame, which is popped when it returns. Factorial of n is n into factorial of n minus one, and Fibonacci adds the two terms before it. Loops save memory and time, while recursion can read more naturally. Trace fact of four on paper, frame by frame, before you run it.