Return value of recursive function

Base condition in recursion is the condition which stops the recursion.

The return value of base condition should be retained in the recursive programming, so that return value can be returned in the caller.

The below program doesn't retain the return value. So, let's see what happens.

/*                      78 
 *            23                  89
 *      5            76      88        97
 *         13     56                       100
 *
 */

#include <stdio.h>
#include <string.h>
#define NUM_OF_NODES 10

typedef struct tree_n {
   int data;
   struct tree_n *left;
   struct tree_n *right;
} tree_t;

tree_t *create_node(int num)
{
   tree_t *node = (tree_t *)malloc(sizeof(tree_t));
   node->data = num;
   node->left = NULL;
   node->right = NULL;
   return node;
}

int search_node(tree_t *root, int num, tree_t **parent)
{
    if (num == root->data) {  //base condition
        printf("\nThe number is %d",num);
        return 1;
    } else {
        *parent = root;
        if (num < root->data) {
            search_node(root->left, num, parent);           
        } else {
            printf("\nRight : The number to search is %d", (*parent)->data);
            search_node(root->right, num, parent);            
        }
    }       
    return 0;
}


void insert(tree_t **root, int num)
{
   
   if (*root == NULL) {  //base condition
       tree_t *node = create_node(num);
       *root = node;
   } else {
       if (num < (*root)->data) {
           insert(&((*root)->left), num);
       } else {
           insert(&((*root)->right), num);
       }
   } 
   return;
}

int main ()
{
   tree_t *root = NULL, *parent = NULL;
   int iterator = 0, found = 0;
   int a[] = {78, 23, 76, 56, 5, 13, 89, 88, 97, 100};
   while (iterator < NUM_OF_NODES) {
       insert(&root, a[iterator++]);
   }
   found = search_node(root, a[NUM_OF_NODES-1], &parent);
   if (found) {
       printf("\nThe searched number is found, and its parent is %d", parent->data);
   } else {
       printf("\nThe searched number is not found");
   }
   return 0;
}

Output:

Right : The number to search is 78 Right : The number to search is 89 Right : The number to search is 97 The number is 100 The searched number is not found

Here, the searched number is found already, but the return value is 0. Why?

I missed adding the return value whenever the function is called. In the below program, this is resolved.

/*                      78 
 *            23                  89
 *      5            76      88        97
 *         13     56                       100
 *
 */

#include <stdio.h>
#include <string.h>
#define NUM_OF_NODES 10

typedef struct tree_n {
   int data;
   struct tree_n *left;
   struct tree_n *right;
} tree_t;

tree_t *create_node(int num)
{
   tree_t *node = (tree_t *)malloc(sizeof(tree_t));
   node->data = num;
   node->left = NULL;
   node->right = NULL;
   return node;
}

int search_node(tree_t *root, int num, tree_t **parent)
{
   int result = 0;
   
   if (num == root->data) {
       return 1;
   } else {
       *parent = root;
       if (num < root->data) {
           search_node(root->left, num, parent);           
       } else {
           result = search_node(root->right, num, parent);           
       }
   }       
   return result;
}


void insert(tree_t **root, int num)
{
   
   if (*root == NULL) {
       tree_t *node = create_node(num);
       *root = node;
   } else {
       if (num < (*root)->data) {
           insert(&((*root)->left), num);
       } else {
           insert(&((*root)->right), num);
       }
   } 
   return;
}

int main ()
{
   tree_t *root = NULL, *parent = NULL;
   int iterator = 0, found = 0;
   int a[] = {78, 23, 76, 56, 5, 13, 89, 88, 97, 100};
   while (iterator < NUM_OF_NODES) {
       insert(&root, a[iterator++]);
   }
   found = search_node(root, a[NUM_OF_NODES-1], &parent);
   if (found) {
       printf("The searched number %d is found, and its parent is %d", 
              a[NUM_OF_NODES-1], parent->data);
   } else {
       printf("The searched number is not found");
   }
   return 0;
}

Output:

The searched number 100 is found, and its parent is 97

Stack Overflow Problem

When a program runs out of memory in the call stack, we call it as stack overflow.

#include <stdio.h>
#define FACTORIAL_NUM 5

int fact(int n)
{
    /* Dangerous base condition which causes stack overflow */
    if (n > 100) {
        return 1;
    } else {
        printf("Value of n %d\n",n);
        return n*fact(n-1);
    }
}


int main()
{
   int result = 0;

   result = fact(FACTORIAL_NUM);
   return 1;
}

Output:

Value of n 5 Value of n 4 Value of n 3 Value of n 2 Value of n 1 Value of n 0 Value of n -1 Value of n -2 Value of n -3 Value of n -4 Value of n -5 Value of n -6 Value of n -7 Value of n -8 Value of n -9 Value of n -10 Value of n -11 Value of n -12 Value of n -13 Value of n -14 Value of n -15 Value of n -16 <Here, it prints till we get stack overflow> timeout

For any recursive calls, stack memory is needed.