Introduction to Computer Programming (C language) - Chapter 6: Functions - Võ Thị Ngọc Châu

Nội dung text: Introduction to Computer Programming (C language) - Chapter 6: Functions - Võ Thị Ngọc Châu

1. Ho Chi Minh City University of Technology Faculty of Computer Science and Engineering Chapter 6: Functions Introduction to Computer Programming (C language) TS. Võ Thị Ngọc Châu (chauvtn@cse.hcmut.edu.vn, chauvtn@hcmut.edu.vn) 2017 – 2018, Semester 2
2. Course Content C.1. Introduction to Computers and Programming C.2. C Program Structure and its Components C.3. Variables and Basic Data Types C.4. Selection Statements C.5. Repetition Statements C.6. Functions C.7. Arrays C.8. Pointers C.9. File Processing 2
3. References [1] “C: How to Program”, 7th Ed. – Paul Deitel and Harvey Deitel, Prentice Hall, 2012. [2] “The C Programming Language”, 2nd Ed. – Brian W. Kernighan and Dennis M. Ritchie, Prentice Hall, 1988 and others, especially those on the Internet 3
4. Content Introduction Functions in the standard library An example of a function Components of a function Function call Recursion Summary 4
5. Introduction In the previous chapters, we have used several so-called functions in the library:  printf in stdio.h Those functions are modular  scanf in stdio.h processing units that are:  fflush in stdio.h Responsible for a  sqrt in math.h certain task  pow in math.h  system in stdlib.h Reusable in many  strcmp in string.h various programs  strcpy in string.h 5
6. Functions in the standard library Source: www.tutorialspoint.com 6
7. Functions in the standard library Some functions in  int printf(const char *format, ) Sends formatted output to stdout  int scanf(const char *format, ) Reads formatted input from stdin  int getchar(void) Gets a character (an unsigned char) from stdin  char *gets(char *str) Reads a line from stdin and stores it into the string pointed to, by str. It stops when either the newline character („\n‟) is read or when the end-of-file (EOF) is reached, whichever comes first. 7
8. Functions in the standard library Some functions in  double cos(double x) Returns the cosine of a radian angle x  double pow(double x, double y) Returns x raised to the power of y  double sqrt(double x) Returns the square root of x  double ceil(double x) Returns the smallest integer value greater than or equal to x  double floor(double x) Returns the largest integer value less than or equal to x 8
9. Functions in the standard library Some functions in  void *malloc(size_t size) Allocates the requested memory and returns a pointer to it  void free(void *ptr) Deallocates the memory previously allocated by a call to calloc, malloc, or realloc  int rand(void) Returns a pseudo-random number in the range of 0 to RAND_MAX (at least 32767, up to implementation)  int system(const char *string) The command specified by string is passed to the host environment to be executed by the command processor . E.g. “pause”, “cls”, “date” 9
10. Introduction Repeated code!!! Can we just code them once and then make use of them over the time just like those in the standard library? 10
11. Introductions Let‟s define a function: getNaturalNumber() Declared in a header file C6_function_getNaturalNumber_1.h for multiple uses Source code file: C6_function_getNaturalNumber.c Purpose: to ask users to input a natural number until a valid number is input 11
12. Use of our previously defined function, which is declared in a header file: “C6_function_getNaturalNumber_1.h” Compile: gcc C6_starTriangle_function_1.c C6_function_getNaturalNumber.c –o C6_starTriangle_function_1.exe 12
13. Introduction A function  A processing unit to perform a specific task  A means to modularize a program for manageable program development C Program 1 C Program 2 main() main() Divide-and-conquer function1() function1() Reusable Information hiding function2() function3() Abstraction Easy for debugging 13
14. Introduction Issues related to functions  Function definition  Function declaration  Function call 14
15. An example of a function Prepare your own library for numbers  Compute the sum of N first natural numbers sum = 1 + 2 + 3 + + (N-1) + N  Compute the factorial of N, a natural number factorial = 1*2*3* *(N-1)*N  Compute the n-th power of x, a floating-point number xn = x*x*x* *x  Count the number of digits in N, a natural number N = 123456 => Number of digits = 6  Round x, a floating-point number, with two digits after the decimal point x = 1.23456 => x = 1.23 x = 9.87654321 => x = 9.88 15
16. An example of a function Prepare your own library for numbers  Check if a natural number is a prime number 7 => true ( 0) 8 => false (0)  Check if a natural number is a squared number 4 => true ( 0) 8 => false (0)  Toggle non-zero digits to „9‟ digits in an integer number to generate its 9-based mask 113789 => 999999 -10789 => -90999  Count the number of occurrences of each digit in an integer number 113789 => 0: 0; 1: 2; 2: 0; 3: 1; 4: 0; 5: 0; 6: 0; 7: 1; 8: 1; 9: 1 -20054 => 0: 2; 1: 1; 2: 1; 3: 0; 4: 1; 5: 1; 6: 0; 7: 0; 8: 0; 9: 0
17. An example of a function Prepare your own library for numbers  Estimate a value of e, the natural number  Estimate a value of ex  Estimate a value of PI  17
18. Components of a function Given N, a natural number, calculate the factorial of N: N! = 1*2* *N = (N-1)!*N 18
19. Components of a function Given N, a natural number, calculate the factorial of N: N! = 1*2* *N = (N-1)!*N Parameter list Function Return with comma body that type separation. includes Function which is No default declarations name a data value for each and type of parameter in C statements the value functions. performed returned for a return statement to return a specific task value of a return type to the caller 19
20. Components of a function [static] return-type function-name (argument-declarations) { declarations and statements } - function-name: a valid identifier - argument-declarations: a list of formal parameters in communication Part + Each parameter is regarded as a local variable with a data type. of the + Each parameter can be specified with “const” for unchanged intention. input + Each parameter can be passed by value or by reference if it is a pointer. Process - declarations: a list of local variables ing in + Each variable can be auto or static with one single initialization. its body - statements: zero, one, or many statements of any kind - return-type: a valid data type or void Part + Statement return [ ]; in the body is used to end the of the output called function and return [a value] to its caller. If not, close brace of the body ends the called function and program control is switched to its caller. - [static]: optional specification to make the function available only in the file Charac teristic where it is defined. 20
21. Concepts related to functions Function definition: [static] return-type function-name (argument-declarations) { declarations and statements } Function prototype: return-type function-name (argument-declarations); Function signature: [extern] return-type function-name (argument-declarations) No concept of “nested functions”!  Implementation-dependent 21
22. Where is a function defined and declared? A function definition can be placed in:  the same file where the main() function is Before the main() function After the main() function  a separated file where the main() function is not Regardless of where a function is defined, its declaration is required before any call to it.  Function prototype in the global declaration section  Function prototype in a header file for common use 22
23. A program for an approximation of the x-th power of e Function definition = Function declaration (as it is placed before its call) Function declaration a call to a function Function definition (a function declaration is required as it is placed after its call.) 23
24. Where is a function defined and declared? SEPARATED FILES Function declaration Function definition Function calls 24
25. Where is a function defined and declared? Source file getFactorial.c 25
26. Where is a function defined and declared? Source file getPower.c 26
27. Where is a function defined and declared? Header file for common use mynumber.h 27
28. Function call Function call is a mention of a function to another function or itself.  The function whose function body contains a a mention is called a calling function or a caller.  The function whose name is mentioned in the caller‟s function body is called a called function or a callee.  The caller is the same as or different from the callee. The program in C6_function_myNumber  The main() function calls the printf(), scanf(), pow(), factorial(), and power() functions. Caller = main Callees = printf, scanf, pow, factorial, power 28
29. Function call A function call is mentioned in the function body of the caller as: function-name (argument-list)  argument-list Optional, i.e. empty if the callee has no argument Each argument is called actual parameter which is an expression corresponding to a formal parameter by order. Each argument has a type compatible with the type of its corresponding formal parameter. Otherwise, type conversion with promotion or truncation is performed. Assignment of each expression value to the corresponding formal parameter‟s memory is performed.  A value of a return type (if it is not void) is returned via this function call. 29
30. Stack‟s values when i=0 in the Function call main() function Caller‟s stack Callee‟s stack 0 i 2 x 10 n 0 n 2 x i 0 e_x aPower The caller The callee 30
31. Function call Function call by value  Parameters are passed by value. The actual parameter values are copied into local storage of the formal parameters of the callee.  The caller and callee do not share any memory. Function call by reference  C has no explicit reference parameters but implements them via pointers, i.e. address passing.  Pointers are passed to the arguments. There is only one copy of the value at any time.  The caller and callee have access to the value in their shared memory through pointers. 31
32. Function call A function to swap two integer numbers void swap(int a, int b){ int temp; a and b will be passed by temp = a; values of int type. a = b; b = temp; } void swap(int *a, int *b){ int temp; temp = *a; a and b will be passed by pointers *a = *b; to int values, i.e. addresses of the memory that contains int values. *b = temp; } 32
33. Function call by value Change on formal parameters in the callee has no impact on actual parameters in the caller. 33
34. Function call by value Stack‟s values when a=10 and b=9 in the main() function Caller‟s stack Callee‟s stack 10 a 10 a 9 b 9 b temp Stack‟s values before the callee ends Callee‟s stack 9 a 10 b 10 temp 34
35. Function call by reference Change on the shared memory can be made by both callee and caller. Pointers are used for reference. 35
36. Function call by reference Stack‟s values when a=10 and b=9 in the main() function Caller‟s stack Callee‟s stack 000000000022FE4C 10 a &a 000000000022FE4C a 000000000022FE48 &b 9 b 000000000022FE48 b temp Stack‟s values before the callee ends Caller‟s stack Callee‟s stack 000000000022FE4C 9 a &a 000000000022FE4C a 000000000022FE48 &b 10 b 000000000022FE48 b 10 temp 36
37. Recursion A recursive function is a function that calls itself either directly or indirectly. When a function calls itself recursively, each invocation gets a fresh set of all the automatic variables, independent of the previous set. Function to compute the factorial of n: non-recursive vs. recursive versions 37
38. rFactorial(10) rFactorial(10) 3628800 Recursion path 10*rFactorial(9) 10*9* 8*7*6*5*4*3*2*1*1 9*rFactorial(8) 9* 8*7*6*5*4*3*2*1*1 8*rFactorial(7) 8*7*6*5*4*3*2*1*1 7*rFactorial(6) 7*6*5*4*3*2*1*1 6*rFactorial(5) 6*5*4*3*2*1*1 5*rFactorial(4) 5*4*3*2*1*1 4*rFactorial(3) 4*3*2*1*1 3*rFactorial(2) 3*2*1*1 2*rFactorial(1) 2*1*1 Recursive cases with smaller sizes 1*rFactorial(0) 1*1 Return path 1 1 Base case 38
39. Recursion Writing a recursive function  Determine and write the base cases and their solutions No recursive call is specified for those base cases.  Determine and write the recursive (inductive) cases and their solutions Establish a connection between the larger problem and the smaller problems using recursive calls  Determine the other cases that are neither base nor recursive cases Check for other constraints with no recursive call 39
40. Recursion Compute the sum of N first natural numbers  sum = 1 + 2 + 3 + + (N-1) + N Base case: sum(1) = 1 Recursive case: sum(N) = sum(N-1) + N Compute the factorial of N, a natural number  factorial = 1*2*3* *(N-1)*N Base case: factorial(0) = factorial(1) = 1 Recursive case: factorial(N) = factorial(N-1)*N Compute the n-th power of x, a floating-point number  xn = x*x*x* *x Base case: power(x, 0) = 1 Recursive case: power(x, n) = power(x, n-1)*x 40
41. Recursion Estimate a value of e, the natural number  Base case: e(0) = 1  Recursive case: e(n) = e(n-1) + 1/factorial(n) 41
42. Recursion Estimate a value of ex  Base case: e_x(0) = 1  Recursive case: e_x(n) = e_x(n-1) + power(x, n)/factorial(n) 42
43. Recursion Estimate a value of PI  Base case: pi(0) = 4  Recursive case: pi(k) = pi(k-1) + power(-1, k)*4/(2*k+1) 43
44. Recursion Hanoi Tower Move disks from peg 1 to peg 3 using peg 2 as a temporary holding area in such a way that smaller disks are always on top of larger disks and one disk peg 1 peg 2 peg 3 is moved at a time A recursive function with 4 parameters: a). The number of disks to be moved b). The peg on which these disks are initially threaded c). The peg to which this stack of disks to be moved d). The peg to be used as a temporary holding area 44
45. Recursion Hanoi Tower 45
46. Hanoi Tower peg 1 peg 2 peg 3 46
47. Recursion Recursive function‟s concern  No saving in storage  Not faster  Infinite recursion No base case is defined or base case can not be reached. Recursive function‟s advantages  Compact recursive code  Easy to write and understand  Convenient for recursively defined data structures and problems 47
48. Summary A function is a processing unit for a specific task.  Divide-and-conquer approach  Reusability  Information hiding  Abstraction  Support for debugging Manageable program development 48
49. Summary Function definition Function declaration Function call  By value  By reference with pointer implementation Recursion  Recursive problem  Recursive data structure 49
50. Chapter 6: Functions 50