Introduction to Computing and

Programming
Recursion
 Recap

FUNCTION WITH ARRAYS MACRO & INLINE SOME PRACTICE QUESTIONS

FUNCTIONS ON THESE TOPICS
 Practice Questions
1. Write a function that takes a positive integer as input and displays all the
positive factors of that number
2. Write a function to find and count the sum of only even digits in an integer
3. Write a function to count the number of Vowels, Consonants and symbols and
print the same
4. Write a function to reverse the characters in an array of size k

5. Write a function to check whether a number can be expressed as the sum of two
prime numbers
You may use a separate method to check primality
#include <stdio.h>
void reverseArray(char arr[], int k) {
int start = 0;
Reversal operation
int end = k - 1;
// Reverse the characters in the array int main() {
char arr[] = "Hello Class!";
while (start < end) {
int size = sizeof(arr)/sizeof(arr[0]);
// Swap the characters printf("%d\n",size);
char temp = arr[start]; reversestring(arr,size);
arr[start] = arr[end];
for (int i = 0; i < size; i++) {
arr[end] = temp;
printf("%c", arr[i]);
start++; }
end--; return 0;
} }

}
Count the number of Vowels, Consonants else if (line[i] >= '0' && line[i] <= '9') {
and symbols and print the same ++digit;
}
#include <stdio.h> else if (line[i] == ' ') {++space; }
void countfunction(char line[], int size) else{++others;}
}
{int vowels, consonant, digit, space,others;
printf("Vowels: %d", vowels);
vowels = consonant = digit = space = others = 0; printf("\nConsonants: %d", consonant);
for (int i = 0; i < size; ++i) { printf("\nDigits: %d", digit);
if (line[i] == 'a' || line[i] == 'e' || line[i] == 'i' || printf("\nWhite spaces: %d", space);
printf("\nOthers: %d", others);
line[i] == 'o' || line[i] == 'u' || line[i] == 'A' ||
}
line[i] == 'E' || line[i] == 'I' || line[i] == 'O' || line[i]
== 'U') { int main() {
char line[] = "Hello, how are you?";
++vowels; } int size = sizeof(line)/sizeof(line[0]);
else if ((line[i] >= 'a' && line[i] <= 'z') || (line[i] >= countfunction(line, size);
'A' && line[i] <= 'Z')) { return 0;
++consonant;} }
Content

• What is Recursion?
• How Recursion works?
• Types of Recursion
• Advantages & Disadvantages of Recursion
Recursion
 What is Recursion?

• A process by which a function calls itself repeatedly is called

recursion.
• Either directly: X calls X
• OR, cyclically in a chain
• X calls Y, and Y calls X
• Recursion breaks the problem into smaller subproblems and
applies the same function to solve the smaller subproblems.
How Recursion Works?

1. Divide the problem into smaller subproblems.

2. Solve the smallest version of the problem (Base Case).
3. Combine the solutions of the smaller problems to solve the original
problem.
• Components of Recursion:
• Base Case: The condition that stops recursion.
• Recursive Case: The condition where the function continues
calling itself.
Recursion – How to write
• For a problem to be written in recursive form, two conditions are to be satisfied:
• It should be possible to express the problem in recursive form
• Solution of the problem in terms of solution of the same problem on smaller sized
data
• The problem statement must include a stopping condition (base case) and recurring
condition (recursive case)
Recursion Example
 Write a C program to calculate the factorial of a number
using function

Example: Let say number is 5

5! = 5*4*3*2*1 =120
Write a C program to calculate the factorial of a number
#include <stdio.h>
int calculateFactorial(int n) { // Check if the input is non-negative
int result = 1; // Initialize result to 1
if (number < 0) {

// Iteratively multiply result by i (from 2 to n) printf("Factorial is not defined for negative numbers.\n");
for (int i = 2; i <= n; i++) { } else {
result *= i; // Call the function and print the result
} int factorial = calculateFactorial(number);
return result; // Return the factorial result printf("Factorial of %d is: %d\n", number, factorial);
}
}
int main() {
int number;
// Ask the user for input return 0;
printf("Enter a number to calculate its factorial: "); }
scanf("%d", &number);
 How to solve using Recursion?

• Basic Syntax Structure of Recursive Functions:

Return_type function_name (args) {
// function statements
// base condition
// recursion case (recursive call)
}
• Used for repetitive computations in which each action is stated in
terms of a previous result
Write a C program to calculate the factorial of a number using Recursion
#include <stdio.h>
// Recursive function to calculate factorial // Check if the input is non-negative
int factorial(int n) { if (number < 0) {
if (n == 0 || n == 1) // Base case: factorial of 0 or printf("Factorial is not defined for negative
1 is 1 numbers.\n");
return 1;
} else {
else
return n * factorial(n - 1); // Recursive case: n // Call the recursive function and print the result
* factorial of (n - 1) int result = factorial(number);
}
printf("Factorial of %d is: %d\n", number, result);
}
int main() {
int number;
// Ask the user for input return 0;
printf("Enter a number to calculate its factorial: }
");
scanf("%d", &number);
Recursive
Function Call
Stack
• Recursive calls are pushed
onto the call stack.

• When the base case is

reached, the stack unwinds
and combines results.
A recursive function example
#include <stdio.h>

void CountDown(int countInt) {

if (countInt <= 0) {
printf("Go!\n"); Output
}
else {
printf("%d\n", countInt);
CountDown(countInt - 1);
}
}

int main(void) {
CountDown(2);
return 0;
}
 Write a C program to calculate the sum of n
number using Recursion
Eg: enter the number 5
5+4+3+2+1=15
 Write a C program to calculate the sum of n
number using Recursion
#include <stdio.h>
int main()
int nSum(int n)
{
{
int n = 5;
// base condition to terminate the recursion
when N = 0
if (n == 0) { // calling the function
return 0; int sum = nSum(n);
} printf("Sum of First %d Natural
Numbers: %d", n, sum);
// recursive case / recursive call
return 0;
int res = n + nSum(n - 1);
}
return res;}
 Recursion
Tree Diagram
of nSum(5)
Function
Function call Stack
of nSum(5)
Function Returning
Value
 Types of Recursion

• Direct Recursion: A function directly calls

itself.
• Head Recursion: The position of the
recursive call is at the start of the function.
• Tail Recursion: The position of the
recursive call is at the end of the function.
• Tree Recursion: Multiple recursive calls
present in the body of the function.
• Indirect Recursion: A function calls another
function, which in turn calls the original
function.
 C Program to Find the Factorial of a Natural
Number using Tail Recursion
#include <stdio.h>
int factorialTail(int n) int main()
{ {
// Base case int n = 5;
if (n == 1 || n == 0) { int fact1 = factorialTail(n);
return 1; printf("Resursive Factorial of %d: %d
} \n", n, fact1);
else {
// Tail recursive call return 0;
return n * factorialTail(n - 1); }
}
}
Example of
Tree
Recursion
 C Program to find the Fibonacci Number
using Tree Recursion
#include <stdio.h>
int fibonacci(int n) int main()
{ {
if (n <= 1) { int n = fibonacci(3);
return n; printf("%d", n);
} return 0;
else { }
// Tree recursive calls
return fibonacci(n - 1) + fibonacci(n - 2);
}}
Example of
Tree
Recursion