Fibonacci Sequence using Recursion - C Program

Problem Question

Write a Recursive Function to obtain first 25 numbers of a Fibonacci Sequence. In a Fibonacci sequence, the sum of two successive terms gives the third term. Following are the first few terms of the Fibonacci Sequence:

1 1 2 3 5 8 13 21 34 55 89...

Explanation of Problem

The problem is simple enough and we just need to print the first 25 terms of the Fibonacci sequence using a recursive function. But I have written a rather general program which could generate the Fibonacci sequence upto nth term. All you need to do is, supply 25 as the input and you will get the first 25 terms.

Code

#include <stdio.h>
/**@Title: RecursiveFibonacci.c*
*@Language: ANSI C*
*@Compiler: GNU GCC*
*@IDE: Code::Blocks 13.12*
*@Author: Toxifier*
*@URL: http://letsplaycoding.blogspot.com/*
*@Date: 31-05-2014*
*/

int recFibo(int a1, int a2, int num)
{
  if (num)
  {
    printf("%d ", a1);
    return recFibo(a2, a1 + a2, num - 1);
  }
  return 0;
}

int main()
{
  int number;
  printf("\n\nEnter a number: ");
  scanf("%d", &number);
  recFibo(1, 1, number);
  printf("\n\n");
  system("pause");
  return 0;
}

Explanation of Code

#include <stdio.h> -> This is the step which occurs before compilation starts. The compiler calls the C Preprocessor to include the STDIO(Standard Input Output) header file into the program, thus letting the use of the standard input/output functions like printf() and scanf() which come from STDIO.H

int main() -> The entry point of the program where the execution starts. This function has to be named main. As per the ANSI specification, the return type has to be int. If you use the traditional C, you may use void as the return type. Since the return type is specified as int in my program, I have to use a return statement at the end of my code. So I use return 0 since zero returned from a function, by convention, implies a correct execution of the program. The return values are used to debug the program.

printf() -> This is a standard output function used to print something on the screen. We have to pass a string to this function which will be displayed on user's terminal.

scanf() -> This is the scanf() function which waits for the user to enter certain value using his/her keyboard. We store the user input at the location in memory which is pointed to by the variable whose address is passed to this function.

recFibo(1, 1, number); -> This is the call to the recursive function we have designed in this program. Just pass 25 as the value of the variable number to get the sequence upto 25 terms. Else he program is generalised to get results upto nth term (as long as the result is within the range of int, memory & computational power).

int recFibo(int a1, int a2, int num) -> The function that calculates the Fibonacci Sequence. It's input are two successive terms, a1 and a2 which are used to compute the next term. The variable num is the number of times we wish to call this function.

if (num) -> The statement makes sure that the block is executed only if the value of num is non zero. As soon as the value becomes zero, the block is not executed. Please note that on encounter of a negative number, we will get unfavourable results. The program is designed to handle positive int only. In case you wish to handle the negative number situation, you can use, if (num > 0).

printf("%d ", a1); -> Prints the first term. We could have also used a1 + a2, but then we will not able to produce 1 1 in the beginning. So while calling the function from main, if you rather use recFibo(0, 1, number);, then you can use, printf("%d ", a1 + a2); instead.

return recFibo(a2, a1 + a2, num - 1); -> This is the most important line in this program which makes recursive call to the function recFibo. Please note, we have supplied the second term, and third term of any three terms in sequence in this call. Also, we decrement num by 1 on each recursive call, so that our if condition gets violated at right time and the program terminates at the right time.

system("pause") -> This statement is used to pause the program, until user presses a key. This function is not necessary in your program, I use it to see my outputs paused. If you use cmd to run your programs, you might not need this. If you use linux/unix you might not need this. Depending on your compiler, this function may or may not work. Moreover, removing this line of code from this program, doesn't affect the functionality of the program.

Output(s)

Download Source Code

Fibonacci Series upto n terms – Linux Shell Script

Problem Question

Write a script to print the Fibonacci series upto n terms

Explanation of Problem

Here we wish to write a Linux Shell Script that takes a command line parameter which denotes upto which term we wish to generate Fibonacci series, and generate the same.

Code

#*Fibonacci Series*
#@Shell: Bash
#@Author: Toxifier
#@URL: http://letsplaycoding.blogspot.com/
#@Date: 17-03-2014
f1=0
f2=1
echo""
echo "Fibonacci sequence for n=$1 is : "
echo""
for (( i=0;i<=$1;i++ ))
 do
  echo -n "$f1 "
  fn=$((f1+f2))
  f1=$f2
  f2=$fn
 done
echo " "
echo""

Explanation of Code

Please note the number of whitespaces in the above script. In Linux Shell Scripts, a single extra whitespace could lead to hours of unnecessary debugging like a missing semicolon in a C program.

f1=0 f2=1 -> The first two terms of the Fibonacci Series(fixed).

echo"" -> Used to print a blank line

$1 -> The first command line argument

echo -> Linux shell command used to display the string following it to the standard output terminal display.

for (( i=0;i<=$1;i++ )) -> For loop used to loop with the code that calculates and prints the next term.

echo -n "$f1 " -> The ‘-n’ option of echo command makes the output to print in the same line. Please note a single whitespace after ‘$f1’ that I have used so that the terms are well separated.

fn=$((f1+f2)) -> We declare a variable ‘fn’ and assign it the value of expression ‘(f1+f2)’

f1=$f2 f2=$fn -> f1 is given the value of f2, and f2 the value of the new term we just found. Actually in Fibonacci series, the new term is calculated as the sum of previous two terms. Thus, we need a track of previous two terms, for which we use f1 and f2.

do done -> for loop delimiters

Output(s)