20250625 17:00 Recursion

← Previous

🏠 Homepage

Next Chapter →

                          

Recursion: Function Calling Itself (Wait, What?!)

In C, a function can call itself.

This is called recursion. It's like asking someone,

"Hey, can you do this?"
And they say,
"Sure, let me first ask myself to do it." 

Example: Factorial

You know this math thing:

• 4! = 4 × 3 × 2 × 1 = 24
  We can also say:

• 4! = 4 × 3!

• 3! = 3 × 2!

• ...and so on.

This makes it a perfect case for recursion!

Non-Recursive Way (Using Loop)

int factorial(int x) {

  int f = 1;
  for (int i = x; i >= 1; i--)
    f = f * i;
  return f;
}

Easy loop. No drama.

Recursive Way (Using Function Inside Itself!)

int rec(int x) {

  if (x == 1)
    return 1;
  else
    return x * rec(x - 1);
}

Breakdown for rec(3):

• rec(3) → 3 × rec(2)

• rec(2) → 2 × rec(1)

• rec(1) → 1 ← stops here
  Then it unwinds like:

• rec(2) = 2 × 1 = 2

• rec(3) = 3 × 2 = 6

Boom! You got the answer.

Behind the Scenes: The Stack 

When functions call each other (or themselves), C uses a thing called a stack:

• It's like a pile of plates.

• Last plate in → First one out. 

So when we call functions, info gets pushed on the stack.
When they return, it's popped off.
Just like:

• Put things on → function starts

• Take them off → function ends

Recursive calls keep stacking until the base case (like if(x == 1)) is reached.
If you forget the base case, it’s like stacking plates forever.
Stack overflow!

Library Magic 

Want to make your own function library?

Steps:

1. Write function (e.g. factorial() in fact.c)

2. Compile → You get fact.obj

3. Use Turbo C’s tlib tool to add it to a .lib file

   tlib math.lib + fact.obj
   

4. Write a header file fact.h with function declaration

5. Use the function in any program!

   #include "fact.h"
   

You can even create your own cool collection of:

• factorial()

• prime()

• fibonacci()
  All packed into one neat .lib 

Summary 

• Functions = Mini-programs inside your program

• Recursion = A function that calls itself (like echoing your name in a cave )

• Stack handles the memory behind recursive calls

• Don't forget a base case or you'll crash the stack!

• You can create your own libraries and become a function wizard