Programming for Engineers
Lecture 4: Fuction & Recursion
Course ID: EE057IU
Lecture Outline
• Functions (Chapter 5)
• Recursion (Chapter 5.14)
School of Electrical Engineering EE057IU
Ho Chi Minh International University Page 2
Introduction
➢ Real world problems are larger, more complex
➢ Top down approach
➢ Modularize – divide and control
➢ Easier to track smaller problems / modules
➢ Repeated set of statements
School of Electrical Engineering EE057IU
Ho Chi Minh International University Page 3
Example: Area and circumference of a circle
School of Electrical Engineering EE057IU
Ho Chi Minh International University Page 4
Example: Computing Rim Area of a Flat Washer
School of Electrical Engineering EE057IU
Ho Chi Minh International University Page 5
Example: Computing Rim Area of a Flat Washer
School of Electrical Engineering EE057IU
Ho Chi Minh International University Page 6
Functions
➢ Functions allow us to
▪ Modularize a program
▪ Reuse the code (Avoid Reinventing the Wheel)
➢ Two types:
▪ Programmer/user write, called programmer-defined functions
▪ Prepackaged functions in C standard library
i
➢ Structure
▪ Input variables n
▪ Output value, which is returned p Function Result value
▪ Function body (series of statements)
u
School of Electrical Engineering EE057IU
Ho Chi Minh International University Page 7
Functions
➢Characteristics
▪ Can be called as many points in a program
▪ Be written only once
▪ The statements are hidden from other functions
➢Calling and Returnning from Functions
▪ Functions are invoked by a function call, which specifies the function name
and provides information (as arguments)
School of Electrical Engineering EE057IU
Ho Chi Minh International University Page 8
Functions – Modularizing Program
➢ Analogy: Hierarchical management
➢ A boss (the calling function or caller) asks a worker (the called
function) to perform a task and report back when the task is done
School of Electrical Engineering EE057IU
Ho Chi Minh International University Page 9
Functions – Math Library Functions (Chap 5.3)
➢C’s math library functions
(header math.h)
▪ Allow you to perform
mathematical calculations
▪ More complicated calculations
can be found in <complex.h>
School of Electrical Engineering EE057IU
Ho Chi Minh International University Page 10
Function Definitions
➢ Each program include a main function called standard library
functions
➢ All variable inside function called local variable, can accessed only
within function
➢ Each function has parameters to enable communication between
calling function and called function
Format of a function definition:
return-value-type function-name(parameter-list) {
statements
}
School of Electrical Engineering EE057IU
Ho Chi Minh International University Page 11
Example of User-defined Function
square Function
School of Electrical Engineering EE057IU
Ho Chi Minh International University Page 12
Function Definition – Analyzing
Function square is invoked or called
Function square
- receives parameter x
- Passes the variable x to calculate the statement number*number
School of Electrical Engineering EE057IU
Ho Chi Minh International University Page 13
Function Definition – Analyzing
Function square
- x in the iterations is defined as typedef int
- Function also expect the integer variable
School of Electrical Engineering EE057IU
Ho Chi Minh International University Page 14
Function Definition – Analyzing
Function square
(1) Perform the calculation inside the statement
(2) Pass the value back to calling function via return
(3) Keyword int at the beginning of function indicate
function need to return an integer to calling function
School of Electrical Engineering EE057IU
Ho Chi Minh International University Page 15
Function Definition – Analyzing
Function prototype
- Informs the compiler that square expects to
receive an integer variable from the caller
- Informs compiler that square return an
integer result to the caller
School of Electrical Engineering EE057IU
Ho Chi Minh International University Page 16
Function Definition … continue
➢ The compiler refers that
▪ Correct return type
▪ Correct number of arguments return-value-type function-name(parameter-list) {
▪ Correct argument types statements
}
▪ Arguments are in correct order
➢The function-name is any valid identifier.
➢ The return-value-type is the data type of the result returned to the caller.
➢The return-value-type void indicates that a function does not return a
value.
➢Together, the return-value-type, function-name and parameter-list are
sometimes referred to as the function header
School of Electrical Engineering EE057IU
Ho Chi Minh International University Page 17
Function Definition … continue
➢ The parameter-list is a comma-separated list that specifies the
parameters received by the function when it’s called.
➢If a function does not receive any values, parameter-list is void.
➢A type must be listed explicitly for each parameter.
➢The definitions and statements within braces form the function body,
which is also referred to as a block.
➢Variables can be declared in any block, and blocks can be nested.
School of Electrical Engineering EE057IU
Ho Chi Minh International University Page 18
Function Definition – Return Control
➢Returns control to calling function after function execution
▪ when a function is called, the program's execution jumps to that
function. When the function is finished, execution must jump back
to the exact place where it was called.
▪ For, void function, it simply executes all statements in its body.
Once the closing brace (}) of the function is reached, control
automatically returns to the calling function
▪ The statement return; It can be placed anywhere in the function
body to stop execution early. It does not send any data back.
▪ Returns the value of the expression to the caller by the statement
- return expression;
School of Electrical Engineering EE057IU
Ho Chi Minh International University Page 19
Function Definition – main() ‘s Return type
➢ main has an int return type.
➢ The return value of main is used to indicate whether the program
executed correctly.
➢ In earlier versions of C, we had to explicitly place
return 0;
➢ at the end of main — 0 indicates that a program ran successfully.
➢ main implicitly returns 0 if we omit the return statement.
➢ We can explicitly return non-zero values from main to indicate that a
problem occurred during your program’s execution.
School of Electrical Engineering EE057IU
Ho Chi Minh International University Page 20
Example of User-defined Function
maximum Function
School of Electrical Engineering EE057IU
Ho Chi Minh International University Page 21
In-class Practice
Write a program that inputs a series of integers and passes them one at a time to
function isEven, which uses the remainder operator to determine whether an
integer is even. The function should take an integer argument and return 1 if the
integer is even and 0 otherwise.
School of Electrical Engineering EE057IU
Ho Chi Minh International University Page 22
Random-Number Generation (Chap 5.10)
➢ Why we need random-number generation?
▪ Simulation, modeling, games, sampling and statistics, testing and debugging
▪ Game: a program that can simulate coin tossing “head” or “tail”
▪ Game: a program that can simulate dice-rolling game that provides randomly
6 integers 1 to 6.
➢ rand function
▪ Defined in <stdlib.h> header
▪ Syntax: i = rand();
▪ Get a random number in a range [0, N]: i = rand() %N;
School of Electrical Engineering EE057IU
Ho Chi Minh International University Page 23
Scaling and Shifting
RAND_MAX: At least 32767
School of Electrical Engineering EE057IU
Ho Chi Minh International University Page 24
Random Number Generation Code
School of Electrical Engineering EE057IU
Ho Chi Minh International University Page 25
rand() is not truly random
• When the program starts, the seed establishes the starting point for a very long, predetermined
sequence of pseudo-random numbers.
• Every time rand() is called in the program, it computes and returns the next number in that
sequence.
• That's why when you call rand() 3 times, it returns 3 different values (the 1st, 2nd, and 3rd
numbers in the sequence), but when you stop and recompile the code, run it again, it keeps
giving out the same 3 numbers (because the starting seed defaults to 1 and the sequence is the
same)
Run again Run again
School of Electrical Engineering EE057IU
Ho Chi Minh International University Page 26
𝑠𝑟𝑎𝑛𝑑 – Randomizing with a seed
• Function srand() takes an int argument and seeds function rand to
produce a different sequence of random numbers for each program
execution.
Try this as a better solution for random
number generator
#include <time.h>
srand(time(NULL));
School of Electrical Engineering EE057IU
Ho Chi Minh International University Page 27
Recursion (Chap 5.14)
➢ A recursive function is a function that calls itself either directly or
indirectly through another function.
➢ Nature of recursion
▪ One or more simple cases of the problem have a straightforward,
nonrecursive solution.
▪ The other cases can be redefined in terms of problems that are closer to the
simple cases.
School of Electrical Engineering EE057IU
Ho Chi Minh International University Page 28
Recursively Calculating Factorials
➢ The factorial of a non-negative integer n:
▪ n! (pronounced “n factorial”)
▪ n · (n – 1) · (n – 2) · … · 1
▪ 1! equal to 1, 0! defined to be 1
➢A recursive definition of the factorial function can be observed by the
relationship
▪ n! = n · (n – 1)!
▪ For example: 5! = 5 · 4 · 3 · 2 · 1
5! = 5 · (4 · 3 · 2 · 1)
5! = 5 · (4!)
School of Electrical Engineering EE057IU
Ho Chi Minh International University Page 29
Recursive evaluation of 5!
School of Electrical Engineering EE057IU
Ho Chi Minh International University Page 30
Recursive factorial function
School of Electrical Engineering EE057IU
Ho Chi Minh International University Page 31
Recursive factorial function
School of Electrical Engineering EE057IU
Ho Chi Minh International University Page 32
Example Fibonacci Series by Recursion
➢ The Fibonacci series
▪ 0, 1, 1, 2, 3, 5, 8, 13, 21, …
▪ Begins with 0 and 1
▪ Each subsequent Fibonacci number = sum of previous two Fibonacci numbers
➢ The Fibonacci series may be defined recursively as follows:
fibonacci(0) = 0
fibonacci(1) = 1
fibonacci(n) = fibonacci(n – 1) + fibonacci(n – 2)
School of Electrical Engineering EE057IU
Ho Chi Minh International University Page 33
Recursive Fibonacci Function
School of Electrical Engineering EE057IU
Ho Chi Minh International University Page 34
Recursive Fibonacci Function
School of Electrical Engineering EE057IU
Ho Chi Minh International University Page 35
Recursive Fibonacci Function - Diagram
School of Electrical Engineering EE057IU
Ho Chi Minh International University Page 36
Recursion vs Iteration
➢Both iteration and recursion are based on a control statement:
Iteration uses a repetition statement; recursion uses a selection
statement.
➢ Both iteration and recursion involve repetition: Iteration explicitly
uses a repetition statement; recursion achieves repetition through
repeated function calls.
➢ Iteration and recursion each involve a termination test: Iteration
terminates when the loop-continuation condition fails; recursion when
a base case is recognized.
School of Electrical Engineering EE057IU
Ho Chi Minh International University Page 37
Recursion is expensive
➢ It repeatedly invokes the mechanism, and consequently the
overhead, of function calls.
➢ This can be expensive in both processor time and memory space.
➢ Each recursive call causes another copy of the function to be
created; this can consume considerable memory.
➢ The amount of memory in a computer is finite, so only a certain
amount of memory can be used to store stack frames on the function
call stack.
➢ If more function calls occur than can have their stack frames stored
on the function call stack, a fatal error known as a stack overflow
occurs
School of Electrical Engineering EE057IU
Ho Chi Minh International University Page 38
In-class Practice
1st Solution 2nd Solution
School of Electrical Engineering EE057IU
Ho Chi Minh International University Page 39