Recursion

Agenda

1. Introduction to Recursion
a. What is recursion?
b. Importance of recursion in computer science
c. Basic example of recursive processes

2. How Recursion Works

a. Base case
b. recursive case
c. Stack memory and function calls in recursion
d. Stack Overflow

3. Recursion Flow
4. Recursive Algorithms
a. Examples
b. Time complexity in recursive algorithms

5. Direct recursion vs indirect recursion

6. Advantages and disadvantages
7. Recursive vs. iterative approaches
1. Introduction to Recursion
As a programming project grows in size, it can become challenging to manage all
the code in one place, especially if it's all written inside the main() function. To
address this issue, developers often use functions to break the code into smaller,
more manageable pieces. In this approach, the main function serves as a driver
function that calls other functions to execute the program's logic.

a. What is Recursion?

Recursion is a programming technique that involves breaking a problem down

into smaller sub-tasks and repeatedly calling the function to solve them. It
provides an alternative to the iterative method, which can be more
time-consuming and require more effort.

It is a useful technique that makes code shorter and easier to read and write.

void recursion() {
recursion();
}

int main() {
recursion();
}
b. Importance of recursion in computer science

Recursion is an important concept in computer science because it is widely used

in algorithms, data structures, and programming languages. It is particularly
useful for dividing a problem into smaller subproblems and solving them
independently. Recursion helps analyze the efficiency of algorithms and
understand their complexity.

c. Basic example of recursive processes

Let’s discuss Factorial from the recursion point of view. Factorial is a

mathematical operation that calculates the product of all integers from 1 to a
given number N.

How can Factorial(N) be represented by a smaller subproblem?

𝐹𝑎𝑐𝑡𝑜𝑟𝑖𝑎𝑙(𝑁) = 𝑁 ∗ 𝐹𝑎𝑐𝑡𝑜𝑟𝑖𝑎𝑙(𝑁 − 1)

Factorial(N - 1) itself can be represented by a smaller subproblem as follows:

𝐹𝑎𝑐𝑡𝑜𝑟𝑖𝑎𝑙(𝑁 − 1) = (𝑁 − 1) ∗ 𝐹𝑎𝑐𝑡𝑜𝑟𝑖𝑎𝑙(𝑁 − 2)

And so on.

So, computing Factorial(N) recursively involves repeatedly multiplying N by

Factorial(N - 1) until 1 is reached.

For example:

● 5! = 5 * 4!
○ 4! = 4 * 3!
■ and so on.

This is how recursion breaks down the problem into smaller subproblems and
combines the results.
2. How Recursion Works

a. Base Case

● The base case in recursion is a fundamental condition that serves as the

termination point for the recursive algorithm.

● It defines the scenario in which the recursive function stops calling itself and
returns a specific result directly, without further recursion.

● Base cases are essential in recursion to prevent infinite recursion and to

provide a final answer or outcome for the problem being solved.

b. Recursive Case

● The recursive case in recursion refers to a specific condition within a

recursive function or algorithm where the function calls itself with a
modified input, typically moving closer to a base case, in order to break
down a complex problem into simpler, more manageable subproblems.

● This process continues until the base case is reached, allowing the algorithm
to solve the problem by aggregating the results from all the recursive calls.

c. Stack memory and function calls in recursion

● In recursion, function calls create stack frames on the call stack. Each frame
represents an active function call and contains relevant information. As the
recursion progresses, stack frames are added and removed from the stack in
a Last-In-First-Out (LIFO) order. Recursive calls continue until a base case
is reached, and then the results propagate back through the stack.

● It is important to consider stack memory usage to avoid stack overflow

errors. Recursion should be designed with proper termination conditions and
mindful memory management.
 d. Stack Overflow

● A stack overflow is a software error that occurs when a program attempts to

use more memory than is available on the stack, causing the program to
crash.

● If a recursive function doesn't reach or define a base case, the recursive calls
will never stop, which will cause a stack overflow problem.

● To avoid infinite recursion, Ensure that your recursive function has

well-defined base cases. These are the conditions under which the recursion
terminates, preventing further recursive calls. Make sure your base cases are
reachable and correctly designed to cover all scenarios.

3. Recursion Flow
The recursion process begins with the first function call and continues until a base
case is reached, after which the return statement is executed to terminate the
recursion.

#include <iostream>
using namespace std;

void printNumbers(int n) {
if (n < 1) {
return;
}
printNumbers(n - 1);
cout << n << " ";
}

int main() {
printNumbers(6);
return 0;
}

Output:

1 2 3 4 5 6
Explanation:

○ The main function calls the printNumbers function with an argument of 6,

passing 6 as the value of the n input parameter.

○ The printNumbers function is called with an input value of 6 for its n

parameter.

○ Since n is not less than 1, the function calls itself with an argument of n-1,
which is 5.

○ The new call to printNumbers is made with an input value of 5 for its n
parameter.

○ Since n is not less than 1, the function calls itself again with an argument of
n-1, which is 4.

○ The new call to printNumbers is made with an input value of 4 for its n
parameter.

○ This process continues until the function call is made with an input value of
1 for its n parameter.

○ Since n is now less than 1, the function immediately returns to the previous
call.

○ The cout statement is executed, printing the value of n (which is 1) followed

by a space.

○ The function returns to the previous call, which also executes the cout
statement and prints the value of n (which is 2) followed by a space.

○ This process continues until the function returns to the original call made by
the main function.

○ The printNumbers function has printed the numbers 6, 5, 4, 3, 2, and 1 in

reverse order.

○ The main function returns 0, indicating that the program executed

successfully.
 To print numbers in reverse order using recursion, you can modify the
printNumbers function from the previous example as follows:

void printNumbers(int n) {
if (n < 1) {
return;
}
cout << n << " ";
printNumbers(n - 1);
}

The only change is the order of the cout statement and the recursive call. In this
modified version of the function, the cout statement is executed before the
recursive call, resulting in the numbers being printed in reverse order.

4. Recursive Algorithms

a. Examples

i. Print the nth Fibonacci number:

#include<iostream>
using namespace std;

int fibonacciRecursive(int n) {
if (n <= 1)
return n;
return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
}

int main () {
int n = 10;
cout << fibonacciRecursive(n) << endl;
return 0;
}
ii. Power Function: x^n:

#include<iostream>
using namespace std;

int recursivePow(int x, int n) {

//Base Condition
if(n == 0) return 1;

//Edge case
if(x == 0) return 0;

//Recursive call
return x * recursivePow(x, n - 1);
}

int main () {
int x, n;
cin >> x >> n;
cout << recursivePow(x,n);
return 0;
}
b. Time complexity in recursive algorithms

● The time complexity of a recursive algorithm is the number of times the

function calls itself, multiplied by the time it takes to execute each
recursive call.

● The time complexity of a recursive algorithm can be analyzed using a

recursion tree. A recursion tree is a tree diagram that shows all the
recursive calls made by the function. The depth of a node in the tree
represents the number of times the function has been called at that point.

For example, let's analyze the time complexity of finding the n-th Fibonacci
number using recursion:

1. The maximum depth in the recursion tree is n recursive calls.

2. In each recursive call, the function makes two new recursive calls, which
means that the total number of calls is multiplied by 2.

3. So, the total number of times the function calls itself to find the n-th
𝑛
Fibonacci number is 2 .

That’s why, the time complexity of finding the n-th Fibonacci number using
𝑛
recursion is 𝑂(2 ).
5. Direct recursion vs Indirect Recursion
a. Direct recursion:

When a function calls itself, this is referred to as direct recursion. The

example we saw earlier is an example of direct recursion.

#include <iostream>
using namespace std;

int factorial(int n) {
if(n > 1)
return n * factorial(n - 1);
else
return 1;
}

int main() {
int num;
cin >> num;
cout << factorial(num) << endl;
return 0;
}
Working of factorial program:
b. Indirect recursion:

Indirect recursion happens when one function calls another function, and
that second function later calls the first function again. A classic example of
indirect recursion is when function A calls function B, which in turn calls
function A.

#include <iostream>
using namespace std;
void indirectRecursion2(int);
void indirectRecursion1(int n = 1){
if(n > 9)
return;
cout << n <<" ";
indirectRecursion2(n + 1);
}
void indirectRecursion2(int n = 1){
if(n > N)
return;
cout << n << " ";
indirectRecursion1(n+1);
}
int main()
{
int start = 1;
indirectRecursion1(start);
return 0;
}
6. Advantages and Disadvantages of Recursion
a. Advantages of Recursion:

Recursion can offer several benefits, such as making code more readable and
concise, increasing modularity and flexibility, reducing code duplication, and
improving the time complexity for certain problems.

b. Disadvantages of Recursion:

Disadvantages of recursion include the potential for stack overflow errors if the
recursion depth becomes too large, high memory consumption due to the
creation of new sets of variables and data for each function call, reduced
performance due to function call overhead and stack manipulation, difficulty in
debugging recursive functions, and increased code complexity.

7. Recursion VS Iteration

Recursion Iteration
Terminates when the base case Terminates when the condition
becomes true. becomes false.
Used with functions. Used with loops.
Every recursive call needs extra space Every iteration does not require any
in the stack memory. extra space.
Smaller code size. Larger code size.

8. To solve:
● Recursion: Fibonacci Numbers

● Recursive Digit Sum

● 10344 - 23 out of 5