Recursion Data Structure

Recursion is a fundamental concept in computer science and programming, where a function calls itself in order to solve a problem. A problem can be broken down into smaller subproblems, and the solution to each subproblem helps in solving the overall problem.

A recursive function has two key parts:

Base Case: This is the condition where the recursion ends. The base case does not make a recursive call.

Recursive Case: This part of the function calls itself, reducing the problem to a simpler form at each step.

Recursion is particularly useful for problems that exhibit self-similarity, where a problem can be broken down into similar subproblems.

Example of a Simple Recursive Function: Factorial

A classic example is the recursive definition for the factorial
function:

n! = (n - 1)! * n

for n > 1; 1! = 0! = 1.

long Fact(int n)
{
	if (n < 1)
	return 1; // Base case: returns the base solution
	return n * Fact(n-1); // Recursive call for n > 1
}

Features of Recursion

Depth of recursion is the longest chain of procedure that calculate function F(n) in recursive way.

Recursion doesn’t differ from normal procedure when function are used. It means, that variables are local and are valid just inside the single procedure.

Example

#include <stdio.h>
int sum (int num)
{
	if (num==0)
		return 0;
	return sum(num-1)+(num);
}
int main()
{
	int num = 10;
	printf("%d\n", sum(num));
	getchar();
	return 0;
}

Example

#include <stdio.h>
void Triangle (int x) 
{
	if (x <= 0)
		return;
	Triangle(x- 1);
for (int i = 1; i <= x; i++)
	printf("*");
	printf("\n")
}
int main() {
	Triangle(7);
	return 0;
}

Trace of the program

Triangle(7)
 Triangle(6)
   Triangle(5)
	Triangle(4)
	  Triangle(3)
		Triangle(2)
		  Triangle(1)
			Triangle(0) <-- base case
		   Triangle(1) <-- prints 1 star & new line
		  Triangle(2) <-- prints 2 stars & new line
		Triangle(3) <-- prints 3 stars & new line
	  Triangle(4) <-- prints 4 stars & new line
	 Triangle(5) <-- prints 5 stars & new line
  Triangle(6) <-- prints 6 stars & new line
Triangle(7) <-- prints 7 stars & new line

Notice

Recursive function always has:

• recursive part (contains one or more recursive calls)
• base case (handles a simple input that can be solved without resorting to a recursive call)

For Fibonacci numbers, the base case is when n == 0 and n==1, then the program returns 1 without any further recursive calls.

Note: Recursive programs must always have a base case!

Recursion in linked lists

struct node
{ 
	int n; 			// some data struct
	node *next; 	// pointer to another struct node
};

typedef struct node *LIST;

.....
void printList(LIST lst)
{ 
	if (!isEmpty(lst)) 	// base case
	{ 
		printf ("%d ", lst->n ); // print integer followed by //space
		printList ( lst->next ); // recursive call
	}
}

Recursion in binary tree

struct node
{ 
	int n; // some data
	struct node *left; // pointer to the left subtree
	struct node *right; // point to the right subtree
};

typedef struct node *TREE;

// Inorder printout of the binary tree :
void printTree(TREE t)
{ 
	if (!isEmpty(t)) { // base case
		printTree(t->left); // go to the left
		printf("%d ", t->n); // print the integer followed by a //space
		printTree(t->right); // go to the right
	}
}

Advantages of Recursion

Simplifies Code: Recursion can make complex algorithms easier to understand and implement, particularly for problems like tree traversal, divide and conquer, and backtracking.

Natural Fit for Divide and Conquer: Many algorithms, such as MergeSort and QuickSort, work naturally with recursion.

Elegant and Concise: Recursive solutions are often more concise and elegant than their iterative counterparts, especially for problems that involve repetitive subproblems.

Disadvantages of Recursion

Memory Usage: Recursive functions use more memory due to the overhead of maintaining a function call stack. This can lead to stack overflow if the recursion depth is too high.

Performance: In some cases, recursion may lead to redundant computations (e.g., in the naive Fibonacci function), which can be inefficient.

Recursion is a powerful programming technique that allows you to solve problems by breaking them down into smaller subproblems. While it can simplify the code and be a natural fit for many problems, recursion should be used carefully, as it may lead to performance issues if not implemented efficiently.