# 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__

__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 **Fibr**a 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