Indirect Recursion & Nested Recursion in Data Structure | McCarthy 91 function | Recursion Playlist C++ | Coding With Clicks

🔁 Indirect Recursion

📖 Definition:

Indirect recursion occurs when two or more functions call each other in a cycle.

📌 Example in C++:

#include <iostream>
using namespace std;

void functionA(int n);
void functionB(int n);

void functionA(int n) 
{
    if (n > 0) 
    {
        cout << "A: " << n << endl;
        functionB(n - 1);  // A calls B
    }
}

void functionB(int n) 
{
    if (n > 0) 
    {
        cout << "B: " << n << endl;
        functionA(n / 2);  // B calls A
    }
}

int main() 
{
    functionA(5);
    return 0;
}

🧠 Explanation:

• functionA() calls functionB(), and functionB() again calls functionA().
• This continues indirectly until the base condition stops the cycle.

🧠 These two lines:

void functionA(int n);
void functionB(int n);

are called function declarations (also known as function prototypes) in C++.

✅ Their purpose:

They tell the compiler ahead of time that:

• functionA and functionB exist
• They both take an int as a parameter
• They both return nothing (void)

This way, you can call them before their full definition appears in the code.

🧩 Why is it necessary here?

Because of indirect recursion.

The problem:

In the code:

void functionA(int n) 
{
    functionB(n - 1); // calls functionB
}

If the compiler hasn’t seen functionB yet, it will give an error:

❌ “What is functionB? I haven’t seen it yet.”

The solution:

We declare them first at the top:

void functionA(int n);
void functionB(int n);

Then we define them below.

In Short:

Code	What It’s Called
void functionA(int n);	✅ Function Declaration
void functionA(int n) { ... }	✅ Function Definition

💡 Why Use Declarations?

• C++ requires a function to be either defined or at least declared before it is used.
• In your case, since functionA calls functionB, and functionB calls functionA, you need declarations before either function is defined.

📦 Analogy:

Think of it like introducing someone before they speak:

🗣️ “Next up, we have Mr. A who will talk about recursion.”

Now when Mr. A starts talking, everyone knows who he is. Without an introduction, they’d be confused.

🧠 Step-by-step Execution:

Let’s trace the calls starting from functionA(5).

1. functionA(5)
   • n = 5 > 0 → prints: A: 5
   • calls functionB(4)
2. functionB(4)
   • n = 4 > 0 → prints: B: 4
   • calls functionA(2) → 4 / 2 = 2
3. functionA(2)
   • n = 2 > 0 → prints: A: 2
   • calls functionB(1)
4. functionB(1)
   • n = 1 > 0 → prints: B: 1
   • calls functionA(0) → 1 / 2 = 0 (integer division)
5. functionA(0)
   • n = 0 → fails condition → stops

✅ Final Output:

A: 5
B: 4
A: 2
B: 1

🧮 Why does 1 / 2 = 0 in C++?

🔷 Because you’re using integers, not floats.

In your code:

void functionA(int n);
void functionB(int n);

• The parameter n is of type int (integer).
• When you do n / 2, you’re dividing one integer by another.

📌 In integer division:

• 1 / 2 does not give 0.5
• It gives 0, because it drops the decimal part (truncates it)

🧪 Examples:

Expression	Type	Result
1 / 2	int	0
1.0 / 2	float	0.5
(float)1 / 2	float	0.5

🧩 Nested Recursion

📖 Definition:

Nested recursion is when a function’s argument itself is a recursive call.

📌 Example in C++ (McCarthy 91 Function):

#include <iostream>
using namespace std;

int nestedRecursion(int n) 
{
    if (n > 100) return n - 10;
    return nestedRecursion(nestedRecursion(n + 11));
}

int main() {
    cout << "Result: " << nestedRecursion(95);  // Output: 91
    return 0;
}

🧠 Explanation:

• The recursive call is nested inside another recursive call: return nestedRecursion(nestedRecursion(n + 11));
• It goes deeper and deeper before resolving.

🧩 Nested Recursion – What does this mean?

“When a function’s argument itself is a recursive call” means:
You are passing the result of a recursive call as the input to another recursive call.

In other words, the recursion is nested inside itself.

🔁 Normal Recursion:

A function calls itself like this:

return f(n - 1);

That’s a simple/regular recursion — the function calls itself once.

🧠 Nested Recursion:

Here’s the key line:

return nestedRecursion(nestedRecursion(n + 11));

This means:

• First, the inner call nestedRecursion(n + 11) is evaluated.
• Then, the outer call uses that result as its argument.

So it’s like:

int temp = nestedRecursion(n + 11);   // inner call
return nestedRecursion(temp);         // outer call

➡️ That’s nested recursion: recursive calls inside recursive calls.

📝 Summary:

Feature	Explanation
🔁 Normal recursion	Function calls itself once directly
🧩 Nested recursion	Recursive call is passed inside another
🔄 Evaluation order	Inner call happens first, then outer

🔑 What is Argument Passing?

In programming, argument passing means sending a value to a function when you call it.

🧠 Now, in Recursion:

Normal Recursion:

int factorial(int n) 
{
    if (n == 0) return 1;
    return n * factorial(n - 1);  // Argument passed is (n - 1)
}

Here, factorial calls itself and passes n - 1 as the argument.

🧩 In Nested Recursion:

return nestedRecursion(nestedRecursion(n + 11));

• The argument to the outer nestedRecursion(...) is the result of another recursive call: nestedRecursion(n + 11).

➡️ So instead of passing a simple value like n - 1, you’re passing the result of another function call.

🧠 What is the McCarthy 91 Function?

The McCarthy 91 function is a famous recursive function named after John McCarthy, a computer scientist and the inventor of the LISP programming language.

It is used to demonstrate nested recursion — recursion where a function’s argument itself is another recursive call.

🧩 The Function:

Here’s the C++ version of the McCarthy 91 Function:

int mccarthy91(int n) 
{
    if (n > 100)
        return n - 10;
    else
        return mccarthy91(mccarthy91(n + 11));
}

🔍 How It Works:

• If n > 100, it returns n - 10.
• Otherwise, it calls itself twice, nesting the recursion:
  mccarthy91(mccarthy91(n + 11)).

🧪 Examples:

Input (n)	Output
101	91
100	91
95	91
50	91

✔️ For all n ≤ 100, it always returns 91.
✔️ For n > 100, it returns n - 10.

🤯 Why is it interesting?

Because:

• It looks very complex (calls itself inside itself).
• But always returns 91 for all inputs ≤ 100.
• It’s used in academic and interview settings to teach recursion and nested recursion logic.

📦 Summary:

Feature	Description
📛 Name	McCarthy 91 Function
🔁 Type	Nested Recursion
📌 Behavior	Always returns 91 for inputs ≤ 100
🎓 Purpose	Educational — shows deep/nested recursive logic

If you give input 120 to the McCarthy 91 function, it will return:

✅ Output: 110

📝 Rule of Thumb:

Input n	Output
n > 100	n - 10
n ≤ 100	Always 91

📝 Summary Table:

Type	Definition	Example Call
Indirect Recursion	Function A calls B, B calls A	A() → B() → A()
Nested Recursion	A recursive call is passed as an argument	f(f(n + 11))