Function and Recursion

FUNCTION AND RECURSION

SUB TOPICS :

• Modular Programming
• Function
• Identifier Scooping
• Passing Parameter
• Recursion Definition
• Recursive Function
• Iterative vs Recursive

Pointer Definition

•       Program is divided into modules

•       Module in C programming language is implemented using function

•       Function is formed through grouping some statements to do a particular job

•       Module is needed when a certain block of statement frequently used by other distinct code in a program

•       Also called Sub-Program

 •       Advantages of using Modules:

1.    Top-down design with sub goal, huge program divided into smaller modules

2.    Can be done by more than one developer/ programmer

3.    Easier to debug, as logical flow is easy to follow and easier to pin point errors

4.    Modification can be done without affecting overall codes

5.    Easier to document

 •       Function in C divided in two types :

–      Library function

–      User-defined function

–      Library function, is a standard function provided by C compiler. Those function described in the header files (.h)

            Example:        strcpy() in string.h

                                    sqrt() in math.h

                                    printf() in stdio.h

•       User-defined function is self defined functions

Function Definition

Function Construction

           return-value-type  function-name( parameter-list )

           {
   statements;

           }

return-value-type:  data type of the value returned

•       If not filled, then default data type will be used (default integer)

•       If return-value-type is void then the function will not return value

Parameter-list: list of value sent from the function initiator (user)

 Function in C usually written above the initiator/caller or main program. Otherwise should use Function Prototype

Function Prototype Objective:

•       To ensure a function is known by the initiator/caller

•       Compiler  will validate the parameters

Syntax :

            return-value-type  function-name ( parameter-list );

 Example:

#include <stdio.h>

int maximum (int x, int y){

      int max = x;

      if ( y > max) max = y;

      return max

}

void main () {

     int a,b;

     printf("Input 2 even values : ");

     scanf("%d %d", &a, &b);

     printf("Largest value : %d\n",maximum(a,b));

}

Identifier Scooping

Local Identifier

•       Identifier declared in a function including the parameters

•       Scope limited in the function

Global Identifier

•       Identifier declared outside any function and placed on top of all functions in a C program

•       Reachable from any point in the program

•       Global Identifier, can be re-declared in subprogram

•       It is advisable not to use global variable for the following reasons:

–      Error rate might increase as line of code increase.

–      Difficult in debugging

–      Exclusivity of data is low. All functions in the program can change its value

Passing Parameter

If a module is not self sufficed then needed data/value and its result passes in and out using parameter(s)

List of parameters is the interface of a module with other modules

Passing Parameter

–      By-Value, sent to other module is the value

–      By Location/by reference, sent to other module is the address

Recursive Definition

•       Recursive is a function call inside a certain function calling itself

•       Recursive Function, suitable for recursive problem

•       Example :

           Factorial (n) or n! defined as follows :

           n! = 1, for n = 0;

           n! = n * (n-1)!, for n > 0

           4! = 4 * 3!

           3! = 3 * 2!

           2! = 2 * 1!

           1! =  1* 0!

           0! =  1

           Trace back : 4! = 1*2*3*4 = 24

 Recursive Function has two components:

–      Base case:

            return value(constant) without calling next recursive call.

–      Reduction step:

            sequence of input value converging to the base case.

Example: (Factorial function)

–      Base case : n = 0

–      Reduction step: f(n) = n * f(n-1)

 Recursive vs Iterative 

• Factorial - Recursive

long factor (int n)

{

              if(n==0) return (1);

      else return(n * factor(n-1));

}

•       Factorial - Iterative

long factor(int n) {

                  long i, fac = 1;

                  for(i=1; i<=n; i++)  fac *= i;

                  return (fac);

}

Recursive Drawback

Although recursive code more concise it needs:

–      More memory consumption – as stack memory is needed

–      Takes longer time, should traverse through all recursive call using stack

Recursive Best Practice

Generally, use recursive solution if:

–      Difficult to solve iteratively.

–      Efficiency using recursive has been reached

–      Efficiency is less important in comparison with readability

–      Memory efficiency and execution time are not the main concern

Consider carefully speed and efficiency using iterative approach, rather than nice logical design using recursive

 Summary

•       Function is formed through grouping some statements to do a particular job

•       C programming language implements modular programming using function

•       Function in C divided in two types :

–      Library function

–      User-defined function

•       Recursive is a function call inside a certain function calling itself

2201760945

Skyconnectiva

Kevin Orlando Sutanto