dsa/recursion at master · xpanvictor/dsa

Checkout above repo for code implementations for this topic

Case study project for this folder will be here - [notComplete]

Considering the Backus Naur Form for programming grammar formulation, recursion shows its advantage.

statement references itself.

The state of every function including main() is stored on the stack frame or activation record which is also stored on the runtime stack. The state involves data like return address, local variables and function parameters. Only the activation record of the main function outlives every other function.

Data in the activation record:

• values of parameters to fn, the address of first cell if an array or another data by ref is passed to fn.
• local variables, can be pointers to the addresses or file descriptors.
• return address to resume control by caller
• dynamic link; the address of the activation record of the caller
• returned value for a none void function

The returned value of a function is placed right above the activation record of the caller.

Hence, recursive fn calls operate by creating another activation record the function right on top of the currently running fn. It’s not a function calling itself but a fn calling another instantiation of the same fn.

Tail recursion

In this case, the recursive call is the last call and there are no other recursive calls. eg

void tail(int i) {
	if (tail > 0) {
		cout << i << endl;
		tail(i-1)
	}
}