Recursion

Problem:
Write a function sum_numbers_recursive that takes in an array of numbers and returns the sum of all the numbers in the array. 
Test case : sum_numbers_recursive([5, 2, 9, 10]) -> 26

Solution:

Step 1: Base case
We saw that any recursive function consists of two parts. One is base case & another one is recursive step. So, our first duty is to find the base case.
To do that, decompose the given problem into sub problem —> deompose the resulting sub problem further —> keep doing this, until it can’t be decomposed —> That last sub problem is the base case.

sum_numbers_recursive([5, 2, 9, 10]) -> 26sum_numbers_recursive([2, 9, 10]) -> 21sum_numbers_recursive([9, 10]) -> 19sum_numbers_recursive([10]) -> 10sum_numbers_recursive([]) -> 0 # Base side

Step 2: Recursive step

In base case step, we divided the given problem into sub problems. Now, think about how to link those sub problem results so that you can end up at the actual result. That’s the recursive step.
As an starting step, let’s see how can we link up first two sub problems.
First element from the input of given problem + result of second sub problem = final answer
sum_numbers_recursive([5, 2, 9, 10]) = 5 + sum_numbers_recursive([2, 9, 10])
Still, you did not hit the base case right? keep goin on, until the base case was hit.
sum_numbers_recursive([2, 9, 10]) = 2 + sum_numbers_recursive([9, 10])
sum_numbers_recursive([9, 10]) = 9 + sum_numbers_recursive([10])
sum_numbers_recursive([10]) = 10 + 0 # Observe that the base case was hit & an concrete result when base case is hit. That’s the very essense of recursion. You start building the final answer based on this result which you returned for an smallest sub problem.

def sum_numbers_recursive(numbers):
    # base case
    if len(numbers) == 0:
        return 0
    # recursive step
    return numbers[0] + sum_numbers_recursive(numbers[1:])

Problem:
Write a function, factorial, that takes in a number n and returns the factorial of that number.
The factorial of n is the product of all the positive numbers less than or equal to n. 
Test case : factorial(3) -> 6

Solution:
From math point of view, what factorials is teaching us is : permutations.
There is not much to explain. Same process that we followed for the first problem. Base case & Recursive step…..

def factorial(n):
    # base case
    if n == 1 or n == 0:
        return 1
    # recursive step
    return n * factorial(n - 1)

Problem:
Write a function sumOfLengths that takes in a list of strings and returns the total length of the strings.
Test case : sum_of_lengths([‘goat’, ‘cat’, ‘purple’]) -> 13

Solution:

def sum_of_lengths(strings):
    # base case
    if len(strings) == 0:
        return 0
    # recursive step
    return len(strings[0]) + sum_of_lengths(strings[1:])

Problem:
Write a function, reverse_string, that takes in a string as an argument.
The function should return the string with its characters in reverse order. 
Test case : reverse_string(“hello”) -> “olleh”

Solution:

def reverse_string(s):
    # base case
    if len(s) == 1:
        return s
    # base case -- edge case
    if len(s) == 0:
        return s
    # recursive step
    return s[-1] + reverse_string(s[0:-1])

Problem:
Write a function, palindrome, that takes in a string and returns a boolean indicating whether or not the string is the same forwards and backwards. 
Test case : palindrome(“pop”) -> True

Solution:

def palindrome(s):
    # base case
    if len(s) == 1:
        return True
    # base case -- Edge case
    if len(s) == 0:
        return True
    # recursive step
    if s[0] != s[-1]:
        return False
    return palindrome(s[1:-1])

Problem:
Write a function, fibonacci, that takes in a number argument, n, and returns the n-th number of the Fibonacci sequence. 
Test case : fibonacci(0) -> 0
0^th number of the sequence is 0.
1^st number of the sequence is 1.
To generate further numbers of the sequence, calculate the sum of previous two numbers.

Solution:

def fibonacci(n):
  # base case
  if n == 0:
    return 0 
  if n == 1:
    return 1 
  # recursive step
  return fibonacci(n-1) + fibonacci(n-2)