Functions and Recursion: Call by Value vs Reference, Storage Classes and Recursive Programs · ফাংশন ও রিকার্সন: কল বাই ভ্যালু বনাম রেফারেন্স, স্টোরেজ ক্লাস ও রিকার্সিভ প্রোগ্রাম

1. What a function is

A function is a named, self-contained block of code that does one job. You write it once and call it wherever you need that job done. Functions make a program shorter (no repeated code), easier to read and test, and easier to change, because a fix in one place fixes every call. Every C program has at least one function, main(), where execution starts.

Point	Library (built-in) function	User-defined function
Written by	The compiler or library vendor	The programmer
Declared in	A header file (printf in <stdio.h>, sqrt in <math.h>, strlen in <string.h>)	The program itself
Can it be changed?	No, only used	Yes
Examples	printf, scanf, pow, strcpy	factorial, isPrime, swap

A function has four parts: the return type (int, double, or void for none), the name, the parameter list, and the body in braces.

2. Declaration, definition and call

#include <stdio.h>

int add(int a, int b);          /* declaration (prototype): ends with ; */

int main(void) {
    int s = add(3, 5);          /* call: 3 and 5 are the arguments */
    printf("%d\n", s);          /* prints 8 */
    return 0;
}

int add(int a, int b) {         /* definition: header plus body */
    return a + b;               /* a and b are the parameters */
}

• A declaration (prototype) tells the compiler the return type, name and parameter types: return-type function-name(argument types);. Parameter names are optional there (int add(int, int);). It is needed when a function is called before its definition.
• A definition is the header plus the body; a function may be declared many times but defined once.
• Formal parameters are the variables in the definition (a, b); actual parameters (arguments) are the values in the call (3, 5).
• A function returns at most one value through return. To hand back more, return a struct, or write the results through pointer parameters. A void function returns nothing. (In C++ and Java, a constructor has no return type at all.)
• Default return type: in C89, a function declared without a return type returns int by default (the usual keyed answer); C99 removed this "implicit int", so modern compilers warn or reject it. Standard C also does not allow one function to be defined inside another.
• In an expression such as a = func3(6) - func2(4, 5) / func1(1, 2, 3);, the order in which the three functions are called is unspecified in C: precedence decides how the results are combined, not which call runs first. The keyed answer is "cannot be predicted".

3. Call by value and call by reference

Call by value: the function receives a copy of each argument, so changing the parameter cannot change the caller's variable. This is the only way C passes arguments. Call by reference: the function works on the caller's own variable. C does this by passing the variable's address in a pointer; C++ also has true reference parameters (int &a).

Worked example 1: swap two integers.

#include <stdio.h>

void swapByValue(int a, int b) {        /* gets copies */
    int t = a; a = b; b = t;
}

void swapByReference(int *a, int *b) {  /* gets addresses */
    int t = *a; *a = *b; *b = t;
}

int main(void) {
    int x = 3, y = 7;
    swapByValue(x, y);
    printf("after swapByValue: %d %d\n", x, y);
    swapByReference(&x, &y);
    printf("after swapByReference: %d %d\n", x, y);
    return 0;
}

after swapByValue: 3 7
after swapByReference: 7 3

1. swapByValue(x, y) copies 3 and 7 into a and b. The copies are swapped and then thrown away, so x and y stay 3 and 7.
2. swapByReference(&x, &y) passes the addresses of x and y. Inside, *a is x and *b is y.
3. t = *a saves 3; *a = *b makes x = 7; *b = t makes y = 3.

Point	Call by value	Call by reference
What is passed	A copy of the value	The address of (or a reference to) the variable
Can the function change the caller's variable?	No	Yes
Memory	Extra copy of each argument	Only an address is copied
Safety	The original is protected	The original can be changed by mistake
C syntax	f(x) with void f(int a)	f(&x) with void f(int *a)

A past MCQ in this style: int fun(int *p) { *p = *p + 10; return *p; } called as fun(&x) with x = 5 returns 15, and x itself is now 15.

Neighbouring facts:

• Arrays are passed as a pointer to their first element (the base address), so a function can change the caller's array elements, and sizeof inside the function gives the pointer size, not the array size. Pass the length as another parameter.
• Java is always call by value. For an object, the value copied is the reference, so the method can change the object's fields but cannot make the caller's variable point to a new object. A Java method that swaps two int parameters therefore changes nothing in the caller.
• Python passes object references ("call by object reference"): a function can change a mutable argument in place (lst.append(4) is seen by the caller), but rebinding the name (x = 100) is not.

4. Scope, lifetime and storage classes

Scope is where in the code a name can be used; lifetime is how long the variable exists while the program runs. A local variable (declared in a function or block) is visible only there; a global variable (declared outside all functions) is visible in every function after it. When a local and a global have the same name, the local one hides (shadows) the global inside its block.

C has four storage classes:

Storage class	Where stored	Default initial value	Scope	Lifetime
auto (the default for locals)	Stack memory	Garbage (indeterminate)	The block	Until the block ends
register	A CPU register if possible (a hint)	Garbage	The block	Until the block ends
static	Static memory	0	The block (static local) or the file (static global)	The whole program
extern	Static memory	0	Global, across files	The whole program

The default storage class is auto for local variables and extern (external linkage) for global variables. (typedef is grouped with the storage-class specifiers in the C grammar only for syntax, and C11 added _Thread_local.)

static keeps a local variable's value between calls, which is the keyed answer to "to retain the values of variables between function calls, we should use …":

void counter(void) {
    static int c = 0;   /* initialized once, before the program starts */
    int d = 0;          /* auto: created again on every call */
    c++; d++;
    printf("c=%d d=%d\n", c, d);
}
/* calling counter() three times prints: c=1 d=1, c=2 d=1, c=3 d=1 */

Rules that exams check:

• You cannot take the address of a register variable: &r is a compile error.
• A declaration may have only one storage class, so register static int i = 10; does not compile ("multiple storage classes in declaration specifiers").
• extern int count; only declares a variable defined elsewhere (often in another file); it does not create one.
• A static global or static function is visible only inside its own source file.

5. Recursion: how a function can call itself

A recursive function calls itself to solve a smaller version of the same problem. Every correct recursion has two parts:

1. Base case: a case small enough to answer directly, which stops the recursion.
2. Recursive case: the function calls itself on a smaller input, moving toward the base case.

int factorial(int n) {
    if (n <= 1) return 1;            /* base case: 0! = 1! = 1 */
    return n * factorial(n - 1);     /* recursive case */
}

Each call gets its own stack frame (an activation record holding its parameters, local variables and return address) on the call stack, which is last in, first out. Calls go down until the base case (winding), then results come back up (unwinding):

So factorial(4) = 24, using 4 calls and at most 4 frames on the stack at once. Without a base case (or if it is never reached), frames pile up until the stack runs out: a stack overflow. Python stops this earlier with a RecursionError once the depth passes its default limit of 1000 (sys.getrecursionlimit()).

Kinds of recursion:

Kind	Meaning	Example
Direct	The function calls itself	factorial
Indirect	A calls B and B calls A	isEven / isOdd written in terms of each other
Tail	The recursive call is the last action	gcd(b, a % b)
Non-tail	Work remains after the call returns	n * factorial(n - 1)
Tree	More than one recursive call per call	fib(n - 1) + fib(n - 2)

6. The classic recursive functions

int fib(int n)         { if (n <= 1) return n; return fib(n - 1) + fib(n - 2); }
int gcd(int a, int b)  { return b == 0 ? a : gcd(b, a % b); }
double power(double x, int n) { if (n == 0) return 1; return x * power(x, n - 1); }
int sumDigits(int n)   { return n == 0 ? 0 : n % 10 + sumDigits(n / 10); }
int countDigits(int n) { return n < 10 ? 1 : 1 + countDigits(n / 10); }

Function	Base case	Recursive case	Checked result
Factorial	n ≤ 1 → 1	n × fact(n − 1)	fact(5) = 120, fact(0) = 1
Fibonacci	n ≤ 1 → n	fib(n − 1) + fib(n − 2)	fib(0 … 10) = 0 1 1 2 3 5 8 13 21 34 55
GCD (Euclid)	b = 0 → a	gcd(b, a mod b)	gcd(48, 18) = 6
Power xⁿ	n = 0 → 1	x × power(x, n − 1)	power(2.5, 3) = 15.625
Sum of digits	n = 0 → 0	n mod 10 + sum(n / 10)	sumDigits(3426) = 15
Number of digits	n < 10 → 1	1 + count(n / 10)	countDigits(5396) = 4
Tower of Hanoi	n = 0 → no move	move n − 1, move 1, move n − 1	3 discs → 7 moves

GCD trace: gcd(48, 18) → gcd(18, 12) → gcd(12, 6) → gcd(6, 0) → 6. If a < b the first call just swaps them: gcd(18, 48) → gcd(48, 18).

Fibonacci is slow when written this way, because it solves the same subproblems again and again: computing fib(n) makes 2 × fib(n + 1) − 1 calls. fib(4) makes 9 calls, fib(5) 15, fib(6) 25 and fib(10) 177 (all counted by running the code). The time grows exponentially; a loop, or storing results already found (memoization), computes it in linear time.

Worked example 2: Tower of Hanoi. Move n discs from peg A to peg C using peg B, moving one disc at a time and never putting a larger disc on a smaller one.

void hanoi(int n, char from, char to, char via) {
    if (n == 0) return;
    hanoi(n - 1, from, via, to);              /* move n-1 discs out of the way */
    printf("%d:%c->%c ", n, from, to);        /* move the largest disc */
    hanoi(n - 1, via, to, from);              /* put the n-1 discs back on top */
}
/* hanoi(3, 'A', 'C', 'B') prints:
   1:A->C 2:A->B 1:C->B 3:A->C 1:B->A 2:B->C 1:A->C */

1. Moving n discs needs the n − 1 discs moved twice plus one move: T(n) = 2T(n − 1) + 1, with T(1) = 1.
2. So T(1) = 1, T(2) = 3, T(3) = 7, T(4) = 15, T(5) = 31, …, T(10) = 1023.
3. The pattern is T(n) = 2ⁿ − 1 moves. For 64 discs that is 2⁶⁴ − 1 = 18,446,744,073,709,551,615 moves.

7. Tracing recursion in exam questions

Worked example 3: what is fun(4, 3)?

int fun(int x, int y) {
    if (x == 0) return y;
    return fun(x - 1, x + y);
}

Call	x == 0?	Next call
fun(4, 3)	No	fun(3, 4 + 3) = fun(3, 7)
fun(3, 7)	No	fun(2, 10)
fun(2, 10)	No	fun(1, 12)
fun(1, 12)	No	fun(0, 13)
fun(0, 13)	Yes	returns 13

Answer: 13 (it adds 4 + 3 + 2 + 1 to y). It is tail recursive: each call just passes its answer back.

More patterns from past papers:

• int fun(int x, int y) { if (y == 0) return 0; return x + fun(x, y - 1); } adds x to itself y times, so it computes x × y (fun(4, 3) = 12).
• Printing before or after the call reverses the order: with if (n == 0) return;, printing n before calling f(n − 1) prints 4 3 2 1 for n = 4, while printing after the call prints 1 2 3 4.
• main itself can be called recursively in C (not in C++). With static int i = 5;, the program if (--i) { printf("%d ", i); main(); } prints 4 3 2 1: the static i is shared by every call and reaches 0 after four prints.
• Beware of reading a global counter in the same printf that calls the function: in printf("%d %d", fib(5), calls); the order of evaluating the arguments is unspecified, so calls may be read before fib runs. Store the result first: v = fib(5); then print (5 and 15).

8. Recursion or iteration?

Point	Recursion	Iteration (loop)
Repeats by	The function calling itself	for, while, do-while
Stops at	The base case	The loop condition becoming false
Memory	One stack frame per active call: O(n) for factorial	A few variables: O(1)
Speed	Usually slower (call and return overhead)	Usually faster
Failure when wrong	Stack overflow	Infinite loop
Clearest for	Trees, divide and conquer, Tower of Hanoi, quicksort, merge sort	Simple counting and running totals

Every recursive function can be rewritten with a loop (and an explicit stack if needed), and the other way round. Writing a naturally iterative job recursively makes it use more memory and run slower; some compilers turn tail recursion back into a loop, but C compilers are not required to.

9. Neighbouring function topics asked with this chapter

• Function pointers: double (*f)(int, float); declares f as a pointer to a function taking an int and a float and returning double. The parentheses matter: double *f(int, float); declares a function that returns a double *. A function pointer is passed as a parameter like this: void pass(int (*fptr)(int, float, char)) { }.
• Function overloading (C++ and Java, not C) means several functions with the same name but different parameter lists. The return type alone cannot tell overloads apart. Overriding is a subclass redefining a method with the same signature (see object-oriented programming).
• Inline functions (C99 and C++) ask the compiler to paste the body at the call site to save call overhead; it is only a request.
• In C and C++, exit() ends the whole program from anywhere, while return leaves only the current function (returning from main also ends the program). In C++, a pure virtual function is written virtual void f() = 0;.