<jupyter_start><jupyter_text>Print sum of digits of a number using Recursion<jupyter_code>def sum_of_digits(n):
    """Returns the sum of all digits of a given number"""
    if n == 0:
        return 0
    else:
        return ( n % 10 ) + sum_of_digits(n//10)
sum_of_digits(2865)<jupyter_output><empty_output><jupyter_text>Max no. of rope cuts<jupyter_code>def max_rope_cuts(n, a, b, c):
    """Find the maximum number of pieces of the rope left,
       when the rope of length n is cut in the lengths a, b and c"""
    if n == 0:
        return 0
    if n < 0:
        return -1
    res = max( max_rope_cuts(n-a, a, b, c), max_rope_cuts(n-b, a, b, c), max_rope_cuts(n-c, a, b, c))
    if res < 0:
        return -1
    else:
        return res+1
max_rope_cuts(23, 11, 9, 12)
max_rope_cuts(5, 2, 1, 5)
max_rope_cuts(12, 4, 5, 3)<jupyter_output><empty_output><jupyter_text>Print all subsets of a string<jupyter_code>def substrings(string, current, index=0):
    """Print all possible string subsets"""
    if index == len(string):
        print(current)
        return 1
    substrings(string, current, index+1)
    substrings(string, current+string[index], index+1)
    
substrings("ABC", "")<jupyter_output><empty_output><jupyter_text>Print numbers from n to 1<jupyter_code>def print_n_1(n):
    """Print the numbers in a reverse order from m till n"""
    if n < 1:
        return 0
    print(n)
    print_n_1(n-1)
print_n_1(12)<jupyter_output><empty_output><jupyter_text>Print numbers from 1 to n<jupyter_code>def print_1_n(n):
    """Print 1 to n using normal recursion"""
    if n < 1:
        return 0
    print_1_n(n-1)
    print(n)
print_1_n(12)<jupyter_output><empty_output><jupyter_text>Tail recursion is a recursive method where there is no computation after the recursive call step. Every modification or operation is done during or before the recursive function call. Therefore tail recursive functions are faster than normal recursion in some cases.<jupyter_code>def tail_recursive_1_n(n, k=1):
    """Print numbers from 1 to n using tail Recursion."""
    if n < 1:
        return 0
    print(k)
    tail_recursive_1_n(n-1, k+1)
tail_recursive_1_n(12)<jupyter_output><empty_output><jupyter_text>Tail Recursive Factorial<jupyter_code>def facto(n, val=1):
    """Print factorial of a given number using tail Recursion."""
    if n == 0:
        return val
    else:
        return facto(n-1, n*val)
facto(6)<jupyter_output><empty_output><jupyter_text>Palindrome<jupyter_code>def palind(string, start, end):
    """Check if a string is a palindrome using recursion."""
    if end == start:
        print(True)
    elif end < start:
        print(True)
    elif string[start] != string[end]:
        print(False)
    else:
        palind(string, start+1, end-1)
a = "aabbaa"
palind(a.lower(), 0, len(a)-1)<jupyter_output><empty_output><jupyter_text>Josephus problem<jupyter_code>def josephus(n, k):
    """Given n numbers arranged in a clockwise cycle and a value k <= n, 
       every kth number in n will be deleted.
       The next number will be treated as 1 and count will start again from 1 to k.
       This goes on till we have 1 number out of n that has remained alive.
       This recursive function will help find that winner number.
    """
    if n == 1:
        return n
    return (josephus(n-1, k) + k - 1) % n + 1
josephus(8, 2)<jupyter_output><empty_output><jupyter_text>Recursive solution for 0/1 knapsack<jupyter_code>def knapsack_recursive(weight_arr, value_arr, bag_weight, n):
    if n == 0 or bag_weight <= 0:
        return 0
    if weight_arr[n-1] <= bag_weight: # If weight of last element is less than the current bag weight
        return max(value_arr[n - 1] + knapsack_recursive(weight_arr, value_arr, bag_weight - weight_arr[n-1], n-1),
                   knapsack_recursive(weight_arr, value_arr, bag_weight, n-1))

    else:               # If weight of last element is greater than the current bag weight
        return knapsack_recursive(weight_arr, value_arr, bag_weight, n-1) # Exclude that element and it's value and not changing the bag weight
    
wt_arr = [2, 6, 7, 2, 4]
val_arr = [12, 12, 12, 15, 16]
bag_weight = int(input("Enter Bag Weight: "))
if len(wt_arr) != len(val_arr):
    print("Weight array length must be same as value array length")
else:
    a = knapsack_recursive(wt_arr, val_arr, bag_weight, len(wt_arr))
    print(a)<jupyter_output>Enter Bag Weight: 9
43
{'fraction_non_alphanumeric': 0.10636856368563685, 'fraction_numerical': 0.025519421860885277, 'mean_word_length': 3.5010162601626016, 'pattern_counts': {'":': 0, '<': 49, '<?xml version=': 0, '>': 40, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '10', 'dir': 'jupyter-structured-clean-dedup', 'id': '108410', 'license': 'MIT', 'n_tokens_mistral': 1663, 'n_tokens_neox': 1546, 'n_words': 489, 'path': 'recursion/Recursion_problems.ipynb', 'repo_name': 'ajayhb/Python-DSA', 'size': '4428'}