Briefly explain recursive algorithm?

Question

What data structure would you mostly likely see in a non recursive implementation of a recursive algorithm?

Answer 1

Recursive algorithm

It targets a problem by dividing it into smaller, manageable sub-problems.
The output of one recursion after processing one sub-problem becomes the input to the next recursive process.

recursive-algorithm(input) {
 //base-case
 if (isSmallEnough(input))
 compute the solution and return it
 else
 break input into simpler instances input1, input 2,...
 solution1 = recursive-algorithm(input1)
 solution2 = recursive-algorithm(input2)
 ...
 figure out solution to this problem from solution1, solution2,...
 return solution
 }

Problem: write a function that computes the sum of numbers from 1 to n

int sum (int n)

use a loop

int sum (int n) {
 int s = 0;
 for (int i=0; i<n; i++)
 s+= i;
 return s;
}

2. recursively

int sum (int n) {
 int s;
 if (n == 0) return 0;
 //else
 s = n + sum(n-1);
 return s;
}

How it works

• Recursion is no different than a function call
• The system keeps track of the sequence of method calls that have been started but not finished yet
(active calls)
• order matters