CS 3343/3341
  Introduction to Algorithms  
Spring 2012
  Fibonacci Numbers:  
  Levels of Nesting of  
Recursive Calls

The Fibonacci numbers are the sequence F0 = 0, F1 = 1, F2 = 1, F3 = 2, F4 = 3, F5 = 5, F6 = 8, F7 = 13, .... They are defined recursively by:

This definition is used directly in the recursive functions below. In the code below, orange is used for comments, while the blue code keeps track of the level of nesting of recursive calls and prints the vertical lines indicating this level. Normally the functions in the C code below would have prototypes, but I wanted to match the two programs side-by-side. Without prototypes, the definitions must come before their use, so for example, the function levout needed to be defined before F. One uses prototypes to keep from having to worry about the order of function definitions.

Fibonacci Numbers
Java C
// Fib.java: calculate nth Fibonacci #
public class Fib {
   private int level = 0; // recursion level

   int f(int n) {
      if (n <= 1) return n;
      return f(n - 1) + f(n - 2);
   }

   void levout(int level) { // recurs level
      for( ; level > 1; level--)
         System.out.print("| ");
      System.out.print("+");
   }

   int F(int n) {

      int val1, val2; // values returned
      level++;
      levout(level);
      System.out.println("Input: " + n);
      if (n <= 1) {
         levout(level);
         System.out.println("Return: " + n);
         level--;
         return n;
      }
      val1 = F(n - 1); // recursive call
      val2 = F(n - 2); // recursive call
      levout(level);
      System.out.println("Return: " +
         (val1 + val2));
      level--;
      return val1 + val2;
   }

   public static void main(String[] args) {
      Fib fib = new Fib();
      int n = Integer.parseInt(args[0]);
      System.out.println("f[" + n + "] = " +
         fib.f(n));
      System.out.println("F[" + n + "] = " +
         fib.F(n));
   }
}
// fib.c: calculate nth Fibonacci #
#include <stdio.h>


int f(int n) {
   if (n <= 1) return n;
   return f(n - 1) + f(n - 2);
}

void levout(int level) {
   for( ; level > 1; level--)
      printf("| ");
   printf("+");
}

int F(int n) {
   static int level = 0;
   int val1, val2;
   level++;
   levout(level);
   printf("Input: %i\n", n);
   if (n <= 1) {
      levout(level);
      printf("Return: %i\n", n);
      level--;
      return n;
   }
   val1 = F(n - 1);
   val2 = F(n - 2);
   levout(level);
   printf("Return: %i\n", val1 + val2);

   level--;
   return val1 + val2;
}

void main(void) {
   int n;
   scanf("%i", &n);
   printf("F[%i] = %i\n", n, f(n));

   printf("F[%i] = %i\n", n, F(n));
}

Common output
n = 1 to 4n = 5n = 6n = 7
f[1] = 1
+Input: 1
+Return: 1
F[1] = 1

f[2] = 1
+Input: 2
| +Input: 1
| +Return: 1
| +Input: 0
| +Return: 0
+Return: 1
F[2] = 1

f[3] = 2
+Input: 3
| +Input: 2
| | +Input: 1
| | +Return: 1
| | +Input: 0
| | +Return: 0
| +Return: 1
| +Input: 1
| +Return: 1
+Return: 2
F[3] = 2

f[4] = 3
+Input: 4
| +Input: 3
| | +Input: 2
| | | +Input: 1
| | | +Return: 1
| | | +Input: 0
| | | +Return: 0
| | +Return: 1
| | +Input: 1
| | +Return: 1
| +Return: 2
| +Input: 2
| | +Input: 1
| | +Return: 1
| | +Input: 0
| | +Return: 0
| +Return: 1
+Return: 3
F[4] = 3
f[5] = 5
+Input: 5
| +Input: 4
| | +Input: 3
| | | +Input: 2
| | | | +Input: 1
| | | | +Return: 1
| | | | +Input: 0
| | | | +Return: 0
| | | +Return: 1
| | | +Input: 1
| | | +Return: 1
| | +Return: 2
| | +Input: 2
| | | +Input: 1
| | | +Return: 1
| | | +Input: 0
| | | +Return: 0
| | +Return: 1
| +Return: 3
| +Input: 3
| | +Input: 2
| | | +Input: 1
| | | +Return: 1
| | | +Input: 0
| | | +Return: 0
| | +Return: 1
| | +Input: 1
| | +Return: 1
| +Return: 2
+Return: 5
F[5] = 5

f[6] = 8
+Input: 6
| +Input: 5
| | +Input: 4
| | | +Input: 3
| | | | +Input: 2
| | | | | +Input: 1
| | | | | +Return: 1
| | | | | +Input: 0
| | | | | +Return: 0
| | | | +Return: 1
| | | | +Input: 1
| | | | +Return: 1
| | | +Return: 2
| | | +Input: 2
| | | | +Input: 1
| | | | +Return: 1
| | | | +Input: 0
| | | | +Return: 0
| | | +Return: 1
| | +Return: 3
| | +Input: 3
| | | +Input: 2
| | | | +Input: 1
| | | | +Return: 1
| | | | +Input: 0
| | | | +Return: 0
| | | +Return: 1
| | | +Input: 1
| | | +Return: 1
| | +Return: 2
| +Return: 5
| +Input: 4
| | +Input: 3
| | | +Input: 2
| | | | +Input: 1
| | | | +Return: 1
| | | | +Input: 0
| | | | +Return: 0
| | | +Return: 1
| | | +Input: 1
| | | +Return: 1
| | +Return: 2
| | +Input: 2
| | | +Input: 1
| | | +Return: 1
| | | +Input: 0
| | | +Return: 0
| | +Return: 1
| +Return: 3
+Return: 8
F[6] = 8
f[7] = 13
+Input: 7
| +Input: 6
| | +Input: 5
| | | +Input: 4
| | | | +Input: 3
| | | | | +Input: 2
| | | | | | +Input: 1
| | | | | | +Return: 1
| | | | | | +Input: 0
| | | | | | +Return: 0
| | | | | +Return: 1
| | | | | +Input: 1
| | | | | +Return: 1
| | | | +Return: 2
| | | | +Input: 2
| | | | | +Input: 1
| | | | | +Return: 1
| | | | | +Input: 0
| | | | | +Return: 0
| | | | +Return: 1
| | | +Return: 3
| | | +Input: 3
| | | | +Input: 2
| | | | | +Input: 1
| | | | | +Return: 1
| | | | | +Input: 0
| | | | | +Return: 0
| | | | +Return: 1
| | | | +Input: 1
| | | | +Return: 1
| | | +Return: 2
| | +Return: 5
| | +Input: 4
| | | +Input: 3
| | | | +Input: 2
| | | | | +Input: 1
| | | | | +Return: 1
| | | | | +Input: 0
| | | | | +Return: 0
| | | | +Return: 1
| | | | +Input: 1
| | | | +Return: 1
| | | +Return: 2
| | | +Input: 2
| | | | +Input: 1
| | | | +Return: 1
| | | | +Input: 0
| | | | +Return: 0
| | | +Return: 1
| | +Return: 3
| +Return: 8


| +Input: 5
| | +Input: 4
| | | +Input: 3
| | | | +Input: 2
| | | | | +Input: 1
| | | | | +Return: 1
| | | | | +Input: 0
| | | | | +Return: 0
| | | | +Return: 1
| | | | +Input: 1
| | | | +Return: 1
| | | +Return: 2
| | | +Input: 2
| | | | +Input: 1
| | | | +Return: 1
| | | | +Input: 0
| | | | +Return: 0
| | | +Return: 1
| | +Return: 3
| | +Input: 3
| | | +Input: 2
| | | | +Input: 1
| | | | +Return: 1
| | | | +Input: 0
| | | | +Return: 0
| | | +Return: 1
| | | +Input: 1
| | | +Return: 1
| | +Return: 2
| +Return: 5
+Return: 13
F[7] = 13

Revision date: 2011-11-26. (Please use ISO 8601, the International Standard Date and Time Notation.)