Article is originally written by Zeeshan Amjad

Here I am going to give a detail about Recursion in C++. Definition: Recursion is the process where a function is called itself but stack frame will be out of limit because function call will be infinite times. So a termination condition is mandatory to a recursion.

Many complex problem can be solved by recursion in a simple code. But it's too much costly than iterative. because in every recursion call one stack frame will formed.You all already know that about it's cost. but if problem is very complex than no way to solve except recursion.

First recursion came into mathematics and then came into Computer science. Idea of it's use that first broke your problem into subproblems and solve it by using recursion.

In C++, Recursion can be divided into two types:

(a)Run- Time Recursion: Normal as in C

(b)Compile- Time Recursion: By using Template

Each of these can be also divided into following types:

1. Linear Recursion

2. Binary Recursion

3. Tail Recursion

4. Mutual Recursion

5. Nested Recursion

Example: Factorial calculation by linear recursion

Winding Process:

Function called Function return

Fact(6) 6*Fact(5)

Fact(5) 5*Fact(4)

Fact(4) 4*Fact(3)

Fact(3) 3* Fact(2)

Fact(2) 2* Fact(1)

Fact(1) 1* Fact(0)

Terminating Point

Fact(0) 1

Unwinding Process

Fact(1) 1*1

Fact(2) 2*1

Fact(3) 3*2*1

Fact(4) 4*3*2*1

Fact(5) 5*4*3*2*1

Fact(6) 6*5*4*3*2*1

To test it how it's working at compile time, just call

cout << Fact<-1>::factVal ;

And compile it then compiler error will come, because no template for -1.

Example: Fibonacci number

Example: Fibonacci number

Example: To find Even Or Odd number

Example: Ackermann function

"Teaching recursion using recursively generated geometric design"

by Aaron Gordon

### Introduction

Here I am going to give a detail about Recursion in C++. Definition: Recursion is the process where a function is called itself but stack frame will be out of limit because function call will be infinite times. So a termination condition is mandatory to a recursion.

Many complex problem can be solved by recursion in a simple code. But it's too much costly than iterative. because in every recursion call one stack frame will formed.You all already know that about it's cost. but if problem is very complex than no way to solve except recursion.

### Background

First recursion came into mathematics and then came into Computer science. Idea of it's use that first broke your problem into subproblems and solve it by using recursion.

### The code

In C++, Recursion can be divided into two types:

(a)Run- Time Recursion: Normal as in C

(b)Compile- Time Recursion: By using Template

Each of these can be also divided into following types:

1. Linear Recursion

2. Binary Recursion

3. Tail Recursion

4. Mutual Recursion

5. Nested Recursion

**This recursion is the most commonly used. In this recursion a function call itself in a simple manner and by termination condition it terminates. This process called 'Winding' and when it returns to caller that is called 'Un-Winding'. Termination condition also known as Base condition.**__1. Linear Recursion:__Example: Factorial calculation by linear recursion

__Run-Time Version__Code:

int Fact(long n) { if(0>n) return -1; if(0 == n) return 1; else { return ( n* Fact(n-1)); } }

Function called Function return

Fact(6) 6*Fact(5)

Fact(5) 5*Fact(4)

Fact(4) 4*Fact(3)

Fact(3) 3* Fact(2)

Fact(2) 2* Fact(1)

Fact(1) 1* Fact(0)

Terminating Point

Fact(0) 1

Unwinding Process

Fact(1) 1*1

Fact(2) 2*1

Fact(3) 3*2*1

Fact(4) 4*3*2*1

Fact(5) 5*4*3*2*1

Fact(6) 6*5*4*3*2*1

__Compile-Time Version__Code:

// template for Base Condition template <> struct Fact<0> { enum { factVal = 1 }; }; template <int n> struct Fact { // Recursion call by linear method enum { value = n * Fact<n - 1>::factVal }; };

cout << Fact<-1>::factVal ;

And compile it then compiler error will come, because no template for -1.

**Binary Recursion is a process where function is called twice at a time inplace of once at a time. Mostly it's using in data structure like operations for tree as traversal, finding height, merging, etc.**__2. Binary Recursion:__Example: Fibonacci number

__Run Time Version Code__Code:

int FibNum(int n) { // Base conditions if (n < 1) return -1; if (1 == n || 2 == n) return 1; // Recursive call by Binary Method return FibNum(n - 1) + FibNum(n - 2); // At a time two recursive function called so // binary }

__Compile Time Version Code__Code:

// Base Conditions template<> struct FibNum<2> { enum { val = 1 }; }; template <> struct FibNum<1> { enum { val = 1 }; }; // Recursive call by Binary Method template <int n> struct FibNum { enum { val= FibNum<n - 1>::val + FibNum<n - 2>::val }; };

**In this method, recursive function is called at the last. So it's more efficient than linear recursion method. Means you can say termination point will come(100%) only you have to put that condition.**__3. Tail Recursion:__Example: Fibonacci number

__Run Time Version Code__Code:

int FibNum(int n, int x, int y) { if (1 == n) // Base Condition { return y; } else // Recursive call by Tail method { return FibNum(n-1, y, x+y); } }

__Compile Time Version Code__Code:

template <int n, int x, int y> struct FibNum { // Recursive call By tail method enum { val = FibNum<n-1, y, (x+y)>::val }; }; // Base Condition or Termination template<int x, int y> struct FibNum<1, x, y> { enum { val = y }; };

**Functions calling each other. Let's say FunA calling FunB and FunB calling FunA recursively. This is not actually not recursive but it's doing same as recursive. So you can say Programming languages which are not supporting recursive calls, mutual recursion can be applied there to fulfill the requirement of recursion. Base condition can be applied to any into one or more than one or all functions.**__4. Mutual Recursion:__Example: To find Even Or Odd number

__Run Time Version Code__Code:

bool IsOddNumber(int n) { // Base or Termination Condition if (0 == n) return 0; else // Recursive call by Mutual Method return IsEvenNumber(n - 1); } bool IsEvenNumber(int n) { // Base or Termination Condition if (0 == n) return 1; else // Recursive call by Mutual Method return IsOddNumber(n - 1); }

__Compile Time Version Code__Code:

// Base Or Termination Conditions template <> struct IsOddNumber<0> { enum { val = 0 }; }; template <> struct IsEvenNumber<0> { enum { val = 1 }; }; // Recursive calls by Mutual Method template <int n> struct IsOddNumber { enum { val = n == 0 ? 0 : IsEvenNumber<n - 1>::val }; }; template <int n> struct IsEvenNumber { enum { val = n == 0 ? 1 : IsOddNumber<n - 1>::val }; };

**It's very different than all recursions. All recursion can be converted to iterative (loop) except nested recursion. You can understand this recursion by example of Ackermann function.**__5.Nested Recursion:__Example: Ackermann function

__Run Time Version Code__Code:

int Ackermann(int x, int y) { // Base or Termination Condition if (0 == x) { return y + 1; } // Error Handling condition if (x < 0 || y < 0) { return -1; } // Recursive call by Linear method else if (x > 0 && 0 == y) { return Ackermann(x-1, 1); } // Recursive call by Nested method else { return Ackermann(x-1, Ackermann(x, y-1)); } }

__Compile Time Version Code__Code:

// Base Or Termination condition template <int y> struct Ackermann<0, y> { enum { val = y + 1 }; }; // Recursive Call by Linear Method template <int x> struct Ackermann<x, 0> { enum { val = Ackermann<x-1, 1>::val }; }; // Recursive Call by Nested Method template <int x, int y> struct Ackermann { Enum { val = Ackermann<x-1, Ackermann<x, y-1> ::val>::val }; };

### References

"Teaching recursion using recursively generated geometric design"

by Aaron Gordon