Recursion
Activity Outcomes:
This lab teaches you the following topics:
- How to formulate programs
- How to apply the three laws of
- How to implement the recursive formulation of a Problem
Introduction
An algorithm is recursive if it calls itself to do part of its work. For this approach to be successful, the ―call to itself‖ must be on a smaller problem then the one originally attempted. In general, a recursive algorithm must have two parts: the base case, which handles a simple input that can be solved without resorting to a recursive call, and the recursive part which contains one or more recursive calls to the algorithm where the parameters are in some sense ―closer‖ to the base case than those of the original call.
We divide/decompose the problem into smaller (sub) problems:
- Keep on decomposing until we reach to the smallest sub-problem (base case) for which a solution is known or easy to find
- Then go back in reverse order and build upon the solutions of the sub- problems
A recursive function is defined in terms of base cases and recursive steps.
- In a base case, we compute the result immediately given the inputs to the function
- In a recursive step, we compute the result with the help of one or more recursive calls to this same function, but with the inputs somehow reduced in size or complexity, closer to a base
What Happens When a Method is called?
Activation records (AR) will store the following information about the method:
- Local variables of the
- Parameters passed to the method.
- Value returned to the calling code (if the method is not a void type).
- The location in the calling code of the instruction to execute after returning from the called method.
Two ways of thinking:
For something simple to start with – let’s write a function pow(x, n) that raises x to a natural power of n. In other words, multiplies x by itself n times.
pow(2, 2) = 4
pow(2, 3) = 8
pow(2, 4) = 16
There are two ways to implement it.
If n == 1, then everything is trivial. It is called the base of recursion, because it immediately produces the obvious result: pow(x, 1) equals x.
Otherwise, we can represent pow(x, n) as x * pow(x, n – 1). In math’s, one would write xn = x * xn-1. This is called a recursive step: we transform the task into a simpler action (multiplication by x) and a simpler call of the same task (powwith lower n). Next steps simplify it further and further until n reaches 1.
Activity 1:
Write a recursive program to calculate factorial of a positive integer
Solution:
Activity 2:
Write a recursive program to find sum of an array elements
Solution:
#include <stdio.h>
// Return sum of elements in A[0..N-1]
// using recursion.
int findSum(int A[], int N)
{
if (N <= 0)
return 0;
return (findSum(A, N – 1) + A[N – 1]);
}
int main()
{
int A[] = { 1, 2, 3, 4, 5 };
int N = sizeof(A) / sizeof(A[0]); cout<< findSum(A, N);
return 0;
}
Activity 3:
Write a recursive program to find reverse of an array
Solution:
#include <bits/stdc++.h> using namespace std;
/* Function to reverse arr[] from start to end*/ void rvereseArray(int arr[], int start, int end)
{
if (start >= end) return;
int temp = arr[start]; arr[start] = arr[end]; arr[end] = temp;
// Recursive Function calling rvereseArray(arr, start + 1, end – 1);
}
/* Utility function to print an array */ void printArray(int arr[], int size)
{
for (int i = 0; i < size; i++) cout << arr[i] << ” “;
cout << endl;
}
/* Driver function to test above functions */ int main()
{
int arr[] = {1, 2, 3, 4, 5, 6};
// To print original array
printArray(arr, 6);
// Function calling rvereseArray(arr, 0, 5);
cout << “Reversed array is” << endl; // To print the Reversed array
printArray(arr, 6);
return 0;
}
Activity 4:
Write a recursive function to find the sum of array elements using binary recursion
Solution:
int BinarySum(int A[], int i, int n)
{
if (n == 1)then // base case return A[i];
else // recursive case I
return BinarySum(A, i, n/2) + BinarySum(A, i+n/2, n/2);
}
Home Activities:
- Write the recursive method to find the binary number of decimal number given by
- Write the method which takes the integer value (n) as input and prints the sequence of numbers from 0 to n in ascending order.
- Write the method which takes the integer value (n) as input and prints the sequence of numbers from n to 0 in descending
- Write the method which takes the integer value (n) as input and prints the sequence of numbers from 0 to n (ascending order) and n to 0 (descending order).
- Write a recursive function to compute first N Fibonacci Test and trace for N= 6
1 1 2 3 5 8
- Write a recursive function that has a parameter representing a list of integers and returns the maximum stored in the list. Thinking recursively, the maximum is either the first value in the list or the maximum of the rest of the list, whichever is larger. If the list only has 1 integer, then its maximum is this single value, naturally.
- Implementation of Euclid’s algorithm for finding the largest common divisor of two integers. It is based on the observation that the greatest common divisor of two integers m and n with m > n is the same as the greatest common divisor of n and m mod n.
- Write the recursive method to find all the subsets of given Assume that ifthe given input is ―abcd, the output will be:
Abcd, , abc, abd, ab, acd, ac, ad, a, bcd, bc, bd, b, cd, c, d
- Write the computer program to solve the puzzle of ―tower of Hanoi‖. The detailed description of the task is given on following link:
https://www.tutorialspoint.com/data_structures_algorithms/tower_of_hanoi.htm
- Here is a simple recursive function to compute the Fibonacci sequence:
long fibr(int n) { // Recursive Fibonacci generator
// fibr(46) is largest value that fits in a long Assert((n > 0) && (n< 47), “Input out of range”); if ((n == 1) || (n == 2)) return 1; // Base cases return fibr(n-1) + fibr(n 2); // Recursion
}
This algorithm turns out to be very slow, calling Fibra total of Fib(n) times. Contrast this with the following iterative algorithm:
long fibi(int n) { // Iterative Fibonacci generator
// fibi(46) is largest value that fits in a long Assert((n > 0) && (n
< 47), “Input out of range”); long past, prev, curr; // Store temporary values past = prev = curr = 1; // initialize
for (int i=3; i<=n; i++) { // Compute next value past = prev;
// past holds fibi(i-2)
prev = curr; // prev holds fibi(i-1) curr = past
+ prev; // curr now holds fibi(i)
}
return curr;
}
Related links
Single link list Stack AVL Trees Binary search Counting Sort
Doubly link list Queue Graphs Bubble Sort Radix sort
Circular link list Binary search tree Hashing Insertion Sort Bucket Sort
Josephus Problem Tree Traversal Heaps Quick Sort Merge Sort
At Cui tutorial, courses, past papers and final year projects
#tutorial #cui #pastpaper #courses
