Recursion Overview

Recursion is a method of solving problems that involves breaking a problem down into smaller and smaller subproblems until you get to a small enough problem that it can be solved trivially. Usually recursion involves a function calling itself. While it may not seem like much on the surface, recursion allows us to write elegant solutions to problems that may otherwise be very difficult to program.

Assignment

Main goal is to compare difference between recursion vs iterative implementation. You must implement functions down bellow in given list using recursion:

• Factorial calculation more than 20!.
• Fibonacci sequence.
• Binary Tree traversal (also known as tree search) implement method for different traversals: InOrder, PreOrder, PostOrder.
• Ackerman function. More u will find here.
• Read selected directory files recursively by selected type for e.g. only “*.txt “ documents.

If its possible try to implement same algorithms: “Factorial, Fibonacci, Ackermar, Read files, Binary Tree traversal” without recursion. Else Write some explanation why is so hard to implement that algorithm.

Binary Tree traversals

NOTE. Visual studio or other IDE users: Here you will find more info how to configure dirent.h library.

Example Read all dirs and files

// read all dirs and files 
#include <stdio.h>
#include <dirent.h>
#include <stdio.h>
#include <string.h>

void listFilesRecursively(char *path);


int main()
{
  // Directory path to list files
  char path[100];

  // Input path from user
  printf("Enter path to list files: ");
  scanf("%s", path);

  listFilesRecursively(path);

  return 0;
}


/**
 * Lists all files and sub-directories recursively
 * considering path as base path.
 */
void listFilesRecursively(char *basePath)
{
  char path[1000];
  struct dirent *dp;
  DIR *dir = opendir(basePath);

  // Unable to open directory stream
  if (!dir)
    return;

  while ((dp = readdir(dir)) != NULL)
  {
    if (strcmp(dp->d_name, ".") != 0 && strcmp(dp->d_name, "..") != 0)
    {
      printf("%s\n", dp->d_name);

      // Construct new path from our base path
      strcpy(path, basePath);
      strcat(path, "/");
      strcat(path, dp->d_name);

      listFilesRecursively(path);
    }
  }

  closedir(dir);
}